2017-Sp24-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
开场各自看题，cjb和yzc觉得E是个简单的贪心，想好结论后就上去敲了一发获得wa，cjb和sub猜了C应该和普通nim游戏一模一样，写了获得wa，cjb写了暴力找到规律后'''C2y31'''. yzc和sub推式子加猜规律找到了A的做法，'''A1y43'''. 接下来时间就比较难受，尝试开K、H、B都没有成功，中途sub离开了一会儿，回来的时候想到了B的做法，'''B4y188'''. cjb觉得G是个二合一莫队，但是很容易tle，写了之后获得RE，但剩下时间不多了cjb也并不想继续去调试，sub尝试写H，时间不够就放弃了。
== 总结 ==
=== chenjb ===
 今天算是这段时间打得最不好的一场，一个是题目比较难受，UESTC出的这套题真的太麻烦了，要不很套路，要不就写了过不去卡时空，但是sub说得很对，还是我们太菜，Siunaus能做到5题呢，而且今天还是比较懈怠，也出现了看题失误的问题，所以大家要好好打起精神来补一下题呀！
=== oipotato ===
=== subconscious  ===
mark一个经典模型：f[mask]代表所有生成图个数,g[mask]代表联通图个数g[i]=f[i]-sigma(g[mask]*f[i/mask])，枚举x(属于mask属于i)
== 题解 ==
 * D：and的传递闭包可以做成一颗树，考虑构造一颗树，节点i表示第i个二进制位，注意bi第i个位一定为1。先建一个虚根，把1连在虚根下。b1到根的路径就是b1有的二进制位。 i从小到大处理。对于bi，将ai中的二进制位节点拿出来做lca，然后让节点i做lca的孩子。 归纳发现一个很神奇的性质，始终保证节点i到根路径表示bi中所有二进制位 维护lca，询问就是点到根路径并，暴力即可。 复杂度O(n2logn)  
 * G：树上莫队和普通莫队二合一...hdu非常卡常数，尽量写得好一些，记得加读入优化，还是过不了就算了....
 * H：dp[i][j][s1][s2]，代表的是前i个物品，总权值为j，已有s1个必选，s2必不选的方案数。那么对于当前一个状态，它有四种转移状态。[[BR]]
      1.选中当前的，增加权值，增加必选个数。[[BR]]
      2.选择当前的，增加权值，不增加必选个数。[[BR]]
      3.不选中当前的，不增加权值，增加不必选个数。[[BR]]
      4.不选中当前的，不增加权值，不增加必选个数。[[BR]]
      因为i，j可以互换，l，k也可以互换，故而最后方案数乘以4即为所求。
 * I：用Trie树来维护以每个位置为起始的特征串，注意到特征串的长度不会超过10，所以我们可以每次按一个长度建立可持久化Trie树，每次对所有询问的区间在线查询，更新答案，做10次即可，我分了奇偶去暴力预处理。
 * J：贪心+瞎jb搜索，要不就降到离目标以下最近的，要不就降到目标以上最近的，记得处理不能降到0以下，还有就是由于按up键也可以打断连续向下的功效所以应该记录停顿了几次，以后向上的时候用停顿补回来
== 补题 ==

流水账

开场各自看题，cjb和yzc觉得E是个简单的贪心，想好结论后就上去敲了一发获得wa，cjb和sub猜了C应该和普通nim游戏一模一样，写了获得wa，cjb写了暴力找到规律后C2y31. yzc和sub推式子加猜规律找到了A的做法，A1y43. 接下来时间就比较难受，尝试开K、H、B都没有成功，中途sub离开了一会儿，回来的时候想到了B的做法，B4y188. cjb觉得G是个二合一莫队，但是很容易tle，写了之后获得RE，但剩下时间不多了cjb也并不想继续去调试，sub尝试写H，时间不够就放弃了。

总结

chenjb

今天算是这段时间打得最不好的一场，一个是题目比较难受，UESTC出的这套题真的太麻烦了，要不很套路，要不就写了过不去卡时空，但是sub说得很对，还是我们太菜，Siunaus能做到5题呢，而且今天还是比较懈怠，也出现了看题失误的问题，所以大家要好好打起精神来补一下题呀！

oipotato

subconscious

mark一个经典模型：f[mask]代表所有生成图个数,g[mask]代表联通图个数g[i]=f[i]-sigma(g[mask]*f[i/mask])，枚举x(属于mask属于i)

题解

• D：and的传递闭包可以做成一颗树，考虑构造一颗树，节点i表示第i个二进制位，注意bi第i个位一定为1。先建一个虚根，把1连在虚根下。b1到根的路径就是b1有的二进制位。 i从小到大处理。对于bi，将ai中的二进制位节点拿出来做lca，然后让节点i做lca的孩子。 归纳发现一个很神奇的性质，始终保证节点i到根路径表示bi中所有二进制位 维护lca，询问就是点到根路径并，暴力即可。 复杂度O(n2logn)
• G：树上莫队和普通莫队二合一...hdu非常卡常数，尽量写得好一些，记得加读入优化，还是过不了就算了....
• H：dp[i][j][s1][s2]，代表的是前i个物品，总权值为j，已有s1个必选，s2必不选的方案数。那么对于当前一个状态，它有四种转移状态。
  

1.选中当前的，增加权值，增加必选个数。

2.选择当前的，增加权值，不增加必选个数。

3.不选中当前的，不增加权值，增加不必选个数。

4.不选中当前的，不增加权值，不增加必选个数。

因为i，j可以互换，l，k也可以互换，故而最后方案数乘以4即为所求。

• I：用Trie树来维护以每个位置为起始的特征串，注意到特征串的长度不会超过10，所以我们可以每次按一个长度建立可持久化Trie树，每次对所有询问的区间在线查询，更新答案，做10次即可，我分了奇偶去暴力预处理。
• J：贪心+瞎jb搜索，要不就降到离目标以下最近的，要不就降到目标以上最近的，记得处理不能降到0以下，还有就是由于按up键也可以打断连续向下的功效所以应该记录停顿了几次，以后向上的时候用停顿补回来

补题