[技巧] 一定有解：一类很强的隐藏条件

\textcolor{E42745}{呐 \ 你知道吗？} \\ \\ \textcolor{E42745}{所谓的难题啊 \ 是你还没发现条件呢} \ \textcolor{339EC8}{唉—} \\ \\ \textcolor{E42745}{呐 \ 你知道吗？} \\ \\ \textcolor{E42745}{思维 \ adhoc \ 开个挂就能切简单模式} \ \textcolor{339EC8}{唉—} \\ \\ \textcolor{E42745}{更何况钦定有解 \ 你就能切掉难题哦} \\ \\

\textcolor{339EC8}{诶～ \ 原来如此\ 真是受益匪浅呢} \\ \\ \textcolor{339EC8}{不如就信了这题一定有解吧！} \\ \\

以上是防伪标识

以下是正文

例题讲的比较简略，主要是为了记录这类 Trick。

我们在做构造或者最优化题目的时候，经常会看到以下的文字：

可以证明，在该约束下问题一定有至少一个解。

这句话在有些题目中确实仅仅是为了打消做题者的疑虑，但是在另一些题目中则是不可多得的珍贵条件。若学会使用此类性质，对此类题目的做题速度将大大提升。因此，我在这里总结了几道要用到这个性质的题目，以及他们对应的入手方向。

数学归纳法

有时候，一定有解是提示我们把问题划分为同类的子问题，并且不需要考虑解决当前问题时对子问题的影响（因为只要保证是同类的子问题，则必然能做出来）。

一个 $n \times m$ 的棋盘，要求用若干 L 型覆盖它，使得只有 $(1, m)$ 不被覆盖，且 L 之间不重叠。

猜想只要余数正确，则一定有解。然后考虑使用数学归纳法，每次覆盖最右上角的几行，然后递归求解相同的问题。

给定两个长度为 $n$ 的数组 $mask, val$ ，你可以选择一个数 $s$ ，然后修改所有数的 $val$ ，如果 $s \& mask$ 有奇数个 $1$ 就把 $val$ 变成 $−val$ 。输出一个 $s$ ，使得权值和与原权值和异号。此问题一定有解。

问题一定有解的条件可以转化一下：一定存在两个数 $x, y$ ，使得选择 $x$ 时权值和为正，选择 $y$ 是为负。

我们对于

i : 61 \to 0

考虑每个二进制位，如果对于一个

j

，

\operatorname{lowbit}(mask_j) = 2^i

，那么

i

这一位决定了

j

。我们只需要考虑被位置

i

决定的数即可，因为剩下的一定有解。因此对于每一位贪心地考虑当前位是否取一就是对的。

把给定数组划分为两个长度相差至多是 $1$ 的子序列，并把这两个子序列按照 ABAB...ABAB 的方式间隔插入排列。要求给出一种新数组相邻元素不同的构造方案。

猜测：众数不超过一半时一定有解。

有了这个条件，我们可以把原数组划分为若干个“众数是绝对众数”的子串，然后用最简单的方式（众数放一个数组，剩下的放另一个数组）划分它们，最后拼起来即可。

需要注意的是最后一次划分可能无法划分出有绝对众数且剩下部分有解的分割线。对这种情况需要特判，详见题解。

往往我们做题时需要采取各种方法规避限制。但是有的时候，把题目转化为严格强于原问题的问题反而会更加好做。

给定 $n$ 条线段 $[l_i, r_i]$ ，给这些线段红蓝染色，使得最后直线上上任意一个点被蓝色及红色线段覆盖次数之差的绝对值不大于 $1$ 。

坐标可能相同，这样不好做。但是题目没有让判断无解，可知任何此类问题都可解，那么可以直接把坐标离散化，这样新问题严格强于原问题，但是更加好做了，我们可以转化为图论问题（欧拉回路）解决。

题意较长，故省略。

显然直接构造是非常困难的。

这时候我们需要注意题目的两个样例都能让所有传送门都是好的。不妨强化限制，把原题变成构造一种让所有传送门都是好的类型设置方式，然后猜测一定有解。

考虑到这一点后，按照权值从小到大考虑传送门的设置方式即可。剩下的部分非常简单。