2017-Sp43-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc判断B是签到题，和sub讲了讲，然后cjb上机敲了线性筛，sub发现没有那么简单，上机调试起了积性函数。cjb和yzc发现G很多人过，讨论起了G，讨论了一段时间后yzc上机写G，'''G1y28'''. cjb发现K也很多人过，而且过得飞快，感觉100000个点用网络流跑跑应该没问题。cjb上机写K，wa了一发后tle了。cjb写K的时候yzc和sub讨论了I，yzc上机写I，之后'''I1y78'''. 此前cjb提出K应该是个简单dp，I过后cjb上机写K，Kwa了两发后过了，'''K5y101'''. yzc和sub讨论了D，K过了之后yzc上机写D，'''D1y114'''. 接下来时间sub继续调B，cjb和yzc脑补了A的做法。cjb上机写点分治，过了样例后wa了。下机思考的sub上机写J，写了三行'''J1y199'''. 三个人一起讨论A，yzc上机写了各种测试程序，计算了wa的ratio。最后耗了很久，终于加特技加出一个wa ratio很低的程序，提交获得tle，反复调参后终于'''A9y278'''。剩下时间三个人一起尝试B，但是没能找到正确的赋值，6题结束了比赛。
== 总结 ==
=== chenjb ===
emmm今天犯了好多小错误，以后开inf的时候一定要特别注意答案或者过程中会不会真的达到这个值，尤其是max，min或者上下界费用流的时候尤其要小心。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：将树的两个重心找到，然后判断一下是否满足每个子树都<=size/2即可。（by机智的Tsr)
 * A：考虑如果能找到T，使得T的点分治树是读入的树A，则T是Centroid。但是直接对A跑点分治树判相同是不对的，考虑随机扰动一下，在寻找重心时，如果遇到一个点x也和当前的root有相同的max_son_size，那么我们在原树中判一判是否存在这样一条边，然后随机一下把root赋值为x，然后重复几次会获得比较优秀的ratio，但是小心会tle，我们最后取了rep=10卡了过去。(by 愚蠢的Legilimens)
 * B：只需要考虑如何给质数的ans函数赋值，最后对mod 3==1的质数置为1，别的置为-1就可以了，理由待证。
 * K：dp一下，f[i][0]和f[i][1]分别表示子树里只保留0或者1的最小代价，注意inf一定要开足够。
== 补题 ==

流水账

开场各自看题，yzc判断B是签到题，和sub讲了讲，然后cjb上机敲了线性筛，sub发现没有那么简单，上机调试起了积性函数。cjb和yzc发现G很多人过，讨论起了G，讨论了一段时间后yzc上机写G，G1y28. cjb发现K也很多人过，而且过得飞快，感觉100000个点用网络流跑跑应该没问题。cjb上机写K，wa了一发后tle了。cjb写K的时候yzc和sub讨论了I，yzc上机写I，之后I1y78. 此前cjb提出K应该是个简单dp，I过后cjb上机写K，Kwa了两发后过了，K5y101. yzc和sub讨论了D，K过了之后yzc上机写D，D1y114. 接下来时间sub继续调B，cjb和yzc脑补了A的做法。cjb上机写点分治，过了样例后wa了。下机思考的sub上机写J，写了三行J1y199. 三个人一起讨论A，yzc上机写了各种测试程序，计算了wa的ratio。最后耗了很久，终于加特技加出一个wa ratio很低的程序，提交获得tle，反复调参后终于A9y278。剩下时间三个人一起尝试B，但是没能找到正确的赋值，6题结束了比赛。

总结

chenjb

emmm今天犯了好多小错误，以后开inf的时候一定要特别注意答案或者过程中会不会真的达到这个值，尤其是max，min或者上下界费用流的时候尤其要小心。

oipotato

subconscious

题解

  • A：将树的两个重心找到，然后判断一下是否满足每个子树都<=size/2即可。（by机智的Tsr)
  • A：考虑如果能找到T，使得T的点分治树是读入的树A，则T是Centroid。但是直接对A跑点分治树判相同是不对的，考虑随机扰动一下，在寻找重心时，如果遇到一个点x也和当前的root有相同的max_son_size，那么我们在原树中判一判是否存在这样一条边，然后随机一下把root赋值为x，然后重复几次会获得比较优秀的ratio，但是小心会tle，我们最后取了rep=10卡了过去。(by 愚蠢的Legilimens)
  • B：只需要考虑如何给质数的ans函数赋值，最后对mod 3==1的质数置为1，别的置为-1就可以了，理由待证。
  • K：dp一下，f[i][0]和f[i][1]分别表示子树里只保留0或者1的最小代价，注意inf一定要开足够。

补题

附加文件