2019 多校(MUTC) Diary Round 3

大家好，又与大家见面了！我是差点爆0的syr。
今天的多校又是一个三人线上交流的round，我在世贸，那就多讲一些世贸打比赛的体验吧。

比赛环境

比赛来到现场的有：(hyh, ycs, jt) (sy, wsr, myf) (wjy, whr, hsc,cxw) (zrm, hqg, xxx)……这些都不重要了
当然还有(syr, , )。
比赛之前还看到了神仙qty和hhr，hhr以一种奇怪的委婉语气问我：“今天下午这里是不是会有很多年轻的小朋友来？”
我一开始摸不着头脑，片刻之后就反应过来，告诉他：“我想下午会比较吵。”

Problems’ First Look

像round1一样，开题的顺序是：
syr 1001～1004
xgn 1005～1008
Monkey King 1009～1012
syr看到1002之后立刻被深深地吸引了……
而xgn迅速锁定1007，与Monkey King一番讨论之后决定由Monkey King开始写

Problem 1007

做法：将权值排序之后用两棵BIT维护，然后二分地寻找。
Monkey King一番调试之后于00:48迅速AC
而此时钢筋们也在00:46通过了1002

Problem 1006

在现场做题的一个好处就是可以跨组交流
没有的事。syr只是听到现场过1006的人比较多，还有人炫耀用暴力AC，所以向xgn汇报了这一情况。
xgn在先尝试了OEIS之后又尝试了暴力，于是有了
做法：暴力地枚举P之前的数，用Miller Rabin算法判断是否是质数
复杂度：O(min(玄学，∞))
一番coding之后“果不其然”TLE了
这时syr提议枚举Q的时候每次-2而非-1，这当然非常傻，于是还是TLE
在xgn下次提交之前他猛然发现要用__int128（1e14 * 1e14会爆ll）
于是就AC了！

Problem 1002

接下来我们果断跟（跳）榜（坑）
在对钢筋的做法进行了一番揣测之后，syr提出了一个真实的
做法：构建一棵dfs树，把出度为0的点全部连向一个新的节点作根。那么一个节点u的能到达的最近的到根路径唯一的点是它所有出度的这个值的LCA。用dp维护这个值，询问的时候找到两个节点的这个值，那么它们到根的一条路径上的所有点都能被算作答案，防止算重，再减去LCA的深度即可
syr迅速代码，果断WA了。
经过一番对拍仔细而认真的检查与分析，syr光荣地假掉了。
原因：一个节点成为割点不一定要到根路径唯一。

Problem 1009

而此时xgn与monkey king的1009也WA了很多发。我不太清楚做法，但知道是
做法：贪心

Problem 1004

此时比赛时间所剩无多，见另外的team都AC了1004，我们迅速集中到1004上。一开始我们觉得负权非常讨厌（废话如果全是正的不就成傻逼题了吗，因此只知道二分不知道如何check
这时monkey king提出了决定性的意见：

dp[i]表示在mid的条件下前i个最多可以割成几段

然后Monkey King试图排序，但我觉得不用
做法：二分，dp，线段树维护，前缀和作下标，单点修改，区间查询
为此syr特地求证了hyh：

syr：1004的做法里有贪心吗？
hyh：没有
syr：1004的做法里有dp吗？
hyh：太强了

这时比赛时间还有1h，syr提议三人各自开始写
当syr调完时还剩30min，信仰一交取得了WA的好成绩
xgn开始帮syr调，syr各种魔改然而还是WA，其中syr觉得会不会不允许文末回车，于是就改了
还剩15min时syr开始闭眼瞎调：
数据
10 3
1 2 3 4 5 6 7 8 9 10
输出非常正确
10 3
10 9 8 7 6 5 4 3 2 1
输出：
9
？？？！！！
最后发现是前缀和0没有放进离散化。
信仰一交：PE！
迅速反应过来是文末回车，改一发：
16：55AC！
不过就算绝杀了我们也只是达到了大众题数而已

总结

其他队伍：大众3个，lxr4个
这次和前两个Round比起来团队合作效果眀显，我个人觉得瓶颈在于不会做，我感觉如果当面讨论效果更好（但是两位队友果断拒绝了我的提议）
目前为止我们的Performance：
Round 1: 1
Round 2: 2
Round 3: 3
Round 4: ?
😀 加油吧！