2017-Sp130-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，榜上有人过K和E，于是'''E1y12'''，'''K1y18'''。sub和yzc开了一波J，大力找了规律，yzc对拍了一下'''J1y54'''。cjb上机写G，反向边没初始化，'''G3y85'''。sub上机'''H1y94'''。yzc和sub讨论了B，yzc上机tle之后debug了一下'''B3y134'''。sub拿了个二次剩余板子'''I1y166'''，cjb上机写F，没删文件名'''F2y203'''。sub和yzc讨论了C，'''C1y227'''，之后rush D，cjb敲了三元环板子，sub上机rush，赛后10min通过。
== 总结 ==
=== chenjb ===
犯了些愚蠢错误，要注意。另外对于找最大割的题目可以考虑用一个很大的数减去w(假装在做负数)。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：

 * B：从根开始深搜，对于一个节点，二分出它的孩子中，从满k叉树到少一层的满k叉树的分界点，满k叉树的值可以预处理得到，递归分界点即可。

 * C：只需要令所有2*2的满足红=蓝即可，可以观察发现必须是相邻两行直接交替或相邻两列交替，统计下自由元数量即可。

 * D：把每个方块看成(x,y,z)，将问题容斥，前一部分很好计算，最后部分是个三元环计数，上个板子即可。

 * E：对于a，a和0显然可以，然后满足n/2.0的都可以，因为可以取b=n-a，反之显然不行，所以答案为(n-1)/2 + 2。

 * F：小于sqrt(500)的质数只有8个，对于每个数字，分拆成mask和base，mask表述包含那8个小质数的状态，base为1或者分解后大于sqrt(500)的因子，这样就把所有数字按base分组了，除了base为1的物品在mask合法的情况下可以随便取，其他每种物品只能取1个，带mask做背包即可。

 * G：f[i][j]表示第i个人至多得到j个糖，S向f[i][1]连inf，然后f[i][j]向f[i][j+1]连1000-w[i][j]的边，f[i][m]向T连1000-w[i][m]的边，对于一组限制(x,y,z)，若k-z<1则f[x][k]向S连inf边，否则k-z<=m则f[x][k]向f[y][k-z]连inf边，再否则向T连inf边，这些边限制了某些点必须在同一个集合。跑出答案后用n*1000-flow即可，这样实际上求了最大割。

 * H：极角序排序维护两边权值和即可。

 * I：两边乘以a[i]+a[j]，设x=a[i]/a[j]，可以得到x是一个二次剩余，大力判定数量即可，注意解出来之后要验算一遍。

 * J：观察发现进行2^i^次操作后，相当于求了一边mod 2^i^意义下的前缀异或和，直接倍增即可。

 * K：按定义推断数列即可。

 * L：

 * M：

 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-7-solutions-by-杭州二中/ Official]

流水账

开场各自看题，榜上有人过K和E，于是E1y12，K1y18。sub和yzc开了一波J，大力找了规律，yzc对拍了一下J1y54。cjb上机写G，反向边没初始化，G3y85。sub上机H1y94。yzc和sub讨论了B，yzc上机tle之后debug了一下B3y134。sub拿了个二次剩余板子I1y166，cjb上机写F，没删文件名F2y203。sub和yzc讨论了C，C1y227，之后rush D，cjb敲了三元环板子，sub上机rush，赛后10min通过。

总结

chenjb

犯了些愚蠢错误，要注意。另外对于找最大割的题目可以考虑用一个很大的数减去w(假装在做负数)。

oipotato

subconscious

题解

A：
B：从根开始深搜，对于一个节点，二分出它的孩子中，从满k叉树到少一层的满k叉树的分界点，满k叉树的值可以预处理得到，递归分界点即可。
C：只需要令所有2*2的满足红=蓝即可，可以观察发现必须是相邻两行直接交替或相邻两列交替，统计下自由元数量即可。
D：把每个方块看成(x,y,z)，将问题容斥，前一部分很好计算，最后部分是个三元环计数，上个板子即可。
E：对于a，a和0显然可以，然后满足n/2.0的都可以，因为可以取b=n-a，反之显然不行，所以答案为(n-1)/2 + 2。
F：小于sqrt(500)的质数只有8个，对于每个数字，分拆成mask和base，mask表述包含那8个小质数的状态，base为1或者分解后大于sqrt(500)的因子，这样就把所有数字按base分组了，除了base为1的物品在mask合法的情况下可以随便取，其他每种物品只能取1个，带mask做背包即可。
G：f[i][j]表示第i个人至多得到j个糖，S向f[i][1]连inf，然后f[i][j]向f[i][j+1]连1000-w[i][j]的边，f[i][m]向T连1000-w[i][m]的边，对于一组限制(x,y,z)，若k-z<1则f[x][k]向S连inf边，否则k-z<=m则f[x][k]向f[y][k-z]连inf边，再否则向T连inf边，这些边限制了某些点必须在同一个集合。跑出答案后用n*1000-flow即可，这样实际上求了最大割。
H：极角序排序维护两边权值和即可。
I：两边乘以a[i]+a[j]，设x=a[i]/a[j]，可以得到x是一个二次剩余，大力判定数量即可，注意解出来之后要验算一遍。
J：观察发现进行2ⁱ次操作后，相当于求了一边mod 2ⁱ意义下的前缀异或和，直接倍增即可。
K：按定义推断数列即可。
L：
M：
Official

附加文件

1.png by chenjb