思维题做题记录-1

CF2600左右有趣的思维题做题记录-1

CF1458C. Latin Square

考虑将原矩阵写成 \(n\times n\) 个限制形如 \((i,j,a_{i,j})\)，那么所有操作就是对这些限制进行的修改：

• 对于 UD 操作相当于将限制改为 \((i\mp 1,j,a_{i,j})\)。
• 对于 LR 操作相当于将限制改为 \((i,j\mp 1,a_{i,j})\)。
• 对于 IC 操作相当于将限制改为 \((i,a_{i,j},j)\) 或 \((a_{i,j},j,i)\)。

因此可以看出我们只需要维护在所有操作结束后三元组的变化情况（包括每一维最后所处的位置和其对应的偏移量）就可以快速得出操作后的矩阵，那么复杂度可以做到 \(O(n^2+m)\)。

CF1666E. Even Split

关注到一个较大的极差中肯定可以构造一个较小极差的方案，也就是说极差是具有单调性的，可以考虑二分。

二分出一个极差后，我们考虑如何判断这个极差是否合法。显然光有极差是难以判断的，我们还需要最小值和最大值。考虑已知最小值和最大值 \(L,R\) 后如何去判断是否有解：对于每一个 \(a_i\)，我们显然可以计算出包含这个点的区间的可行右端点范围 \([l_i,r_i]\)，因为有

\[l_i=\max(l_{i-1}+L,a_{i}),r_i=\min(r_{i-1}+R,a_{i+1}) \]

那么显然我们还要求 \(l_i\le a_{i+1},r_i\ge a_i\)，否则我们显然无法构造出合法的解（我们认为 \(a_{n+1}=l\)）。显然这两个条件不可能同时不成立，并且我们可以分析出违反第一个条件是因为最小值太大了，违反第二个条件是因为最大值太小了，也就是最小值同样满足单调性，那么我们依旧可以通过二分简单求出是否存在一个合法的 \(L,R\) 并给出构造。

现在问题在给出方案，考虑先取所有 \(p_i=l_i\)，那么 \(p_i-p_{i-1}\ge L\) 的条件就已经满足了，接着我们先强制要求 \(p_n=l\)，接着从后往前推，令所有 \(p_i-p_{i-1}>R\) 的 \(p_{i-1}\) 的值为 \(p_i-R\)，这样也就满足了 \(p_i-p_{i-1}\le R\) 的条件。因为你已经保证了对于 \(L,R\) 有解，那么这样构造出来的方案定然是合法的。那么我们可以做到 \(O(n\log^2V)\) 的复杂度。

CF1809E. Two Tanks

考虑不管怎样倒水两个水桶里的水的总量不变，因此不妨将总量相同的点放在一起考虑。

在这种情况下，我们发现 \(v_i>0\) 相当于试图将所有点向右上方移动 \(v_i\) 步（一步指从 \((a,b)\) 移动到 \((a-1,b+1)\)），相应的 \(v_i<0\) 相当于试图将所有点向左下方移动 \(-v_i\) 步（一步指从 \((a,b)\) 移动到 \((a+1,b-1)\)），显然越界的操作我们不会执行。那么最靠左下的若干个点将会重叠在一起，最靠右上的若干个点将会重叠在一起，剩下的点相邻的分布在对应位置上，每个点的答案就是其所处位置的横坐标。

于是我们只需要知道对于每个不同的总量，在操作完之后有多少个最靠左下的点重叠在了一起、有多少个最靠右上的点重叠在了一起、最左下的点在操作完之后相对于初始位置移动了多少步就可以推出所有点的答案。

事实上注意到对 \(v\) 求出前缀和 \(v'\)，记 \(L=1+\max\limits_{i=0}^{n}-v'_i,R=1+\max\limits_{i=0}^{n}v'_i\)，那么前 \(L\) 个最靠左下的点和前 \(R\) 个最靠右上的点是一定会重叠在一起的，因此只需要统计最左下的点在操作完之后相对于初始位置移动了多少步就可以了。复杂度是 \(O(n(a+b))\) 的。

CF1774F2. Magician and Pigs (Hard Version)

我们设 \(w_i\) 表示第 \(i\) 次操作 3 之前的所有操作造成的减少的和，对于 \(w\) 的维护是容易的：对于操作 2，\(w\) 会加上减少的生命 \(x\)；对于操作 3，\(w\) 会翻倍。

那么对于这次操作之前的所有操作 1 产生的当前生命为 \(x\) 的猪，相当于要选择变成 \(x\) 还是 \(x-w\)（考虑这头猪在复制后是前面的还是后面的），那么要求的内容就是 \(x\) 在减去之后的所有 \(2\) 操作后，有多少种选择方法能够使最终的 \(x>0\)。

注意到我们有 \(2w_i\le w_{i+1}\)，也就是除去最开始的 \(w_i=0\) 的操作 3，我们最多有 \(\log V\) 个操作 3 是有效的，否则我们定然不能让 \(x\) 减去 \(w\)。然后考虑如何统计方案数，除了有效的操作 3 的数量，\(2w_i\le w_{i+1}\) 还保证了 \(\sum\limits_{k=1}^{i}w_i<w_{i+1}\)。那么我们只需要从大到小枚举 \(w\)，如果当前的 \(x\) 足够减去这个 \(w\)，就说明如果不减这个 \(w\)，后面的选择可以任意选，贡献是 \(2^{i-1}\)。然后我们只剩下一种选择，向下继续枚举即可。复杂度是 \(O(n\log v)\) 的。

CF1208G. Polygons

考虑在选择一个 \(n\) 之前，我们肯定已经选择了其的所有因子。如果存在某个因子 \(d\) 还没有选，那么因为我们一定可以调整使得这 \(d\) 个点被 \(n\) 个点完全包含，那么选择 \(d\) 肯定不劣。

现在 \(n\) 的所有因子已经选过了，我们记所有多边形都存在一个点 \(0\)，那么其它的点顺次排开应该是 \(\frac{1}{n},\frac{2}{n},\cdots,\frac{n-1}{n}\)，能够留下的点一定满足分子分母互质，否则选择两个数的最大质因子时这个点一定已经出现了。那么一个边数为 \(n\) 的多边形的贡献就是 \(\varphi(n)\)，用线性筛求出后，排序选择前 \(k\) 小的值即可。

然而，因为我们只能选择 \(n\ge 3\) 的多边形，那么实际上我们并没有统计到 \(0,\frac{1}{2}\) 这两个点，那么我们求得的答案就是错的。不妨考虑特判：

• \(k=1\) 时我们一定选择正三边形，此时应该统计 \(0\) 这个点。
• \(k=2\) 时我们一定多选择了正四边形，此时应该统计 \(\frac{1}{2}\) 这个点。
• \(k\ge 3\) 时两个点都已经在选择正三边形和正四边形的时候统计了，不需要继续特判。

于是我们只需要特判 \(k=1,2\) 的情况。复杂度瓶颈在排序的 \(O(n\log n)\)。

CF1887C. Minimum Array

考虑对操作差分，那么当差分数组的第一个非 \(0\) 数 \(<0\) 时，当前数组的字典序一定比之前记录的字典序要小，那么我们记录此时的数组，然后清空差分数组即可。关注到我们只需要清空有值的位置，那么复杂度是正确的，用线段树可以简单维护这个内容，复杂度是 \(O(n\log n)\) 的。

CF1672F2. Checker for Array Shuffling

考虑排列的交换次数越多，那么排列所形成的置换环个数就越少。考虑对给定的原序列构造一个置换环，显然如果一个置换环中存在相同元素，我们肯定存在一个方案使得环更多，因此最终得到的环中肯定不存在相同的元素。那么不难构造出环的个数为 \(\max c_i\) 满足条件（其中 \(c_i\) 表示 \(i\) 的出现次数）。

考虑如何判定。不难发现不存在一个环使得其中没有出现次数最多的元素是环的个数是 \(\max c_i\) 的充要条件。那么考虑对于一个 \(i\)，所有 \(a_p=a_i\) 的 \(p\) 向所有 \(b_q=b_i\) 的 \(q\) 连边，最后删除所有出现次数最多的元素，如果仍然存在环则不合法。直接连边有 \(O(n^2)\) 条边，建立虚拟节点可以做到 \(O(n)\)。用拓扑排序判环，复杂度可以做到 \(O(n)\)。

注意有多个出现次数最多的元素时我们只取其中之一。

CF1975F. Set

考虑到当我们确定一个元素是否在集合中时，我们本质需要的限制会减半，因此可以直接搜索。每次确定一位 \(i\) 后，先判断 \(V_{f(\{i\})}\) 是否合法，然后将 \(V_{f(S)}\) 和 \(V_{f(S\cap\{i\})}\) 的限制合并，然后递归子问题即可。复杂度是 \(O(n\log n)\) 的。

CF1680D. Dog Walking

先特判掉无解的 corner case。接下来问题相当于要最大化极差，考虑极差相当于一段区间和，那么我们枚举这个区间，并试图让这个区间的和最大即可。显然我们为了最大化区间和，这个区间中的所有 \(0\) 要么全取 \(+k\)，要么全取 \(-k\)。

然而这个题目还限制了所有 \(a_i\) 的和必须为 \(0\)，所以我们必须要求区间外的数可以平衡我们的最大值。设我们有不等式 \(L\le p\le R,L'\le p'\le R'\)，为了使 \(p+p'=0\)，我们有 \(\max(L,-R')\le p\le \min(R,-L')\)，\(|p|\) 的最大值显然在端点处取到，于是我们可以做到 \(O(n^2)\) 求解。

CF1930F. Maximize the Difference

考虑所求本质相当于 \(\max\{(b_i|x)-(b_j|x)\}\)。考虑对于一对 \((i,j)\)，如果数位上分别是 \((1,0)\)，那么这一位肯定不能或 \(1\)；而如果数位上分别是 \((0,1)\)，那么这一位肯定要或 \(1\)；对于 \((0,0)(1,1)\)，这一位或不或都行，那么显然 \(x=b_j\) 时最优，那么就相当于求 \(\max\{(b_i|b_j)-b_j\}=\max\{b_i\&(\lnot b_j)\}\)。

考虑如何动态维护这个内容，我们设 \(f_S\) 表示是否存在 \(S\subseteq b_i\)，\(g_S\) 表示是否存在 \(S\subseteq (\lnot b_j)\)，那么答案就是最大的使 \(f_S,g_S\) 同时成立的 \(S\)。我们考虑直接记忆化搜索更新 \(f,g\) 数组，复杂度均摊是 \(O(n\log n)\) 的。

CF1375G. Tree Modification

看到相邻考虑黑白染色，那么对于一个白色点操作相当于将其周围的所有黑色点挂到某一个白点上，并将这个点染为黑色后同样挂到白点上（对黑色点操作则正相反）。最后的形态显然只有一个黑色点或白色点，而每次最多减少一个黑色点或白色点，答案自然就是黑色点数量和白色点数量的最小值最后减去 \(1\)，复杂度是 \(O(n)\) 的。

CF1817C. Similar Polynomials

对于一次函数我们显然是能快速求解的：设 \(A(x)=kx+b\)，则 \(A(0)=b,A(1)=k+b,B(0)=A(s)=ks+b\)，那么可以解出 \(s=\frac{B(0)-A(0)}{A(1)-A(0)}\)。

然而现在我们有一个多次函数，因此可以考虑对函数降次，也就是差分。我们知道差分一次会让得到的函数的次数减 \(1\)，那么只需要进行 \(d-1\) 次差分就可以得到一个一次函数，用 \(A(0),A(1),B(0)\) 计算 \(s\) 即可。至于如何快速计算 \(d-1\) 阶差分后的结果，我们有公式

\[\Delta^kf(x)=\sum_{i=0}^{k}\binom{k}{i}(-1)^{k-i}f(x+i) \]

于是可以在 \(O(d)\) 的复杂度内求解原问题。

CF1842F. Tenzing and Tree

考虑求出每个子树中黑点的个数 \(\text{sum}_i\)，那么答案就是 \(\sum|k-2\text{sum}_i|\)。当我们以所有黑点的重心为根时，显然有 \(2\text{sum}_i\le k\)，那么就可以去掉绝对值。考虑枚举这个重心 \(p\)，那么所有的贡献就是 \(\sum(k-2\text{sum}_i)=(n-1)k-2\sum\text{dep}_i\)，可以看出只需要最小化所有黑点的 \(\text{dep}\) 和即可，排序后贪心选择前 \(k\) 小的黑点即可，复杂度是 \(O(n^2\log n)\) 的。

如果我们贪心选出来的 \(k\) 个点不以 \(p\) 为重心，那么答案显然更小，因此不会有问题。

CF1369E. DeadLee

设当前第 \(i\) 道菜还有 \(c_i\) 个人要吃，还剩 \(w_i\) 个这道菜，那么当 \(c_i\le w_i\) 时显然这 \(c_i\) 个人肯定都有饭吃，那么不如把他们全部安排到序列尽可能后的位置，否则他们会抢占其他人的名额。然后我们将这些人除去后更新一下 \(c_i\)，如果出现新的 \(c_i\le w_i\)，就继续更新，这样操作直到无法更新。此时如果所有人都被安排了，那么输出即可；否则，对于此时所有的 \(c_i>w_i\)，显然不论怎样安排顺序都不会使得 \(c_i\le w_i\)，那么当所有 \(w_i=0\) 时，一定存在 \(c_i\) 不为 \(0\)，显然不合法。

整个过程和拓扑排序较为相似，用队列实现即可做到 \(O(m)\)。