2017-Sp106-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc迅速上机'''D1y6'''，之后F也是签到题，'''F2y27'''，cjb上机写B，'''B1y44'''。cjb和sub开出了A，丢给yzc，'''A2y72'''。cjb想出了I，上机获得wa，和yzc一起看了看发现是数字算错了囧，'''I3y92'''。sub终于想好了H，上机'''H1y120'''。cjb想了个结论丢给yzc写L，'''L1y149'''。sub和yzc开出了K，yzc上机wa了之后sub上机调边界，'''K2y215'''。cjb之前上机敲了闵可夫斯基和的板子，sub上机调G，wa了之后对拍找了错误，'''G2y270'''。最后迭代rush J，在mle和tle和wa的边缘试探，未能通过，cjb和yzc假装口胡出了B。
== 总结 ==
=== chenjb ===
打得还行，感觉C和J都是再给时间也能出的题。看到今天踩了一堆final队，心里还是有点小难过....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：multiset，只维护前100个值对答案贡献，暴力即可。

 * B：处理出a>b的关系建图，判是否有环。

 * C：首先折半，然后枚举左半边的余数，右半边余数也确定了，对于每一边余数p，直接暴力枚举k*m+p，然后用builtin_popcount来统计，因为枚举余数不超过m，然后下一层枚举的效率是sqrt(1e15)/m*builtin_popcount，所以乘起来效率应该是sqrt(1e15)*builtin_popcount，2秒多就能跑掉大点。

 * D：two-pointer。

 * E：cjb

 * F：模拟

 * G：分治，闵可夫斯基和求最远距离。

 * H：f[i][j]=min(a[k]+max(f[i][k-1],f[k+1][j]))，树状数组维护两边最小值即可。

 * I：最大权闭合子图。

 * J：sub

 * K：理解为从大到小插入到序列中，将插入两个端点视为同一个操作，最后乘上组合数即可。

 * L：只要保证每条边只走2次就一定最优(dfs序)，换根dp。
== 补题 ==

流水账

开场各自看题，yzc迅速上机D1y6，之后F也是签到题，F2y27，cjb上机写B，B1y44。cjb和sub开出了A，丢给yzc，A2y72。cjb想出了I，上机获得wa，和yzc一起看了看发现是数字算错了囧，I3y92。sub终于想好了H，上机H1y120。cjb想了个结论丢给yzc写L，L1y149。sub和yzc开出了K，yzc上机wa了之后sub上机调边界，K2y215。cjb之前上机敲了闵可夫斯基和的板子，sub上机调G，wa了之后对拍找了错误，G2y270。最后迭代rush J，在mle和tle和wa的边缘试探，未能通过，cjb和yzc假装口胡出了B。

总结

chenjb

打得还行，感觉C和J都是再给时间也能出的题。看到今天踩了一堆final队，心里还是有点小难过....

oipotato

subconscious

题解

• A：multiset，只维护前100个值对答案贡献，暴力即可。
• B：处理出a>b的关系建图，判是否有环。
• C：首先折半，然后枚举左半边的余数，右半边余数也确定了，对于每一边余数p，直接暴力枚举k*m+p，然后用builtin_popcount来统计，因为枚举余数不超过m，然后下一层枚举的效率是sqrt(1e15)/m*builtin_popcount，所以乘起来效率应该是sqrt(1e15)*builtin_popcount，2秒多就能跑掉大点。
• D：two-pointer。
• E：cjb
• F：模拟
• G：分治，闵可夫斯基和求最远距离。
• H：f[i][j]=min(a[k]+max(f[i][k-1],f[k+1][j]))，树状数组维护两边最小值即可。
• I：最大权闭合子图。
• J：sub
• K：理解为从大到小插入到序列中，将插入两个端点视为同一个操作，最后乘上组合数即可。
• L：只要保证每条边只走2次就一定最优(dfs序)，换根dp。

补题

附加文件

• 1.png by chenjb