2021-08-17~2022-01-07¶
CF1375D¶
题意¶
给定一个长度为 \(n\) 的序列 \(a_0,a_1,\ldots,a_{n-1}\)，每次可以将一个位置替换为这个序列的 \(\text{mex}\)，要求用不超过 \(2n\) 次操作将整个序列变为不减的。(\(1 \le n \le 1000\)，\(0 \le a_i \le n\))
题解¶
首先从 \(0\) 遍历到 \(n-1\)，如果当前序列没有这个数，那么当前 \(\text{mex}\) 就是这个数，让 \(a_{\text{mex}}=\text{mex}\)。
那么整个序列必然构成一个排列，对于一个长度为 \(m\) 的环 \(a_{p_1},a_{p_2},\ldots,a_{p_m}\)，依次选择 \(p_1,p_2,\ldots,p_m,p_1\) 这些位置替换为当前的 \(\text{mex}\)，就可以让这个环每个位置有 \(a_i=i\)，即先把 \(n\) 放到 \(p_1\)，再把原来的 \(a_{p_1}\) 放到 \(p_2\)，依次类推，最后再把 \(a_{p_m}\) 放回 \(p_1\)。
第一步中操作后所有点均为大小为 \(1\) 的环，可以不进行操作，第二步对于每个长度为 \(m\) 的环需要进行 \(m+1\) 步，因此总和不会超过 \(2n\) 次。
CF1375E¶
题意¶
给定一个长度为 \(n\) 的序列 \(a_1,a_2,\ldots,a_n\)，设它的逆序对分别为 \((u_1,v_1),(u_2,v_2),\ldots,(u_m,v_m)\)，给这 \(m\) 个逆序对任意排列使得依次交换 \((u_1,v_1),(u_2,v_2),\ldots,(u_m,v_m)\) 位置上的数可以使得序列变得不减。(\(1 \le n \le 1000\)，\(1 \le a_i \le 10^9\))
题解¶
先考虑排列的情况，考虑如下的增量构造法：
考虑把 \(n\) 放到最后一个位置，并且用完包含位置 \(n\) 的所有逆序对，不使用不包含位置 \(n\) 的所有逆序对，同时操作完后前 \(n-1\) 个位置的大小关系保持不变，这样就可以转化为一个规模为 \(n-1\) 的子问题。
设 \(p_{a_i}=i\)，则依次操作位置 \((p_{a_n+1},n),(p_{a_n+2},n),\ldots,(p_{n},n)\) 就可以把 \(n\) 放到最后，同时前面每个比 \(a_{n}\) 大的数都恰好减少了 \(1\)，从而转化为了一个规模为 \(n-1\) 的子问题。
本题不是排列，可以将值设为第一关键字，位置设为第二关键字，这样原序列转化为一个排列，同时逆序对和转化后的排列完全相同，按上面的方法构造即可。
CF1375F¶
题意¶
交互题，两个人博弈，初始有数量为 \(a,b,c\) 的三堆石子，先手每次给定一个正整数 \(y\)，后手则需要将其加到一堆石子上，不能连续两次加同一堆石子，你需要选先手或后手使得你可以必胜。(\(1 \le a,b,c \le 10^9\)，\(1 \le y \le 10^{12}\))
题解¶
先手必胜，只需将三堆石子构造成等差数列 (当然公差不能为 \(0\)) 且上一次加到了最大的上面就可以获胜。
首先选一个大数 \(10^{10}\)，不妨设加到了 \(a\) 上，让 \(a+10^{10}\) 作为等差中项。
再选一个数 \(2\left(a+10^{10}\right)-b-c\)，不妨设加到了 \(b\) 上，那么此时 \(c,a+10^{10},2\left(a+10^{10}\right)-c\) 构成等差数列。
最后选其公差 \(a+10^{10}-c\) 即可获胜。
CF1375G¶
题意¶
给定一颗 \(n\) 个节点的树，每次可以选择 \(a,b,c\) 三个节点，其中 \((a,b)\) 和 \((b,c)\) 边存在，进行如下操作：
问最少需要几次操作可以将树变成菊花图。(\(3 \le n \le 2 \times 10^5\))
题解¶
对树黑白染色，可以发现每次操作恰好只让一个节点颜色翻转，例如保持 \(c\) 的颜色不变，则只有 \(a\) 的颜色翻转了。
而菊花图有 \(1\) 个黑点 \(n-1\) 个白点，因此操作次数的下界为 黑点数与白点数的最小值 \(-1\)， 作为一道 cf 题，一般下界就是答案，只需证明不是菊花图的树一定可以进行该操作：
如果不是菊花图，一定存在长度为 \(3\) 的链，从而一定可以选择 \(a,b,c\) 进行该操作。