通过奇偶性来构造：P9575
通过奇偶性来构造：P9575
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471708
对于没有思路的，和数有关的构造题，可以考虑2的情况，也就是用奇偶来构造
构造时需要考虑：
如何用奇偶构造合法
非法是否能用奇偶反证
例题：P9575
考虑到 不定，可以转化为奇偶问题。
发现在奇偶情况下容易构造，且非法可以奇偶反证。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-24
对于DP颜色类问题的切换方法：P9561
对于dp颜色类问题的切换方法：P9561 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471731 对于dp颜色类问题的切换方法 两种颜色为例，一般情况下 dp[i][0]dp[i][0]dp[i][0] 可以由 dp[j][0/1]dp[j][0/1]dp[j][0/1] 在某些情况下转移 但从0到0的过程中，对于 jjj 前的1，可能 jjj 满足，但 iii 不满足 此时可以考虑0只从1转移，1只从0转移，对于新的0，我们除了统计当前dp值，我...
2022-04-29
【CF339D Xenia and Bit Operations】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...
2023-09-07
回文自动机PAM小结
回文自动机PAM小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132136120 https://www.luogu.com.cn/problem/P5496 类似AC自动机，维护两个指针，nxt和fail nxt表示当前回文串开头末尾都接a转移到哪 fail表示当前串最长broder PAM关键点：一个回文串的broder一定也是回文串，而且所有回文子串（末尾相同）都可以用此方法构造 然后转移和AC自动机类似。 几个理解上的易错点： fail...
2021-12-11
【P1661 扩散】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674805.html 题目链接 题目 一个点每过一个单位时间就会向四个方向扩散一个距离，如图。 两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。 思路 二分答案+并查集。 首先二分时间 ttt。 如果两个点能直接相连，则他们的曼哈顿距离小于二倍 ttt。并且把...
2022-01-10
【CF5E Bindian Signalizing】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15784242.html 题目链接 题目 Everyone knows that long ago on the territory of present-day Berland there lived Bindian tribes. Their capital was surrounded by n n n hills, forming a circle. On each hill there was a watchman, who watch...
2021-11-24
【NOIP2021 方差】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简 首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1∑i=1n(ai−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1∑i=1nai。 我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...