写洛谷题
被洛谷题爆切
上午听课写了P2168和P2827
P2168
没什么好说的，Huffman树模板题，二叉堆动态维护最小值即可
P2827
这题挺有意思的，乍一看我觉得应该是暴力模拟，实际上暴力模拟
最重要的部分应该是对于切出的蚯蚓满足单调性的证明
C1:维护的是 \(\left \lfloor px \right \rfloor\) 显然是满足单调性的
C2:维护的是 \(x - \left \lfloor px \right \rfloor\)
只需令 \(x \ge y\)
显然有 \(x - y \ge p(x-y)\)
移项 \(x + px - y \ge px\)
自然有 \(\left \lfloor py + (x - y) \right \rfloor \ge \left \lfloor px \right \rfloor\)
由于 \(x,y \in \mathbb{Z}\)
则 \(\left \lfloor py \right \rfloor + x - y \ge \left \lfloor px \right \rfloor\)
移项自然得出 \(x - \left \lfloor px \right \rfloor \ge y - \left \lfloor py \right \rfloor\)
单调性得证
然后维护三个队列按顺序输出即可
下午打RiOI
得了100+100+1+20=221pts，rk45，第一次排进第一页，有点激动
T1
按2升幂输出即可
T2
基环树，处理环即可
T3
概率dp，不会，骗了1pt
T4
神奇构造打了个 \(O(n^2logn)\) 的暴力二分跑路
晚上被@slr切
莫名其妙MLE，明天接着调
标签：lfloor,right,px,rfloor,20230115,ge,left From： https://www.cnblogs.com/cxz-stO/p/17054203.html