2017-Sp221-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，波兰人英语写得比较诡异，阅读有巨大障碍，cjb上机'''F1y31'''，yzc上机'''G1y35'''，之后sub上机写J。cjb和yzc开A，之后'''J2y66'''。yzc上机写A，wa了一发后fix了一下还是wa，发现做法有问题。cjb和sub讨论E，上机'''E1y81'''。yzc和sub试图fix A，还是wa，对拍又发现做法还是有问题。cjb开出了H，上机写H，'''H1y138'''。yzc和sub终于fix好了A，'''A4y152'''。发现lyk过了B，cjb和sub开了一下，cjb上机'''B1y166'''，sub和yzc讨论C，yzc上机'''C1y206'''。之后yzc和cjb试图开D和K，sub上机试图艹I。D猜测应该不存在无解的情况，但胡乱贪心是不行的。K得到了一个分治+二维线段树，三个log也不能承受，而且很难写。sub的I发现不能贪心，搞不定。
== 总结 ==
=== chenjb ===
感觉A花的时间过久了，还好这次别的题比较轻量级，以后这种题还是谨慎上机，疯狂fix算法这种情况是很难受的，要尽量避免。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：悬线法，称到上面第一个点的距离为s1，到上面第二个点为s2。一种情况是当前点取的高度为s2，左右两边按原来悬线法方法做，另一种是当前点取s1，左右两端有一端取了s2，用树状数组维护下标最大值和次大值即可。

 * B：枚举第一步选哪个叶子填-2，然后直接把所有未确定的叶子忽略掉check即可。

 * C：维护所有可能组成某个2^i^的数字的形状，用所有点的相对位置来表示这个形状，最后得到的那个数字，会放在相对位置为(0,0)的位置。从2^i^到2^i+1^次，只需要枚举任意两种形状，和四种最终位置的相对关系，枚举发现只有当1,2,4,8,16的时候才存在这样的形状，并且方案数不会太多，对每个格子暴力枚举即可。

 * D：因为有偶数条边且连通，所以先对相邻边进行两两匹配，具体操作是在dfs树上先尽量把后继边两两匹配，否则和承父边匹配即可。匹配之后建出新图，在新图上，点的度数奇偶性不变，然后考虑一条从奇数点出发，奇数点结束的路径，头尾度数-1，否则度数-2，因此暴力走到不能走为止，剩下的图依然满足原先性质，而且未被匹配的奇数点至少有一条出边且图依然连通，重复过程即可成功构造。

 * E：从大到小处理，每次把>=当前要求房间值的灯泡全部加入栈中。然后对于每个房间，如果栈有元素，取栈顶来凑，顺便累计一个delta值进队列，代表可以操作的一个冗余值。如果栈无元素，则只能硬换一个该期望值的灯泡。之后通过判定这种情况的次数来判无解，之后贪心选择最优的k个冗余值更新答案即可。

 * F：把奇和偶分开排序，然后每次取最大值加入，如果不是偶数，考虑用当前考虑到的奇数和偶数来凑奇数。

 * G：等价于求最多可以盖几次，每一个位置可以盖的次数相当于它跟它后面第一个不一样的字母有多远，直接取min即可。

 * H：原本模型是最大权闭合子图，把所有宝藏先取，把覆盖区域坐标变换后，按x坐标逐渐加入事件，对于所有保安，不停暴力寻找当前能加入流的y最小的宝物填充，本质上就是模拟增广。这个复杂度真的对吗??? '''UPD:'''这复杂度对的，因为你考虑增广的过程，要不就会使得保安的流量被全部吃到了，要不就会使得一个宝物消失，所以均摊是正确的。

 * I：所有左右存在差值大于一的位置都视为断点，暴力枚举两个断点翻转。dfs过程中出现断点数量超过翻转次数四倍即退出。注意一上来断点超过6就不可能有解。

 * J：强制定根，每个点与其父亲作差，可以得到两倍子树减掉全局，再通过根节点头上的数，解方程即可得到全局，然后一个个计算即可。

 * K：考虑DP，f[i]表示前i个小朋友最多可以分成几组，转移显然。用分治优化转移，每次左边和右边分别计算能取到的另一边，左边按照能取到的右边的端点拆成添加和删除事件，用线段树维护即可。由于时限很紧，NB的卡常@jsb或者zkw线段树可以通过。

 * [https://icpc.camp/new-meta/2017/04/22%20Petrozavodsk%20Summer-2014.%20Warsaw%20U%20Contest New Meta]

流水账

出门各自看题，波兰人英语写得比较诡异，阅读有巨大障碍，cjb上机F1y31，yzc上机G1y35，之后sub上机写J。cjb和yzc开A，之后J2y66。yzc上机写A，wa了一发后fix了一下还是wa，发现做法有问题。cjb和sub讨论E，上机E1y81。yzc和sub试图fix A，还是wa，对拍又发现做法还是有问题。cjb开出了H，上机写H，H1y138。yzc和sub终于fix好了A，A4y152。发现lyk过了B，cjb和sub开了一下，cjb上机B1y166，sub和yzc讨论C，yzc上机C1y206。之后yzc和cjb试图开D和K，sub上机试图艹I。D猜测应该不存在无解的情况，但胡乱贪心是不行的。K得到了一个分治+二维线段树，三个log也不能承受，而且很难写。sub的I发现不能贪心，搞不定。

总结

chenjb

感觉A花的时间过久了，还好这次别的题比较轻量级，以后这种题还是谨慎上机，疯狂fix算法这种情况是很难受的，要尽量避免。

oipotato

subconscious

题解

A：悬线法，称到上面第一个点的距离为s1，到上面第二个点为s2。一种情况是当前点取的高度为s2，左右两边按原来悬线法方法做，另一种是当前点取s1，左右两端有一端取了s2，用树状数组维护下标最大值和次大值即可。
B：枚举第一步选哪个叶子填-2，然后直接把所有未确定的叶子忽略掉check即可。
C：维护所有可能组成某个2ⁱ的数字的形状，用所有点的相对位置来表示这个形状，最后得到的那个数字，会放在相对位置为(0,0)的位置。从2ⁱ到2ⁱ⁺¹次，只需要枚举任意两种形状，和四种最终位置的相对关系，枚举发现只有当1,2,4,8,16的时候才存在这样的形状，并且方案数不会太多，对每个格子暴力枚举即可。
D：因为有偶数条边且连通，所以先对相邻边进行两两匹配，具体操作是在dfs树上先尽量把后继边两两匹配，否则和承父边匹配即可。匹配之后建出新图，在新图上，点的度数奇偶性不变，然后考虑一条从奇数点出发，奇数点结束的路径，头尾度数-1，否则度数-2，因此暴力走到不能走为止，剩下的图依然满足原先性质，而且未被匹配的奇数点至少有一条出边且图依然连通，重复过程即可成功构造。
E：从大到小处理，每次把>=当前要求房间值的灯泡全部加入栈中。然后对于每个房间，如果栈有元素，取栈顶来凑，顺便累计一个delta值进队列，代表可以操作的一个冗余值。如果栈无元素，则只能硬换一个该期望值的灯泡。之后通过判定这种情况的次数来判无解，之后贪心选择最优的k个冗余值更新答案即可。
F：把奇和偶分开排序，然后每次取最大值加入，如果不是偶数，考虑用当前考虑到的奇数和偶数来凑奇数。
G：等价于求最多可以盖几次，每一个位置可以盖的次数相当于它跟它后面第一个不一样的字母有多远，直接取min即可。
H：原本模型是最大权闭合子图，把所有宝藏先取，把覆盖区域坐标变换后，按x坐标逐渐加入事件，对于所有保安，不停暴力寻找当前能加入流的y最小的宝物填充，本质上就是模拟增广。这个复杂度真的对吗??? UPD:这复杂度对的，因为你考虑增广的过程，要不就会使得保安的流量被全部吃到了，要不就会使得一个宝物消失，所以均摊是正确的。
I：所有左右存在差值大于一的位置都视为断点，暴力枚举两个断点翻转。dfs过程中出现断点数量超过翻转次数四倍即退出。注意一上来断点超过6就不可能有解。
J：强制定根，每个点与其父亲作差，可以得到两倍子树减掉全局，再通过根节点头上的数，解方程即可得到全局，然后一个个计算即可。
K：考虑DP，f[i]表示前i个小朋友最多可以分成几组，转移显然。用分治优化转移，每次左边和右边分别计算能取到的另一边，左边按照能取到的右边的端点拆成添加和删除事件，用线段树维护即可。由于时限很紧，NB的卡常@jsb或者zkw线段树可以通过。
New Meta

附加文件

1.png by chenjb