2017-Sp216-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb读了E丢给sub，然后想F。之后有人过B，和sub确认了做法，cjb上机'''B1y28'''。yzc和sub推D，然后上机写D，'''D1y66'''。cjb决定上机乱搞G，让yzc暴搜搜出了规律，之后贪心了一下'''G1y95'''。sub上机写H，'''H1y99'''。然后sub继续写E，cjb和yzc开了A和I。sub挖了之后cjb上机写树剖，之后sub '''E2y124'''。yzc上机写I，'''I1y132'''。sub上机写F，cjb和yzc开出了J，抽空上机写了一下'''J1y168'''。sub F比较踉跄，wa了之后查了很久，yzc上机写A，也wa了。抽空sub推了C的式子，最后F终于'''F3y273'''。yzc的A拍了之后变成了tle，很难受，sub写的C wa12。直到赛后终于过了C，A一直在tle，因为复杂度都是线性的，感觉被卡常卡得很憋屈。
== 总结 ==
=== chenjb ===
前面还不错，可惜sub的F题拖沓了，A这个tle太伤了，感觉最近常数老出问题？C大概还需要多10min左右，但是这个corner case似乎需要更多点时间去发现。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：i向p[i]连边后环套树森林dp，注意自环、重边，还有常数。

 * B：相邻连边，跑tarjan。

 * C：特判最后一段，n<k不可能，n>=2k-1全是，其他情况每个k都会有1次贡献，k和p的lcm又会有一次贡献。特判任何一个数为0的特殊情况。

 * D：f[len][rest]=Σ(0<=i<=rest)C(i,rest)*(n-i)^len^/len!，二分。

 * E：在凸包上转。

 * F：状压dp，注意爆数组。

 * G：当层数>50的时候直接每次取最大的人放置，<=50直接暴力记忆化搜索。

 * H：枚举最左下的点，顺时针的第一个向量的gcd，设为(a,b)，边长设为(x,y)，直接枚举，复杂度是对的。

 * I：动态链分治裸题(nmd一个树链剖分维护毛毛虫没了)。

 * J：对于区间(l,r)，维护最小步数的情况下再维护最大的冗余，显然具有偏序，则可以直接转移到(l,r+1)和(l-1,r)，滚动数组控制内存。

 * K：取出所有线段，发现横纵相交只会有双方都是线段端点的情况。取出所有端点set去重，横横和纵纵排序去重即可。

流水账

出门各自看题，cjb读了E丢给sub，然后想F。之后有人过B，和sub确认了做法，cjb上机B1y28。yzc和sub推D，然后上机写D，D1y66。cjb决定上机乱搞G，让yzc暴搜搜出了规律，之后贪心了一下G1y95。sub上机写H，H1y99。然后sub继续写E，cjb和yzc开了A和I。sub挖了之后cjb上机写树剖，之后sub E2y124。yzc上机写I，I1y132。sub上机写F，cjb和yzc开出了J，抽空上机写了一下J1y168。sub F比较踉跄，wa了之后查了很久，yzc上机写A，也wa了。抽空sub推了C的式子，最后F终于F3y273。yzc的A拍了之后变成了tle，很难受，sub写的C wa12。直到赛后终于过了C，A一直在tle，因为复杂度都是线性的，感觉被卡常卡得很憋屈。

总结

chenjb

前面还不错，可惜sub的F题拖沓了，A这个tle太伤了，感觉最近常数老出问题？C大概还需要多10min左右，但是这个corner case似乎需要更多点时间去发现。

oipotato

subconscious

题解

  • A：i向p[i]连边后环套树森林dp，注意自环、重边，还有常数。
  • B：相邻连边，跑tarjan。
  • C：特判最后一段，n=2k-1全是，其他情况每个k都会有1次贡献，k和p的lcm又会有一次贡献。特判任何一个数为0的特殊情况。
  • D：f[len][rest]=Σ(0<=i<=rest)C(i,rest)*(n-i)len/len!，二分。
  • E：在凸包上转。
  • F：状压dp，注意爆数组。
  • G：当层数>50的时候直接每次取最大的人放置，<=50直接暴力记忆化搜索。
  • H：枚举最左下的点，顺时针的第一个向量的gcd，设为(a,b)，边长设为(x,y)，直接枚举，复杂度是对的。
  • I：动态链分治裸题(nmd一个树链剖分维护毛毛虫没了)。
  • J：对于区间(l,r)，维护最小步数的情况下再维护最大的冗余，显然具有偏序，则可以直接转移到(l,r+1)和(l-1,r)，滚动数组控制内存。
  • K：取出所有线段，发现横纵相交只会有双方都是线段端点的情况。取出所有端点set去重，横横和纵纵排序去重即可。
附加文件