T1 可持久化线段树
做法一:注意到 \(\sum k<n\),所以数据结构直接暴力回溯是对的,然后做完了。
做法二:还是注意到那个,记一下修改过的节点,然后回溯直接改节点。
做法三:主席树区间修改,一直想写,但是好像没啥用这个东西,to the moon 是板子,我想抽时间玩玩 to the moon
T2 Little Busters !
只保留 L
边,找一下全部的边双,这样可以保证所有属于变双的 L
边一定是没有必要删的,对于是割边的 L
边,否则它要么与 Q
边组成边双,要么自己仍然是割边,一定不合法,所以一定要删。
想到这一点就没什么了,接下来考虑加入 \(Q\) 边,当且仅当它连接的两个端点不在一个连通块内才加入,拿并查集跑一下即可,最后检查一遍连通性。
T3 魔卡少女樱
对于答案序列 \(a\) 来说,它的差分数组是独一无二的,所以就转化为了求差分数组的方案数,这样转化后可以保证序列单调递增。
对于差分数组 \(b\) 来说,\(\sum b_i\le m\),\(\forall i\in[2,n]\ \ \ \ b_i\not\equiv 0\pmod{3}\),由于 \(b_i\) 只有 \(1\) 和 \(2\) 两个取值,所以当确定一个取值的数量的时候,另一个取值的数量也确定了。
考虑枚举 \(b_i=2\) 的数量为 \(k\),这时方案数为 \(\operatorname{C}_{n-1}^k\),\(\sum b_i=b_1+2k+(n-1-k)=b_1+n-1+k\),然后还剩下可以加的值为 \(s=m-b_1-n-k+1\),为了确保 \(b_i\bmod 3\) 不变,所以对于一个 \(b_i\),只能给他加上 \(3w(w\in\mathbb N)\),所以最多可以加 \(\lfloor\frac{s}{3}\rfloor\) 个 \(3\),这个的数量就是分配数,答案就是求
其中第一个 \(\sum\) 是枚举 \(b_1\bmod 3\) 的取值,第二个 \(\sum\) 是枚举 \(b_i\bmod 3=2\) 的个数,第三个是枚举加 \(3\) 的个数,代码只需要预处理阶乘逆元和前缀和即可,世界复杂度 \(O(n+m)\)。
T4 声之形
不会
总结
这场也不行,图论还是不咋会,也不是思路多难,想不到,就是对图论的一些理解不深刻,对 tarjan
的理解就更不深刻了,或者说遇到图论就不会思考了,建议多练图论题单(来个人推一下)。T3 数组小了,挂 5pts,T4 看错题挂 10pts。总结就是没切 T2 不应该,T3 没打上特殊性质不应该,这场期望 280pts。