2017-C12-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(0831.png)]]
= 流水账 =
   今天开始的时候就是无脑签到。然后A的时候，很快讨论了一个n2log/64的算法，感觉xjb优化一下就能过，本地极限数据跑一下只需要两秒，感觉很稳。然而垃圾杭电，把取余优化掉，赛后18分钟终于卡过了A。
= 总结 =

== reku ==
  感觉今天头脑一点也不冷静。其实完全在比赛时可以过掉A的，但是后来常数卡完之后，又因为一个傻吊错误卡了半个小时，导致比赛的时候没有过掉这个题，打出GG。   
== lzw4896s ==
   今天签到题过得就有点慢，之后开了A题，想到一个n^2^logn / bitset 的做法，本地极限数据跑了2s，时限开了3.5s，结果交上去就TLE(hdoj上大概要跑4s,猜测是hdoj是32位机，本地64位，bitset的时间相差了一倍)，心态有点崩。之后reku学长开始卡常，我觉得可能正解不是这样做的，觉得mod 2可能会有什么神奇的性质，就在边上闷头想，结果越想越困，脑子越来越不清楚，导致最后我们的程序能卡过去了，却因为一个小错误没有发现，WA到结束也没有看出来。其实今天的B题也不算难，但是我认为自己不擅长字符串，A题过的队伍又比较多，所以没有仔细去想。 之后的比赛要避免一个人闷头想题，遇到卡题的时候要勇于放弃，去开新的题目。
== Johann ==

= 教训 =

= 题解 =
   * A： 我们队比赛时的做法： 枚举B, 对于一个B, 将A的计数数组分成[0,B - 1] [B, 2B-1][2B, 3B-1]...这样的块。对于每一块,把它的计数01序列和 ans[0..B - 1] 用bitset xor 一下。 有NlognN段,每段耗时N / bitset. 总的复杂度是O(N^2^logN / bitset). 这样是卡不过去的，还要对于B比较小的情况(<=5000)直接暴力，暴力的时候还要注意不要有太多的mod操作，对于B大一点分块，最后3.4s卡过去了。  堡学长的做法：从大到小枚举k, 对于一个k, 对它有贡献的只是那些比k大的b。 对于每个b, 对它的所有倍数计数(只需要关心奇偶性)，维护一个bitset，第i位表示i这个数是多少个b(b > k)的倍数(奇数为1偶数为0)。 计算答案的时候只要把a的计数数组右移k位，然后和b的倍数的bitset做and操作。  时间复杂度O(N^2^ / bitset)。   
   * B： 把每个串以及和它反对称的串都插入AC自动机，dp[i][pos][mask] 表示在自动机上走i步,走到自动机的pos位置,mask二进制表示那些串已经出现过。 在自动机上先走L步, 对于长度为2L的符合要求的反对称串，如果有一个子串跨过了中轴线, 那么要么它在轴线左边的长度>= 在轴线右边的长度, 要么把它反过来后在轴线左边的长度>= 在轴线右边的长度。 所以只要枚举状态dp[L][pos][mask]，从pos开始 沿着trie树的父亲走,如果它是父亲的左儿子，那么往右边走，反之亦然，一定会枚举到那个子串。这样最多走10步， 总的复杂度O(L * 自动机点数 * 2^6^ * 10)，比官方题解要好写，耗时也更少。  Orz 贺总
   * I： 一个d进制数一定在 d^d-1^ 和 d^d^之间。 考虑<=lim的有多少个。  如果d^d^ <= lim 那么这些d的排列组成的d! - (d - 1)!都<=lim.  所以实际要算的只是1-2个d。把lim转化为d进制 逐位统计一下就好了。(reku:学习了一下康拓展开)
  * G:  dp方程感觉还不是很理解啊，大概还是记录一下每个点的子树的全部子图的匹配数，然后记录一下这个点是否参与匹配，之后暴力合并...不过这个时间复杂度的计算很有意思

流水账

今天开始的时候就是无脑签到。然后A的时候，很快讨论了一个n2log/64的算法，感觉xjb优化一下就能过，本地极限数据跑一下只需要两秒，感觉很稳。然而垃圾杭电，把取余优化掉，赛后18分钟终于卡过了A。

总结

reku

感觉今天头脑一点也不冷静。其实完全在比赛时可以过掉A的，但是后来常数卡完之后，又因为一个傻吊错误卡了半个小时，导致比赛的时候没有过掉这个题，打出GG。

lzw4896s

今天签到题过得就有点慢，之后开了A题，想到一个n²logn / bitset 的做法，本地极限数据跑了2s，时限开了3.5s，结果交上去就TLE(hdoj上大概要跑4s,猜测是hdoj是32位机，本地64位，bitset的时间相差了一倍)，心态有点崩。之后reku学长开始卡常，我觉得可能正解不是这样做的，觉得mod 2可能会有什么神奇的性质，就在边上闷头想，结果越想越困，脑子越来越不清楚，导致最后我们的程序能卡过去了，却因为一个小错误没有发现，WA到结束也没有看出来。其实今天的B题也不算难，但是我认为自己不擅长字符串，A题过的队伍又比较多，所以没有仔细去想。 之后的比赛要避免一个人闷头想题，遇到卡题的时候要勇于放弃，去开新的题目。

Johann

教训

题解

• A： 我们队比赛时的做法： 枚举B, 对于一个B, 将A的计数数组分成[0,B - 1] [B, 2B-1][2B, 3B-1]...这样的块。对于每一块,把它的计数01序列和 ans[0..B - 1] 用bitset xor 一下。 有NlognN段,每段耗时N / bitset. 总的复杂度是O(N²logN / bitset). 这样是卡不过去的，还要对于B比较小的情况(<=5000)直接暴力，暴力的时候还要注意不要有太多的mod操作，对于B大一点分块，最后3.4s卡过去了。 堡学长的做法：从大到小枚举k, 对于一个k, 对它有贡献的只是那些比k大的b。 对于每个b, 对它的所有倍数计数(只需要关心奇偶性)，维护一个bitset，第i位表示i这个数是多少个b(b > k)的倍数(奇数为1偶数为0)。 计算答案的时候只要把a的计数数组右移k位，然后和b的倍数的bitset做and操作。 时间复杂度O(N² / bitset)。
• B： 把每个串以及和它反对称的串都插入AC自动机，dp[i][pos][mask] 表示在自动机上走i步,走到自动机的pos位置,mask二进制表示那些串已经出现过。 在自动机上先走L步, 对于长度为2L的符合要求的反对称串，如果有一个子串跨过了中轴线, 那么要么它在轴线左边的长度>= 在轴线右边的长度, 要么把它反过来后在轴线左边的长度>= 在轴线右边的长度。 所以只要枚举状态dp[L][pos][mask]，从pos开始 沿着trie树的父亲走,如果它是父亲的左儿子，那么往右边走，反之亦然，一定会枚举到那个子串。这样最多走10步， 总的复杂度O(L * 自动机点数 * 2⁶ * 10)，比官方题解要好写，耗时也更少。 Orz 贺总
• I： 一个d进制数一定在 d^d-1 和 d^d之间。 考虑<=lim的有多少个。 如果d^d <= lim 那么这些d的排列组成的d! - (d - 1)!都<=lim. 所以实际要算的只是1-2个d。把lim转化为d进制 逐位统计一下就好了。(reku:学习了一下康拓展开)
  • G: dp方程感觉还不是很理解啊，大概还是记录一下每个点的子树的全部子图的匹配数，然后记录一下这个点是否参与匹配，之后暴力合并...不过这个时间复杂度的计算很有意思

附加文件

• 0831.png by ruiker