2017-Sp96-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，有人过E，讨论了一下，cjb上机写，发现有点问题，sub fix了一下做法，'''E1y35'''。yzc上机写B的莫队，wa了一发，对拍找不到错，后来sub猛然点醒需要特判0，'''B2y70'''。sub上机写K，许久wa了，发现问题，然后数组开小了又RE，'''K3y102'''。之后三个人讨论了许久H，中途cjb试图上机随机搞D，失败。yzc上机'''H1y138'''。三个人研究A，无果，sub表示会F，上机写F，失败，封榜后猛然想起可以FWT，想到可能的corner case，侥幸交wa了，改了double，wa，'''A3y276'''。
== 总结 ==
=== chenjb ===
菜菜，A应该早想到的。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：FWT，为了避免被出题人卡mod数，换一个mod数就好。

 * B：答案显然为区间里每一种出现次数/2并向上取整之和，特判0，莫队即可。

 * C：写一个函数，每次传入一个k，用o(n)的时间返回k的答案，当k<=sqrt(n)，直接暴力做，否则显然k的答案不会比n/k大，那么对于大于sqrt(n)的k，答案显然不会超过sqrt(n)，所以对于所有这些k，答案变化次数不会超过sqrt(n)，于是进行sqrt(n)次二分，找到每一种答案对应的k的区间即可，实现的时候直接在dfs序上逆序做即可，同时可以用整体二分减少常数。

 * D：n大的时候答案肯定是0，我们考虑n<=13(14)的时候直接做，n>13(14)的时候直接让后面的男女生一一对应，算出一个和0差的数字，前面的13(14)的数字肯定能凑出一个让答案为0的数字，就对前13(14)个男女生找这个值就好了。对于这十几个男生女生，找的时候我们考虑折半，先P(magic,magic/2)枚举前一半女生和前一半男生匹配，让剩余一半女生和后一半男生匹配，对于每一半女生直接枚举全排列(magic/2)!，然后塞进set里，直接find所需要的数值就好了。n<=13(14)的时候也是类似的折半做法，在set里lower_bound(mod-x)，如果找不到就取set.begin()。

 * E：首先统计点相邻边边权为奇数的个数，同时还需要判断该点相邻最大边权的两倍大于邻边权之和，此时要取最大边圈两倍减去邻边权之和，最后答案除以2。

 * F：f代表当前状态前至少需要经过多少轮当前的那个人才能判断自己的rank（注意这个值可以是非法的），tl代表当前状态前至少需要经过多少轮才非法（之前已经有人报出自己rank），ans可由f推出。

 * G：block将点分为了很多横棒和竖棒，显然同一棒子上的答案一样。假如两个棒子有交叉点，则连一条边，然后bfs即可得到每个点两个方向上的最小答案。由于边数过多，考虑用线段树优化建图，又因为不同的列的棒子编号不同，于是考虑用主席树来维护建图，两个方向各做一遍之后就得到每个点光线以两种方向来到这个点的最小步数之和。不难发现，每个点的两个答案是恰好差1的，于是我们现在的总和sum=2*ans+光线能到的点数。于是同时维护哪些点能到即可推出答案。注意边权有0，1时bfs需特殊处理，或者直接使用最短路算法。

 * H：从轻的往重的连边，每个点最长链加起来。

 * I：行上环长为x，列上环长为y可获得gcd(x,y)个置换环，枚举较小维的拆分数，组合数可得方案数，对于较大维，f[i]代表较大维长度为i时的答案，枚举环长组合数dp即可，O(n^2^*partition(m))。

 * J：因为集合大小只有5，考虑合法切割的每个末端点的prexor值肯定都是集合的子集异或值，子集总共只有32个，单次询问我们可以类似dijkstra的方式处理出每一个子集从开头开始凑出对应异或值并且存在合法拆分的最小长度，注意不能直接令d[0]=0，因为必须存在至少一个末端点，所以第一步也要枚举。假设当前是mask，则要找到在d[mask]之后第一个prexor值为 “mask对应xor值 xor 当前枚举的元素” 的地方去更新转移，最后只需要判断下d[全序列异或值]是否有值即可(若有值则肯定存在合法拆分)。至于多组询问，考虑dijkstra的瓶颈在于如何找出x之后第一个prexor为y的位置，我们用分块的方法就可以简单维护了。

 * K：容斥，f[i][0/1]代表强制经过了偶/奇条公共边的方案数，dp即可。
== 补题 ==

流水账

开场各自看题，有人过E，讨论了一下，cjb上机写，发现有点问题，sub fix了一下做法，E1y35。yzc上机写B的莫队，wa了一发，对拍找不到错，后来sub猛然点醒需要特判0，B2y70。sub上机写K，许久wa了，发现问题，然后数组开小了又RE，K3y102。之后三个人讨论了许久H，中途cjb试图上机随机搞D，失败。yzc上机H1y138。三个人研究A，无果，sub表示会F，上机写F，失败，封榜后猛然想起可以FWT，想到可能的corner case，侥幸交wa了，改了double，wa，A3y276。

总结

chenjb

菜菜，A应该早想到的。

oipotato

subconscious

题解

A：FWT，为了避免被出题人卡mod数，换一个mod数就好。
B：答案显然为区间里每一种出现次数/2并向上取整之和，特判0，莫队即可。
C：写一个函数，每次传入一个k，用o(n)的时间返回k的答案，当k<=sqrt(n)，直接暴力做，否则显然k的答案不会比n/k大，那么对于大于sqrt(n)的k，答案显然不会超过sqrt(n)，所以对于所有这些k，答案变化次数不会超过sqrt(n)，于是进行sqrt(n)次二分，找到每一种答案对应的k的区间即可，实现的时候直接在dfs序上逆序做即可，同时可以用整体二分减少常数。
D：n大的时候答案肯定是0，我们考虑n<=13(14)的时候直接做，n>13(14)的时候直接让后面的男女生一一对应，算出一个和0差的数字，前面的13(14)的数字肯定能凑出一个让答案为0的数字，就对前13(14)个男女生找这个值就好了。对于这十几个男生女生，找的时候我们考虑折半，先P(magic,magic/2)枚举前一半女生和前一半男生匹配，让剩余一半女生和后一半男生匹配，对于每一半女生直接枚举全排列(magic/2)!，然后塞进set里，直接find所需要的数值就好了。n<=13(14)的时候也是类似的折半做法，在set里lower_bound(mod-x)，如果找不到就取set.begin()。
E：首先统计点相邻边边权为奇数的个数，同时还需要判断该点相邻最大边权的两倍大于邻边权之和，此时要取最大边圈两倍减去邻边权之和，最后答案除以2。
F：f代表当前状态前至少需要经过多少轮当前的那个人才能判断自己的rank（注意这个值可以是非法的），tl代表当前状态前至少需要经过多少轮才非法（之前已经有人报出自己rank），ans可由f推出。
G：block将点分为了很多横棒和竖棒，显然同一棒子上的答案一样。假如两个棒子有交叉点，则连一条边，然后bfs即可得到每个点两个方向上的最小答案。由于边数过多，考虑用线段树优化建图，又因为不同的列的棒子编号不同，于是考虑用主席树来维护建图，两个方向各做一遍之后就得到每个点光线以两种方向来到这个点的最小步数之和。不难发现，每个点的两个答案是恰好差1的，于是我们现在的总和sum=2*ans+光线能到的点数。于是同时维护哪些点能到即可推出答案。注意边权有0，1时bfs需特殊处理，或者直接使用最短路算法。
H：从轻的往重的连边，每个点最长链加起来。
I：行上环长为x，列上环长为y可获得gcd(x,y)个置换环，枚举较小维的拆分数，组合数可得方案数，对于较大维，f[i]代表较大维长度为i时的答案，枚举环长组合数dp即可，O(n²*partition(m))。
J：因为集合大小只有5，考虑合法切割的每个末端点的prexor值肯定都是集合的子集异或值，子集总共只有32个，单次询问我们可以类似dijkstra的方式处理出每一个子集从开头开始凑出对应异或值并且存在合法拆分的最小长度，注意不能直接令d[0]=0，因为必须存在至少一个末端点，所以第一步也要枚举。假设当前是mask，则要找到在d[mask]之后第一个prexor值为 “mask对应xor值 xor 当前枚举的元素” 的地方去更新转移，最后只需要判断下d[全序列异或值]是否有值即可(若有值则肯定存在合法拆分)。至于多组询问，考虑dijkstra的瓶颈在于如何找出x之后第一个prexor为y的位置，我们用分块的方法就可以简单维护了。
K：容斥，f[i][0/1]代表强制经过了偶/奇条公共边的方案数，dp即可。

补题

附加文件

180329.en.pdf by chenjb
1.png by chenjb
Contest_Analysis_29032018.pdf by chenjb