2017-Sp114-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
剩下polya和物理不会做，十分痛楚。
== 总结 ==
=== chenjb ===
KM原来是有用的啊...
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：把1号边缩掉，在ac自动机上跑dp。

 * B：f[i][j]表示有i个棒子，j个圆环的最小步数，f[i][j]=min(f[i][k]*2+f[i-1][j-k])，打印过程十分疼痛。

 * C：O(n)合并果子，搞一下单调性。

 * D：如果确定了中间点的位置，可以先尝试45度角起跳，会碰到柱子时进行调整，可以得到所需要的最小初速度。随后三分中间点位置即可。

 * E：dp,f[i][j]表示目前考虑到第i个人且上一个人选择了第j个的最小值，dp即可。

 * F：考虑生成树上的边的修改值d是变小，反之是变大，则对于一条非树边j，两点路径上任意一条边i都要满足c[i]-d[i]<=c[j]+d[j]，移项得d[i]+d[j]>=c[i]-c[j]，把树边和非树边当做二分图的两边，根据KM算法的性质，可以等价于使用KM算法求出图上最大权匹配后头上的下标。

 * G：贪心，先让每个人取到下限，然后对每个人处理出金钱加1后对答案的贡献，排序后从大到小取完。

 * H：polya定理，有两种置换，一种是shift，另一种是旋转，n=m时可以旋转90度，否则180度，大力跑出所有置换，polya上大整数即可。

 * [http://blog.watashi.ws/816/andrew-stankevich-2-solution/ Watashi]

流水账

剩下polya和物理不会做，十分痛楚。

总结

chenjb

KM原来是有用的啊...

oipotato

subconscious

题解

• A：把1号边缩掉，在ac自动机上跑dp。
• B：f[i][j]表示有i个棒子，j个圆环的最小步数，f[i][j]=min(f[i][k]*2+f[i-1][j-k])，打印过程十分疼痛。
• C：O(n)合并果子，搞一下单调性。
• D：如果确定了中间点的位置，可以先尝试45度角起跳，会碰到柱子时进行调整，可以得到所需要的最小初速度。随后三分中间点位置即可。
• E：dp,f[i][j]表示目前考虑到第i个人且上一个人选择了第j个的最小值，dp即可。
• F：考虑生成树上的边的修改值d是变小，反之是变大，则对于一条非树边j，两点路径上任意一条边i都要满足c[i]-d[i]<=c[j]+d[j]，移项得d[i]+d[j]>=c[i]-c[j]，把树边和非树边当做二分图的两边，根据KM算法的性质，可以等价于使用KM算法求出图上最大权匹配后头上的下标。
• G：贪心，先让每个人取到下限，然后对每个人处理出金钱加1后对答案的贡献，排序后从大到小取完。
• H：polya定理，有两种置换，一种是shift，另一种是旋转，n=m时可以旋转90度，否则180度，大力跑出所有置换，polya上大整数即可。
• Watashi