2017-Sp101-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，L有人过后sub上机写L，wa了之后发现ll出了问题，'''L2y38'''。cjb此前读到C后也打断了sub，上机写完C下机调整。之后C因为数组开小一位而PE，'''C2y55'''。yzc上机写E，wa了两发，sub帮忙调整，cjb提了个corner case发现居然错了，'''E3y65'''。sub上机写几何题G，'''G3y93'''。cjb开出了B，让yzc上机敲dij，cjb上机因为ll又wa了一发，'''B2y122'''。之后sub开出了K，上机'''K1y146'''。yzc在sub写K的时候和cjb把模拟题D的准备工作做好了，上机写D。cjb和sub讨论了A，yzc wa了一发后sub上机写A，'''A1y204'''。yzc之后wa了两发， 三个人讨论了逻辑问题，提出了corner case，最后'''D4y261'''。cjb在yzc写D的时候读完了所有题，但是都比较大，最后20min三个人讨论了F，无果，最后现场rk21。
== 总结 ==
=== chenjb ===
毒性很大，看起来很多题，实际上很可怕，7题就会爆炸，8题就是ave，9题才有牌，难想还需要多时间，确实很考验封榜策略，模拟题因为逻辑问题卡了很久，落后夜幕40分钟，但是他们也是最后10s才过第9题。另外今天dirt率非常高，三个人都犯了很多小错误，要提高警觉。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：每次取距离下界最小的糖吃，吃到1e6输出forever

 * B：预处理1~B的点到B+1再回来的最短路径f[i]，按此值排序，显然分组肯定是取连续的k个f[i]为一组，则贡献为Σf[i]*(k-1)，然后f[i][j]表示前i个人分成j组的最小值，显然随着f[i]增大，组大小不增，所以枚举到i/j就好了，效率为O(n^2^logn)。

 * C：暴力建树，暴力判同构。

 * D：模拟即可，搞清楚题目的逻辑。

 * E：不断二分调整。

 * F：按叶子节点深度从小到大枚举答案，一开始把dist[i]-dist[father[i]]加入堆，不停弹出不大于当前枚举的d[x]的路径，同时对于每个点维护其已弹出的后代中最浅值，如果有一个点p的所有后代都弹出了，那么只能选择后代最浅的一段加上dist[p]-dist[father[p]]加入堆中，每次堆中元素+1就是答案。

 * G：每次枚举一个点，另外一个点做极角序扫一遍统计答案。

 * H：'''????变态几何 sub'''

 * I：'''sub'''

 * J：'''????啥玩意儿啊 可能要问下claris'''

 * K：dp，f[i][j][0/1]代表当前到第i个引号，当前的左引号下降到了大小为j的，当前状态有没有触过单引号这个底是否可能，从大到小枚举答案即可。

 * L：a<b时按a从小到大排序，a>b的按b从大到小排序接在后面，模拟即可。

 * M：暴力调整寻找优先级，模拟即可。
== 补题 ==

流水账

开场各自看题，L有人过后sub上机写L，wa了之后发现ll出了问题，L2y38。cjb此前读到C后也打断了sub，上机写完C下机调整。之后C因为数组开小一位而PE，C2y55。yzc上机写E，wa了两发，sub帮忙调整，cjb提了个corner case发现居然错了，E3y65。sub上机写几何题G，G3y93。cjb开出了B，让yzc上机敲dij，cjb上机因为ll又wa了一发，B2y122。之后sub开出了K，上机K1y146。yzc在sub写K的时候和cjb把模拟题D的准备工作做好了，上机写D。cjb和sub讨论了A，yzc wa了一发后sub上机写A，A1y204。yzc之后wa了两发， 三个人讨论了逻辑问题，提出了corner case，最后D4y261。cjb在yzc写D的时候读完了所有题，但是都比较大，最后20min三个人讨论了F，无果，最后现场rk21。

总结

chenjb

毒性很大，看起来很多题，实际上很可怕，7题就会爆炸，8题就是ave，9题才有牌，难想还需要多时间，确实很考验封榜策略，模拟题因为逻辑问题卡了很久，落后夜幕40分钟，但是他们也是最后10s才过第9题。另外今天dirt率非常高，三个人都犯了很多小错误，要提高警觉。

oipotato

subconscious

题解

• A：每次取距离下界最小的糖吃，吃到1e6输出forever
• B：预处理1~B的点到B+1再回来的最短路径f[i]，按此值排序，显然分组肯定是取连续的k个f[i]为一组，则贡献为Σf[i]*(k-1)，然后f[i][j]表示前i个人分成j组的最小值，显然随着f[i]增大，组大小不增，所以枚举到i/j就好了，效率为O(n²logn)。
• C：暴力建树，暴力判同构。
• D：模拟即可，搞清楚题目的逻辑。
• E：不断二分调整。
• F：按叶子节点深度从小到大枚举答案，一开始把dist[i]-dist[father[i]]加入堆，不停弹出不大于当前枚举的d[x]的路径，同时对于每个点维护其已弹出的后代中最浅值，如果有一个点p的所有后代都弹出了，那么只能选择后代最浅的一段加上dist[p]-dist[father[p]]加入堆中，每次堆中元素+1就是答案。
• G：每次枚举一个点，另外一个点做极角序扫一遍统计答案。
• H：????变态几何 sub
• I：sub
• J：????啥玩意儿啊 可能要问下claris
• K：dp，f[i][j][0/1]代表当前到第i个引号，当前的左引号下降到了大小为j的，当前状态有没有触过单引号这个底是否可能，从大到小枚举答案即可。
• L：ab的按b从大到小排序接在后面，模拟即可。
• M：暴力调整寻找优先级，模拟即可。

补题

附加文件

• 1.png by chenjb