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: ?

:D 加油吧!