通过奇偶性来构造：P9575
通过奇偶性来构造：P9575
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471708
对于没有思路的，和数有关的构造题，可以考虑2的情况，也就是用奇偶来构造
构造时需要考虑：
如何用奇偶构造合法
非法是否能用奇偶反证
例题：P9575
考虑到 不定，可以转化为奇偶问题。
发现在奇偶情况下容易构造，且非法可以奇偶反证。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-05
兔队线段树：楼房重建
兔队线段树：楼房重建 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126096 https://www.luogu.com.cn/problem/P4198 本质：在线段树上每个节点维护信息时再深入到底部，加个 log\loglog O(nlog2n)O(n\log^2n)O(nlog2n) 总比 O(n2)O(n^2)O(n2) 优。 抽象到本题，就是对于每个线段树节点单独维护只考虑这个区间的答案。 合并的过程，显然左子树可以直接继承，所以可以...
2022-01-20
【CF1304C Air Conditioner】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15826957.html 题目 Gildong owns a bulgogi restaurant. The restaurant has a lot of customers, so many of them like to make a reservation before visiting it. Gildong tries so hard to satisfy the customers that he even memorized al...
2022-05-18
【一本通1489：构造完全图】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16285749.html 题目链接 题目 对于完全图 GGG，若有且仅有一棵最小生成树为 TTT，则称完全图 GGG 是树 TTT 扩展出的。 给你一棵树 TTT，找出 TTT 能扩展出的边权和最小的完全图 GGG。 思路 要使一个图总存在唯一最小生成树，需满足所有非最小生成树的边（假设连接 u,vu,vu,v），使这条边的边权 www 大于 u,vu,vu,v 在最小生成树上的最短路径的最大边权。 因此，我们可以先dfs一遍求出每个点到根节点...
2022-01-12
【Loj #10051. 「一本通 2.3 例 3」Nikitosh 和异或】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15791222.html 题目链接 题目 给定一个含 NNN 个元素的数组 AAA，下标从 111 开始。请找出下面式子的最大值： (A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])(A[l_1]⨁A[l_1+1]⨁…⨁A[r_1])+(A[l_2]⨁A[l_2+1]…⨁A[r_2])(A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])，其中 1≤l1≤...
2023-08-25
树套树小结
树套树小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132501426 树状数组套权值线段树，实现过程类似主席树，采用动态开点实现 https://www.luogu.com.cn/problem/P3380 树状数组部分 线段树部分
2026-06-17
算法复键——AC自动机
算法复键——AC自动机 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162074359 什么是AC自动机： 在Trie上跑kmp 核心思想：构建fail树。fail[u]指向一个节点，表示这个节点具有和u所在节点所代表串的最长公共后缀。 核心代码： 12345678910111213141516171819void bfs() { int i, j; q.push(1); fail[1] = 0; fail[0] = 1; // 根节点失配指向...