2017-Sp116-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
开场各自看题，sub表示自己能秒J，然后wa了。cjb读了H，被yzc抢了，'''H1y20'''。之后sub怀疑是读入错，改了又wa了，cjb上机写E，wa了。之后sub终于改对，'''J4y51'''。cjb上机'''E2y58'''。yzc上机写B，mle后写了离散化，'''B2y93'''。cjb上机随意秒了F，'''F1y112'''。sub上机写D，cjb读了G，感觉是板子几何题，和sub说了一下，成功换成了更短的板子，'''G1y145'''，之后'''D1y162'''，yzc上机写A，wa了之后sub上机写I，都遇到了问题，之后一起艹A，'''A2y230'''。最后三个人一起攻I，艰难从tle变成wa，疯狂提交无果，赛后发现sub爆了long long*long long，修改后通过。
== 总结 ==
=== chenjb ===
最后的long long * long long太可惜了，感觉今天的题有几个old模型，基本在做法上没遇到什么太大问题，一切顺利的话应该要努力全部过掉。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：f[i]表示i子树的最深深度，改一个点的权值只会影响log个点的f值，然后每个节点答案只需要从他遍历到根就可以得到，用map存状态即可。

 * B：主席树。

 * C：每次大力极角序扫描线即可。对于跨过初始位置的墙区间，分成两个区间即可。注意精度。

 * D：次数不多，模拟即可。

 * E：tarjan后在dag上拓扑排序，队列里出现超过1个点就FFF。

 * F：枚举答案中两点不同的二进制位，分成两个点集，跑dijkstra。

 * G：二分答案，最小圆覆盖判断是否可行即可。

 * H：排序，从小取到大，取一个就把他会产生的数字删掉。

 * I：当k大于1e6时直接特判输出0或k，小于时f[i][j]表示1到i中被前1到j个素数筛到后的答案，f[i][j]=f[i-1][j]-p[i]*f[i-1][j/p[i]]，记忆化搜索即可。

 * J：最长公共子序列dp，注意'.'要先匹配具体字符，之后才能复制。

 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-9-solutions-by-北京邮电大学/  Official]

流水账

开场各自看题，sub表示自己能秒J，然后wa了。cjb读了H，被yzc抢了，H1y20。之后sub怀疑是读入错，改了又wa了，cjb上机写E，wa了。之后sub终于改对，J4y51。cjb上机E2y58。yzc上机写B，mle后写了离散化，B2y93。cjb上机随意秒了F，F1y112。sub上机写D，cjb读了G，感觉是板子几何题，和sub说了一下，成功换成了更短的板子，G1y145，之后D1y162，yzc上机写A，wa了之后sub上机写I，都遇到了问题，之后一起艹A，A2y230。最后三个人一起攻I，艰难从tle变成wa，疯狂提交无果，赛后发现sub爆了long long*long long，修改后通过。

总结

chenjb

最后的long long * long long太可惜了，感觉今天的题有几个old模型，基本在做法上没遇到什么太大问题，一切顺利的话应该要努力全部过掉。

oipotato

subconscious

题解

• A：f[i]表示i子树的最深深度，改一个点的权值只会影响log个点的f值，然后每个节点答案只需要从他遍历到根就可以得到，用map存状态即可。
• B：主席树。
• C：每次大力极角序扫描线即可。对于跨过初始位置的墙区间，分成两个区间即可。注意精度。
• D：次数不多，模拟即可。
• E：tarjan后在dag上拓扑排序，队列里出现超过1个点就FFF。
• F：枚举答案中两点不同的二进制位，分成两个点集，跑dijkstra。
• G：二分答案，最小圆覆盖判断是否可行即可。
• H：排序，从小取到大，取一个就把他会产生的数字删掉。
• I：当k大于1e6时直接特判输出0或k，小于时f[i][j]表示1到i中被前1到j个素数筛到后的答案，f[i][j]=f[i-1][j]-p[i]*f[i-1][j/p[i]]，记忆化搜索即可。
• J：最长公共子序列dp，注意'.'要先匹配具体字符，之后才能复制。
• Official