NOI.AC CSP-S 模拟 Round 4 简要题解

本文主要是介绍NOI.AC CSP-S 模拟 Round 4 简要题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接
T1
一个数，有贡献，当前仅当包涵它的区间个数为奇数
发现区间长度为偶数时没有贡献，答案为 0
长度为奇数时贡献是第 $1,3,5...$ 个数，预处理两个前缀异或和即可

---

T2
结论题，orz
发现对于一个联通块，如果边数 - 点数为偶数，一定可以有一种方案使得全部都是奇数
如果边数 - 点数为奇数，一定可以有一种方案使得只有一个点是偶数
于是并查集维护一下连通块的边数点数即可

---

T3
发现取 $min$ 的操作不能回退，于是背包回退就凉了
开始想的是求前缀后缀然后拼接，发现拼接需要 $O(m^2)$ 凉凉
只好分治，在进入 $[l,mid]$ 之前将 $[mid+1,r]$ 插入背包，递归到最底层的时候就只有当前点没有插入
复杂度 $O(nmlogn)$

---

总结：
关于 T2：没有头绪时可以猜一猜结论，再试着去证明
然后复习了一下分治背包

这篇关于NOI.AC CSP-S 模拟 Round 4 简要题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---