通过奇偶性来构造：P9575
通过奇偶性来构造：P9575
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471708
对于没有思路的，和数有关的构造题，可以考虑2的情况，也就是用奇偶来构造
构造时需要考虑：
如何用奇偶构造合法
非法是否能用奇偶反证
例题：P9575
考虑到 不定，可以转化为奇偶问题。
发现在奇偶情况下容易构造，且非法可以奇偶反证。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-03
网络最大流
网络最大流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091032 < Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷 > 先bfs分层 2.dfs增广，当前弧优化 重复以上步骤 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
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≤...
2022-04-22
【GDOI2022PJD1T4 小学生计数题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16180001.html D1T4 小学生计数题 题目 作为 GDOI 的组题人，小 Y 需要整理手中已有的题目，考虑它们的难度以及所考察的知识点，然后将它们组成数套题目。 小 Y 希望先能组出第一套题目，为了整套题目具有良好的区分度，在一套题目中： 所有题目的难度需要能排成等差数列；（也就是说，若将所有题目按难度从小到大排序，那么每相邻两题的难度的差相等，这个差叫做公差） 每道题目的难度都是公差的倍数，公差不为 0； 需要有不少于 LLL 道...
2021-11-18
【P2344 [USACO11FEB]Generic Cow Protests G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接 首先朴素dp不用讲，设 dpidp_idpi 表示前 iii 个数划分的总方案数，SiS_iSi 表示前 iii 个数的和。 dpi=∑j=0i−1dpj (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi=j=0∑i−1dpj(Si−Sj⩾0) 其中 dp0=1dp_0=1dp0=1。 可是这样的时间复杂度为 O...
2022-02-16
【一本通OJ 1600：【例 4】旅行问题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15901652.html 题目链接 题目 原题来自：POI 2004 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：判断以每个车站为...
2022-01-08
【ZR #540. 【19普转提4】串串】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778576.html 题目链接 题目 给定两个长度为 nnn 的只包含’a’,‘b’,'c’的字符串s,ts,ts,t。 请打乱串 sss，使得 ∀i,si≠ti\forall i,s_i \not= t_i∀i,si=ti，且 sss 字典序最小。 思路 对于 ttt 串中从前往后每一个字母，在 sss 的剩余可选字母中选字典序最小的。 如果 sss 的剩余字母中没了，就往前找第一个可以替换的替换。 最后再对每种 ttt 中的字母按...