Timeline

07:40-08:00

看到 A 第一眼就秒了，写暴力 + 正解。

08:00-08:30

B 第一时间没想到什么好的做法，先把暴力打了。

08:30-09:00

想出了个贪心做法，结果测大样例寄了 XwX。

09:00-09:20

先把 C 暴力和 D 最低档分写了。

09:20-09:35

想了一会把 D 另外 10 档分写了。

09:35-10:35

B 居然有重边，把重边删了大样例就过了，算了下时间复杂度能过

剩下时间

摆烂。

Result

100+100+15+20=235100+100+15+20=235

Solution

T1

答案只与奇偶性有关，用并查集维护一下就行了。

另外二进制下乘法是 AND⁡\operatorname{AND}，加法是 XOR⁡\operatorname{XOR}.

T2

贪心的选权值最大点，然后再把其从其它点的权值和中减去，时间复杂度 O(nlog⁡n+n+m)\mathcal{O}(n\log n+n+m)。

但这样的话每条边上只会有点权较小的一个点会被统计入答案，所以直接加较小的那个点的点权即可，时间复杂度 O(mlog⁡m)\mathcal{O}(m\log m)，log⁡\log 的来源为判重。

T3

对于每段无 11 的连续段从两头删。

T4

将操作转化为图上的边，再通过性质类比转化为 LIS。