2019-team11/summary-190812

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
opentrain临时出锅换上的一套陈题，风格略毒。虽说大家都爆炸，但做得也并不是很好，很多时间都耗在A上了。能做的D一开始否掉了。策略失当+1。
A从头卡到尾，开始在瞎找规律没有注意到这就是个nimm game，后来kc发现这是个nimm game然后ln盯着式子发呆kc盯着一些数据思考，我们可能想到了数位dp但自己不会也没有跟xtx说（他在专心调Bing）。经验太不足了。
开头感觉这些题目都不太好做，发呆了40min发现I好多队都做出来了那就开I吧。排个序瞎搞一下就做好了，虽然开得有些慢，但幸亏没有WA。59min。
接着继续跟榜，看G也是一万支队伍都搞出来了就跟着看。一开始不知道求最大团是个NP问题可解决的规模只有n=50这个量级于是ln和kc怀疑自己读了假题，反复读反复读，直到看到板子上那个n=50才明白这题就是这个意思……然后想了个贪心的做法，感觉对，就交给xtx了。码完交上去无限running，发现已经封榜了……这个时候挺欢乐的。
榜解封后发现WA掉了，然后kc发现这题是个智商题有巧解，于是过了。1h58min+2。
之后xtx和kc看E，想着想着发现求个树的重心就好了，然后xtx边看板边理解就过了。3h25min。
之后xtx开看B，想了个匹配的做法，但因为对Hungary算法的理解还不深赛场上就没调出来，赛后调出来了。
A一直想一直不知道怎么写，而交了的队伍基本都很快过的。失败。F也是猛看但越看越感觉自己ds辣鸡得一批，主席树还不怎么会，整体二分也没学过，ln太菜了。
D题kc开局的时候看了一下然后ln提出可以倒着做卡时卡一卡，然后xtx提出边的松弛要做好多次卡不过去的。两个没看过题的就这样口胡出正确答案然后又把正解否掉了，赛后发现D能秒过，hhhh。
== 个人总结 ==
ln：加强合作能力，不能看到B有匹配就慌，本来可能可以帮到忙的。还有图论又该补补了，不能看到就怕。
xtx：不管怎么样，题一定要看。D 一开始以为要维护任意点到点最短路所以没看，结束后才发现只要维护固定起点就秒掉了。对算法还是要理解，不能光会套板子题。
== 补题 ==
A：转化为 Nim 游戏，对于某个位置是否必败的充要条件是 (x-1) xor (n-x) xor (y-1) xor (m-y)=0，转化为 (x-1) xor (n-x) = (y-1) xor (m-y)，对 x,y 数对求和，然后不会了。
B：首先可以把时间内可做的最大题数算出来，然后每层题数把选手当另一个人一起跑匈牙利算法并根据能否增广添加对罚时和答案的贡献，最后把前做出的题数个有匹配的人输出就行了。最后几个剪枝：这一层做不出题的选手以后都直接跳过不增广，题已经做完了直接结束。
C：
D：倒着做就变成加边更新最短路了。把边删完跑一遍 dijkstra ，接着每次加边判断是否会更新 dis，会更新就加入队列，类似松弛操作。
E：根据树的重心的性质，只有重心有解。O(n) 求出重心的最大子树大小，然后对于每个最大子树大小等于重心的最大子树大小的点求答案，这个点之多两个。求答案时直接深搜求出每条边对答案的贡献乘二减去最远点的距离，需要特判最远点所在子树是否有限制条件。
F：整体二分例题，同时二分答案的区间和每种询问所在的区间。
G：建补图，每次任删一边，最后剩下的若干点中必有至少n/3个在一直的团上。
H：
I：同时枚举每种颜色的最长stick，然后如果答案没出来就让最长的往前跑。
J：

流水账

opentrain临时出锅换上的一套陈题，风格略毒。虽说大家都爆炸，但做得也并不是很好，很多时间都耗在A上了。能做的D一开始否掉了。策略失当+1。

A从头卡到尾，开始在瞎找规律没有注意到这就是个nimm game，后来kc发现这是个nimm game然后ln盯着式子发呆kc盯着一些数据思考，我们可能想到了数位dp但自己不会也没有跟xtx说（他在专心调Bing）。经验太不足了。

开头感觉这些题目都不太好做，发呆了40min发现I好多队都做出来了那就开I吧。排个序瞎搞一下就做好了，虽然开得有些慢，但幸亏没有WA。59min。

接着继续跟榜，看G也是一万支队伍都搞出来了就跟着看。一开始不知道求最大团是个NP问题可解决的规模只有n=50这个量级于是ln和kc怀疑自己读了假题，反复读反复读，直到看到板子上那个n=50才明白这题就是这个意思……然后想了个贪心的做法，感觉对，就交给xtx了。码完交上去无限running，发现已经封榜了……这个时候挺欢乐的。

榜解封后发现WA掉了，然后kc发现这题是个智商题有巧解，于是过了。1h58min+2。

之后xtx和kc看E，想着想着发现求个树的重心就好了，然后xtx边看板边理解就过了。3h25min。

之后xtx开看B，想了个匹配的做法，但因为对Hungary算法的理解还不深赛场上就没调出来，赛后调出来了。

A一直想一直不知道怎么写，而交了的队伍基本都很快过的。失败。F也是猛看但越看越感觉自己ds辣鸡得一批，主席树还不怎么会，整体二分也没学过，ln太菜了。

D题kc开局的时候看了一下然后ln提出可以倒着做卡时卡一卡，然后xtx提出边的松弛要做好多次卡不过去的。两个没看过题的就这样口胡出正确答案然后又把正解否掉了，赛后发现D能秒过，hhhh。

个人总结

ln：加强合作能力，不能看到B有匹配就慌，本来可能可以帮到忙的。还有图论又该补补了，不能看到就怕。

xtx：不管怎么样，题一定要看。D 一开始以为要维护任意点到点最短路所以没看，结束后才发现只要维护固定起点就秒掉了。对算法还是要理解，不能光会套板子题。

补题

A：转化为 Nim 游戏，对于某个位置是否必败的充要条件是 (x-1) xor (n-x) xor (y-1) xor (m-y)=0，转化为 (x-1) xor (n-x) = (y-1) xor (m-y)，对 x,y 数对求和，然后不会了。

B：首先可以把时间内可做的最大题数算出来，然后每层题数把选手当另一个人一起跑匈牙利算法并根据能否增广添加对罚时和答案的贡献，最后把前做出的题数个有匹配的人输出就行了。最后几个剪枝：这一层做不出题的选手以后都直接跳过不增广，题已经做完了直接结束。

C：

D：倒着做就变成加边更新最短路了。把边删完跑一遍 dijkstra ，接着每次加边判断是否会更新 dis，会更新就加入队列，类似松弛操作。

E：根据树的重心的性质，只有重心有解。O(n) 求出重心的最大子树大小，然后对于每个最大子树大小等于重心的最大子树大小的点求答案，这个点之多两个。求答案时直接深搜求出每条边对答案的贡献乘二减去最远点的距离，需要特判最远点所在子树是否有限制条件。

F：整体二分例题，同时二分答案的区间和每种询问所在的区间。

G：建补图，每次任删一边，最后剩下的若干点中必有至少n/3个在一直的团上。

H：

I：同时枚举每种颜色的最长stick，然后如果答案没出来就让最长的往前跑。

J：