2017-Sp169-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb和yzc秒了A，'''A1y4'''，之后cjb会做E，上机写E，中间yzc过了J，'''J1y8'''，sub推了B，'''B1y20'''，cjb拿下一血'''E1y27'''，之后yzc上机写D，cjb和sub讨论C，'''D1y34'''，'''C1y49'''，sub和yzc讨论K，上机'''K1y84'''，之后cjb开出了H，yzc上机写H，the了之后拍了拍，'''H2y199'''，之后cjb上机ntt，sub上机写G，ole了两发，感觉要手动分配空间，sub和yzc讨论好了F，yzc上机写F，'''F2y281'''，最后sub fix G，'''G4y286'''，考虑到现场没有memory limit，是rk2，vjudge上rk3，I题读错题没有出，有点可惜。
== 总结 ==
=== chenjb ===
读错题了，错亿，I是相邻格子.......
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：只有aaaaaa和abababab，枚举即可。

 * B：n*π(k+1-k/p)

 * C：如果H先手，则只有全1且n%3==0时会输，反之只有对手能通过一步变成那种局势时才有可能会输。

 * D：从后往前直接推出每个点期望子树大小，直接计算结果。

 * E：点分治，用bitset优化背包维护经过root点的连通块w的答案。

 * F：爆搜，所有三号卡牌肯定在每一轮的结束才用且顺序无关，在第三轮时三号卡牌一定打脸。

 * G：多项式第i个家庭的f[i]表示在这个家庭中选取i个错误匹配的方案数，分治乘完之后在每个位置配上(n-i)!，最后偶数项减去奇数项。

 * H：第一棵树中，第一个点选sqrt个关键点使得任意一个点到祖先中第一个关键点的路径长度不超过sqrt，之后对于每个关键点，在第二棵树从根开始遍历，如果遍历到的点属于我枚举的关键点的控制范围，则暴力将路径上的边添加，需要使用支持加边、删边的按秩合并并查集。

 * I：注意到所有限制条件都是相邻的，那么考虑对棋盘黑白染色，黑点按操作次数从小到大连，白点反之，从S连出n*m路到T，之后<=的限制从白向黑连约束，>=反之，可以理解为把所有白点的权值取反后，原约束条件变成了a-b<=x或a-b>=x，>=可以通过同乘-1变号，这样就变成经典的最小割模型了。

 * J：每次修改相当于让一个区间的2或3的质因子数量加一，用两个差分数组维护一下，最后取min即可。

 * K：对每个a[i]分类，把所有能被a[i]整除的部分全部拿走，可以发现剩下部分用树状数组维护，每次查询时二分即可。

 * L：拆成sqrt(n)个等差数列求gcd，对于每个等差数列，可以用类欧中把c改成1<<i然后%2得到第i位的答案，注意n<20000左右的要直接暴力求解来优化常数。

流水账

出门各自看题，cjb和yzc秒了A，A1y4，之后cjb会做E，上机写E，中间yzc过了J，J1y8，sub推了B，B1y20，cjb拿下一血E1y27，之后yzc上机写D，cjb和sub讨论C，D1y34，C1y49，sub和yzc讨论K，上机K1y84，之后cjb开出了H，yzc上机写H，the了之后拍了拍，H2y199，之后cjb上机ntt，sub上机写G，ole了两发，感觉要手动分配空间，sub和yzc讨论好了F，yzc上机写F，F2y281，最后sub fix G，G4y286，考虑到现场没有memory limit，是rk2，vjudge上rk3，I题读错题没有出，有点可惜。

总结

chenjb

读错题了，错亿，I是相邻格子.......

oipotato

subconscious

题解

  • A：只有aaaaaa和abababab，枚举即可。
  • B：n*π(k+1-k/p)
  • C：如果H先手，则只有全1且n%3==0时会输，反之只有对手能通过一步变成那种局势时才有可能会输。
  • D：从后往前直接推出每个点期望子树大小，直接计算结果。
  • E：点分治，用bitset优化背包维护经过root点的连通块w的答案。
  • F：爆搜，所有三号卡牌肯定在每一轮的结束才用且顺序无关，在第三轮时三号卡牌一定打脸。
  • G：多项式第i个家庭的f[i]表示在这个家庭中选取i个错误匹配的方案数，分治乘完之后在每个位置配上(n-i)!，最后偶数项减去奇数项。
  • H：第一棵树中，第一个点选sqrt个关键点使得任意一个点到祖先中第一个关键点的路径长度不超过sqrt，之后对于每个关键点，在第二棵树从根开始遍历，如果遍历到的点属于我枚举的关键点的控制范围，则暴力将路径上的边添加，需要使用支持加边、删边的按秩合并并查集。
  • I：注意到所有限制条件都是相邻的，那么考虑对棋盘黑白染色，黑点按操作次数从小到大连，白点反之，从S连出n*m路到T，之后<=的限制从白向黑连约束，>=反之，可以理解为把所有白点的权值取反后，原约束条件变成了a-b<=x或a-b>=x，>=可以通过同乘-1变号，这样就变成经典的最小割模型了。
  • J：每次修改相当于让一个区间的2或3的质因子数量加一，用两个差分数组维护一下，最后取min即可。
  • K：对每个a[i]分类，把所有能被a[i]整除的部分全部拿走，可以发现剩下部分用树状数组维护，每次查询时二分即可。
  • L：拆成sqrt(n)个等差数列求gcd，对于每个等差数列，可以用类欧中把c改成1<
附加文件