2017-Sp07-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,400px)]]
== 流水账 ==
希望改善一下我们队后期总离过题只差一点点的情况，我们选择了风学长推荐的yandex cup的题目来训练。开场各自看题，sub认为J是简单题，上机写，写着发现不对，此前cjb和yzc讨论了一下D，觉得D就用以前的打架方法套个线段树就能找到众数了，就让yzc上机写D。看到有人过了G后，cjb和sub一起看G，yzc调试样例发现并不简单，cjb上机写G。G一开始似乎是因为没加文件读写(但后来不加也没事)wa了一发，后来加了wa在了别的地方，读了读代码找到了小错误，'''G3y49'''. sub和yzc讨论出了强行艹J的方法，yzc上机写J，J wa了两发后发现数组开小了，改后过了，'''J3y79'''(后来把文件读写删了又交了一次，也能过). 三人讨论题目，决定让cjb上机写B的搜索，yzc和sub尝试做A和F. cjb写了一段时间，一个小时之后调试完毕，交了就过了，'''B1y147'''. yzc上机写A，把之前他们两人讨论的几个式子一糊，然后就过了,'''A1y164'''. 剩下的时间，三人一起开题，sub发现C是个区间dp，和yzc讨论之后就让他上去打，cjb在场下溜达了一会儿就和sub看了看I，发现I十分傻逼，仙人掌上的独立集dp挺好写的，决定等yzc过了之后去写。结果接下来的一个半小时，yzc一直被卡常数，cjb用中间的20min高速写了I，但是获得wa，最后一段时间网十分垃圾，十分难交题。最后比赛结束也没有交题，最后比赛结束之后I几乎马上就过了，C也在比赛结束后半小时通过了，今天我们的原定目标也应该是6题的，这证明我们和理想状态还是有差距，Siunaus和Dominoes在封榜前都落后于我们，我们只要过掉任何一道题都能够打败他们，只可惜我们最后维持了4题，被他们5题小小地踩了踩。
== 总结 ==
=== chenjb ===
今天挺遗憾的，前面立体几何带着大家主动弃掉是比较科学的，封榜前也领先于去年集训队，但后来C和I非常难受，检讨下自己的I，应该更自信些，再早开哪怕10分钟，结果就会有变化了，但今天其实达到了我想要达到的训练效果，而最后的结果也看到了我们的不足，但今天其实离过掉那两题也就差一点点，相信通过接下来的训练，能够把那两题做到稳稳拿下，赛后也发现我们对于大多数题目的预判都是准确的，我觉得这场比赛选得挺好，能体现出我们的优势和不足，也达到了锻炼我们缺点的任务。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * C：f[l][r][d]表示剩下棋子原来第一个坐标是l，最后坐标为R，相差为D，dp即可，注意常数问题。
 * D：
   * 题意：有n只猪排成一排，每一只猪有一个颜色。q次操作，操作1:选择一个区间把里面的猪涂成同一种颜色。操作2:询问一个区间是否存在一种颜色，涂上这种颜色的猪多于一半，有则输出颜色，否则输出-1。n，q为2e5，颜色范围为[0,1e6)。
   * 解法：考虑用颜色数棵动态开点，回收内存的线段树维护每一种颜色在每个区间的数量。用set维护一段段区间，暴力修改，均摊O(n)。显然一个区间的答案一定是两个子区间的答案中的一个，于是用线段树维护，每一次区间合并都暴力询问颜色出现的次数。总复杂度O(nlog^2^n)。
 * E：
   * 题意：求n^x^=x(mod m)的解集，输出前50000个剩余类。n,m<=1000000.
   * 解法：n^x^是rho形结构。结论：所有解都出现在环上。显然模数为两边环长gcd，枚举环上值，用CRT即可求出对应解。注意要偏移来保证走到了环上。
 * H：
   * 题意：询问对于一个长度为n<=10000000的串，KMP后有多少个不同的next数组，并且next数组里元素大小不超过k<=10。
   * 解法：考虑next数组的求解过程，因为pre[i]是从pre[i-1](当前指针j)推过来的，所以pre[i]实际上只和pre[1..k]有关，因此我们暴力枚举前k位合法的next数组，然后求出转移矩阵，对于后面n-k位做矩阵快速幂求方案就好。所谓合法的next数组，在枚举pre[i]的时候，for(j=pre[i-1];;j=pre[j])然后令pre[i]=j+1(参考于next数组的实际求解过程)，至于pre[i]=j+1是否能够合法，还要检验for(t=pre[i-1];t!=j;t=pre[t])中是否存在pre[t+1]=i+1，因为如果存在就不符合next数组的最长匹配位置的定义了。实现的时候要注意常数，极限数据还是有点卡时的。
 * I：仙人掌上dp，双联通分量缩点后，类似树型dp就好，对于一个环，环根取的话两端不取，否则取，扫两次就好。
== 补题 ==
 * ~~C~~ by sub
 * ~~D~~ by yzc
 * ~~E~~ by sub
 * ~~H~~ by cjb
 * ~~I~~ by cjb

流水账

希望改善一下我们队后期总离过题只差一点点的情况，我们选择了风学长推荐的yandex cup的题目来训练。开场各自看题，sub认为J是简单题，上机写，写着发现不对，此前cjb和yzc讨论了一下D，觉得D就用以前的打架方法套个线段树就能找到众数了，就让yzc上机写D。看到有人过了G后，cjb和sub一起看G，yzc调试样例发现并不简单，cjb上机写G。G一开始似乎是因为没加文件读写(但后来不加也没事)wa了一发，后来加了wa在了别的地方，读了读代码找到了小错误，G3y49. sub和yzc讨论出了强行艹J的方法，yzc上机写J，J wa了两发后发现数组开小了，改后过了，J3y79(后来把文件读写删了又交了一次，也能过). 三人讨论题目，决定让cjb上机写B的搜索，yzc和sub尝试做A和F. cjb写了一段时间，一个小时之后调试完毕，交了就过了，B1y147. yzc上机写A，把之前他们两人讨论的几个式子一糊，然后就过了,A1y164. 剩下的时间，三人一起开题，sub发现C是个区间dp，和yzc讨论之后就让他上去打，cjb在场下溜达了一会儿就和sub看了看I，发现I十分傻逼，仙人掌上的独立集dp挺好写的，决定等yzc过了之后去写。结果接下来的一个半小时，yzc一直被卡常数，cjb用中间的20min高速写了I，但是获得wa，最后一段时间网十分垃圾，十分难交题。最后比赛结束也没有交题，最后比赛结束之后I几乎马上就过了，C也在比赛结束后半小时通过了，今天我们的原定目标也应该是6题的，这证明我们和理想状态还是有差距，Siunaus和Dominoes在封榜前都落后于我们，我们只要过掉任何一道题都能够打败他们，只可惜我们最后维持了4题，被他们5题小小地踩了踩。

总结

chenjb

今天挺遗憾的，前面立体几何带着大家主动弃掉是比较科学的，封榜前也领先于去年集训队，但后来C和I非常难受，检讨下自己的I，应该更自信些，再早开哪怕10分钟，结果就会有变化了，但今天其实达到了我想要达到的训练效果，而最后的结果也看到了我们的不足，但今天其实离过掉那两题也就差一点点，相信通过接下来的训练，能够把那两题做到稳稳拿下，赛后也发现我们对于大多数题目的预判都是准确的，我觉得这场比赛选得挺好，能体现出我们的优势和不足，也达到了锻炼我们缺点的任务。

oipotato

subconscious

题解

• C：f[l][r][d]表示剩下棋子原来第一个坐标是l，最后坐标为R，相差为D，dp即可，注意常数问题。
• D：
  • 题意：有n只猪排成一排，每一只猪有一个颜色。q次操作，操作1:选择一个区间把里面的猪涂成同一种颜色。操作2:询问一个区间是否存在一种颜色，涂上这种颜色的猪多于一半，有则输出颜色，否则输出-1。n，q为2e5，颜色范围为[0,1e6)。
  • 解法：考虑用颜色数棵动态开点，回收内存的线段树维护每一种颜色在每个区间的数量。用set维护一段段区间，暴力修改，均摊O(n)。显然一个区间的答案一定是两个子区间的答案中的一个，于是用线段树维护，每一次区间合并都暴力询问颜色出现的次数。总复杂度O(nlog²n)。
• E：
  • 题意：求n^x=x(mod m)的解集，输出前50000个剩余类。n,m<=1000000.
  • 解法：n^x是rho形结构。结论：所有解都出现在环上。显然模数为两边环长gcd，枚举环上值，用CRT即可求出对应解。注意要偏移来保证走到了环上。
• H：
  • 题意：询问对于一个长度为n<=10000000的串，KMP后有多少个不同的next数组，并且next数组里元素大小不超过k<=10。
  • 解法：考虑next数组的求解过程，因为pre[i]是从pre[i-1](当前指针j)推过来的，所以pre[i]实际上只和pre[1..k]有关，因此我们暴力枚举前k位合法的next数组，然后求出转移矩阵，对于后面n-k位做矩阵快速幂求方案就好。所谓合法的next数组，在枚举pre[i]的时候，for(j=pre[i-1];;j=pre[j])然后令pre[i]=j+1(参考于next数组的实际求解过程)，至于pre[i]=j+1是否能够合法，还要检验for(t=pre[i-1];t!=j;t=pre[t])中是否存在pre[t+1]=i+1，因为如果存在就不符合next数组的最长匹配位置的定义了。实现的时候要注意常数，极限数据还是有点卡时的。
• I：仙人掌上dp，双联通分量缩点后，类似树型dp就好，对于一个环，环根取的话两端不取，否则取，扫两次就好。

补题

• C by sub
• D by yzc
• E by sub
• H by cjb
• I by cjb

附加文件

• 1.png by chenjb