2017-Sp112-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，sub表示会做I，上机wa了。cjb想好了D，和yzc讨论了mex的求解，sub很快开出了D，上机'''D1y34'''，yzc紧接着上机'''H1y48'''。cjb开出了B，上机'''B1y82'''。sub和yzc讨论了J，sub上机写J，tle了两发，压了常数过去了'''J3y117'''。之后sub和yzc开构造题G，cjb开I，cjb和sub讨论了I的构造证明，大力一发'''I1y171'''。之后cjb单独开C，sub和yzc继续搞G，之后cjb有了思路，和sub聊了好几次，最后'''C1y266'''。G一直在爆搜调整，一直和满足条件的构造差一点，没能艹过去。
== 总结 ==
=== chenjb ===
构造题卡了一年??? 有点毒，还好刚了个dp...感觉这套题的几个题都挺妙的，推荐C、H、I。后来发现我们的G构造是1650，标解的构造基本只有一种，要不是1718或者1722，我觉得很震惊啊....到底为什么大家都能想到啊，我觉得不natural啊，subgg怎么撸不出来啊...
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：'''sub变态几何咕咕咕咕咕咕咕咕'''

 * B：按横坐标排序后考虑第i个点和x相同且y最接近的至多2个点连无向边，初始化所有点可行。之后如果存在两个连通块大小为奇数，则都不可行，若连通块大小为偶数则该连通块都不可行，对于每个连通块双联通分量缩点，则点到子树点是割边且子树size为奇数，则这个点也不可行。

 * C：易证最优方案肯定是往两边放，而且两边向中间不增。考虑f[i][j]代表前i个家庭，放了j个人在左边的最大距离差，决策就是把第i+1个家庭放在左侧还是右侧，转移方程中还要考虑放置端所有房屋对于未放置的人的增量。放置左端转移方程为：f[i+1][j+a[i+1]]=max(f[i][j]+a[i+1]*(sum[i]-j)*(n-i)+j*(S-sum[i]))，同理放置右端为f[i+1][j]=max(f[i][j]+a[i+1]*j*(n-i)+(sum[i]-j)*(S-sum[i]))

 * D：分治，每次把所有点投影到x的中位数点的竖轴上，分治即可。

 * E：考虑h和w的最大公约数的步数，为了保证循环节恰为h*w，必须使得向下走的步数与h互质，向右走的步数与w互质，在同一个最大公约数内走的形态完全相同，设t为gcd(h,w)，枚举k(0..t)，使得gcd(h,k)为1，gcd(w,t-k)为1，ans+=C(t,k)。

 * F：根据题意，最后合法的路径一定将所有的行和列都拆成了两个一对的格子，于是显然终点只会在某一个格子数为奇数的行上，于是O(n)枚举终点，O(n^2^)检查是否合法即可。

 * G：取p=13为质数，构造13*13的大网格，每个网格为13*13，一共169*169，对于每个大格子内部，取其对角线偏移i+j为全部取O，可以证明对于任意两行x1,x2，y1=y2时最多只存在唯一解，得证合法。[[BR]]'''PS：不能理解这么多人在赛场上是如何natural地想到这个构造的...'''.[[BR]]

 * H：对于每个石子视作一个独立的nim游戏，那么转化为有限制的取石子问题，线段树上维护某一个sg值最晚出现的位置，然后二分找到mex值就好了。

 * I：首先，如果存在一个RBRB...的奇环，那无敌了，肯定yes。否则考虑从枚举终点和到达终点的颜色，大力感受到枚举终点和颜色后只要按照黑白染色，一定能构造出解，所以floodfill判断一下是否所有边都经历过，顺便判断下有没有找到一个点在floodfill中f[i][0]和f[i][1]都遍历到就好了。

 * J：从左往右dp，f[cur][line][mod][mask]代表到第cur段经过了line次目前的和模M余mod，目前出现过mask这些点的方案数，大力dp，注意常数即可。

 * [wiki:2016-E23-team1  Siunaus]

 * [https://wiki.icpc.camp/wood-cube/XVII%20Open%20Cup%20GP%20of%20Japan WoodCube]

流水账

开场各自看题，sub表示会做I，上机wa了。cjb想好了D，和yzc讨论了mex的求解，sub很快开出了D，上机D1y34，yzc紧接着上机H1y48。cjb开出了B，上机B1y82。sub和yzc讨论了J，sub上机写J，tle了两发，压了常数过去了J3y117。之后sub和yzc开构造题G，cjb开I，cjb和sub讨论了I的构造证明，大力一发I1y171。之后cjb单独开C，sub和yzc继续搞G，之后cjb有了思路，和sub聊了好几次，最后C1y266。G一直在爆搜调整，一直和满足条件的构造差一点，没能艹过去。

总结

chenjb

构造题卡了一年??? 有点毒，还好刚了个dp...感觉这套题的几个题都挺妙的，推荐C、H、I。后来发现我们的G构造是1650，标解的构造基本只有一种，要不是1718或者1722，我觉得很震惊啊....到底为什么大家都能想到啊，我觉得不natural啊，subgg怎么撸不出来啊...

oipotato

subconscious

题解

A：sub变态几何咕咕咕咕咕咕咕咕
B：按横坐标排序后考虑第i个点和x相同且y最接近的至多2个点连无向边，初始化所有点可行。之后如果存在两个连通块大小为奇数，则都不可行，若连通块大小为偶数则该连通块都不可行，对于每个连通块双联通分量缩点，则点到子树点是割边且子树size为奇数，则这个点也不可行。
C：易证最优方案肯定是往两边放，而且两边向中间不增。考虑f[i][j]代表前i个家庭，放了j个人在左边的最大距离差，决策就是把第i+1个家庭放在左侧还是右侧，转移方程中还要考虑放置端所有房屋对于未放置的人的增量。放置左端转移方程为：f[i+1][j+a[i+1]]=max(f[i][j]+a[i+1]*(sum[i]-j)*(n-i)+j*(S-sum[i]))，同理放置右端为f[i+1][j]=max(f[i][j]+a[i+1]*j*(n-i)+(sum[i]-j)*(S-sum[i]))
D：分治，每次把所有点投影到x的中位数点的竖轴上，分治即可。
E：考虑h和w的最大公约数的步数，为了保证循环节恰为h*w，必须使得向下走的步数与h互质，向右走的步数与w互质，在同一个最大公约数内走的形态完全相同，设t为gcd(h,w)，枚举k(0..t)，使得gcd(h,k)为1，gcd(w,t-k)为1，ans+=C(t,k)。
F：根据题意，最后合法的路径一定将所有的行和列都拆成了两个一对的格子，于是显然终点只会在某一个格子数为奇数的行上，于是O(n)枚举终点，O(n²)检查是否合法即可。
G：取p=13为质数，构造13*13的大网格，每个网格为13*13，一共169*169，对于每个大格子内部，取其对角线偏移i+j为全部取O，可以证明对于任意两行x1,x2，y1=y2时最多只存在唯一解，得证合法。
PS：不能理解这么多人在赛场上是如何natural地想到这个构造的....
H：对于每个石子视作一个独立的nim游戏，那么转化为有限制的取石子问题，线段树上维护某一个sg值最晚出现的位置，然后二分找到mex值就好了。
I：首先，如果存在一个RBRB...的奇环，那无敌了，肯定yes。否则考虑从枚举终点和到达终点的颜色，大力感受到枚举终点和颜色后只要按照黑白染色，一定能构造出解，所以floodfill判断一下是否所有边都经历过，顺便判断下有没有找到一个点在floodfill中f[i][0]和f[i][1]都遍历到就好了。
J：从左往右dp，f[cur][line][mod][mask]代表到第cur段经过了line次目前的和模M余mod，目前出现过mask这些点的方案数，大力dp，注意常数即可。
Siunaus
WoodCube

附加文件

1.png by chenjb