2017-C29-team3

从 Trac 迁移的文章

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

原文章内容如下：

= 流水账 =

= 总结 =

== reku ==
  感觉我们猜结论的能力还是太弱...而且F题用错误的做法写了太久了。而且因为我读题能力太弱，我们两个人只能做到不停跟榜，无法发现新的可做题...
== lzw4896s ==
  主要失误还是在于C题,我一看就觉得是线性基搞一搞，也想到转化为A取一些数和B取一些数xor起来为0的方案数，然后就卡住了，没想到转化为求方程的解数。 最后和reku xjb乱搞竟然搞过去了，如果能早点想出来也多做一个题。
== Johann ==

= 教训 =

= 题解 =
 * C: 先求出A和B的线性基,设基的大小分别是a和b, 然后问题转化为 有 a + b的数， 每个数取或者不取，xor起来为0的方案数。 就是求一个线性异或方程组的解数，这个方程组有a + b的变量, 对C = A + B求出线性基的大小c, a + b - c就是方程组的自由元个数。 答案就是2^a + b - c^  
 * E: 求个前缀和, 把n + 1个前缀和排序， 然后最大最小，次大次小依次配对就好了。
 * B: 对于某个长度的边集，首先把小于这些边权值的所有边都缩点，然后对于缩点后的图，只能用该长度连接的点建立一个新图，然后利用Stoer Wagner对于每个连通块求个无向图最小割就好了
 * J: f[i][j][x][y]为dp到a[i]和b[j]，最大值和最小值分别为x,y的方案数，因为x或y一定有一个等于b[j]，所以状态只有n*m*m个，然后我们对于一个j去扫后面的状态，因为所有的状态我们都只关心其中的某一维，然后按照另一维的值放到m个树状数组中，扫一遍就好了

流水账

总结

reku

感觉我们猜结论的能力还是太弱...而且F题用错误的做法写了太久了。而且因为我读题能力太弱，我们两个人只能做到不停跟榜，无法发现新的可做题...

lzw4896s

主要失误还是在于C题,我一看就觉得是线性基搞一搞，也想到转化为A取一些数和B取一些数xor起来为0的方案数，然后就卡住了，没想到转化为求方程的解数。 最后和reku xjb乱搞竟然搞过去了，如果能早点想出来也多做一个题。

Johann

教训

题解

• C: 先求出A和B的线性基,设基的大小分别是a和b, 然后问题转化为 有 a + b的数， 每个数取或者不取，xor起来为0的方案数。 就是求一个线性异或方程组的解数，这个方程组有a + b的变量, 对C = A + B求出线性基的大小c, a + b - c就是方程组的自由元个数。 答案就是2^{a + b - c}
• E: 求个前缀和, 把n + 1个前缀和排序， 然后最大最小，次大次小依次配对就好了。
• B: 对于某个长度的边集，首先把小于这些边权值的所有边都缩点，然后对于缩点后的图，只能用该长度连接的点建立一个新图，然后利用Stoer Wagner对于每个连通块求个无向图最小割就好了
• J: f[i][j][x][y]为dp到a[i]和b[j]，最大值和最小值分别为x,y的方案数，因为x或y一定有一个等于b[j]，所以状态只有n*m*m个，然后我们对于一个j去扫后面的状态，因为所有的状态我们都只关心其中的某一维，然后按照另一维的值放到m个树状数组中，扫一遍就好了