CF1343D Constant Palindrome Sum 题解

[也许更好的阅读体验](https://blog.csdn.net/Andrewzdm/article/details/105682808) # [CF1343D Constant Palindrome Sum](https://www.luogu.com.cn/problem/CF1343D) 打比赛的时候这道题没想出来，等到想出来的时候比赛结束了……$qwq$ 下面进入正题：（前一部分我会复盘我的思路过程供大家参考，当然这是一个**蒟蒻的思考过程**， 大家完全可以跳过） * * * * 首先拿到题目，先想了下能否贪心，发现找不到贪心策略。毫无头绪，我开始尝试寻找突破口。这时我发现题目有一点比较奇怪：题目给了 $k$ 的范围还保证 $\sum k \leq 2 \times 10^5$。这就在暗示我们复杂度正常情况下应该含有 $k$（大部分题目还是没有废话的）。 接下来我观察到因为所有的数（初始的和替换的）都在 $[1,k]$ 内，所以每一对数的和一定在 $[2,2k]$ 内。 那么我们不妨考虑枚举题目中要求的等式 $$a_i + a_{n-i-1} = x$$ 中的 $x(2 \le x \le 2k)$，算出每一对数需要替换多少个数，最后在所有的结果中取 $\min$，时间复杂度为 $O(nk)$。 但是这样会 $\texttt{TLE}$，为了不超时，基于枚举 $x$ 的算法思想，时间复杂度要么 $O(k \log n)$ 要么 $O(k+n)$。 首先我想出了一个解法，然而很遗憾是错的。这个想法是这样的（不想看的可以跳过）： 把每一对数的总和进行排序，然后把所有的总和分成 $sum<x,sum=x,sum>x$ 三个部分。当 $2 \le x \le k$ 时，除了 $sum=x$ 的一部分，剩下的两部分都要进行一次替换。还没开始想 $k < x \le 2k$ 的情况，我就发现我错了： > 比方说给定的 $a$ 是 $1,2,2,3$，求出总和排序后是 $4,4$。当 $x=2$ 时，我们会计算出替换次数为 $2$。可是 $2,2$ 这一对数要想总和为 $2$ 必须替换两次。所以替换次数应该为 $3$。 好吧，只能换思路了。 接下来是正解： ---- 我们先前的算法之所以是 $O(nk)$，是因为我们在枚举 $x$ 的过程中才计算每一对数需要替换多少个。为了优化，我们需要想办法进行**预处理**，算出对于每一个 $x$，有多少对数可以一个都不替换，有多少可以只替换其中一个，有多少必须两个都要替换。 不妨考虑各个击破： ### 一个都不替换 这个很简单，我们开一个数组 $equ$，其中 $equ_i$ 表示当 $x=i$ 时有多少对数可以一个都不替换。 因为不用替换的条件就是一对数的和 $sum=x$，那么我们只要算出每一对数的和 $sum$，并且 `equ[sum]++` 就可以了。 ### 只需要替换其中一个 首先，对于一对数 $a_i,a_{n-i+1}$，在只替换其中一个数的情况下，它们的和只能在 $[\min(a_i,a_{n-i+1})+1, \max(a_i,a_{n-i+1})+k]$ 中。我们稍微变通一下，求出有多少对数**至多**需要替换一个，那么**只**需要替换一个的数目就很好求了，为至多需要替换一个的数目减去一个都不需要替换的数目。 那么如何求出有多少对数至多需要替换一个？这个问题就变成了：对于 $x$，求出有多少个区间 $[\min(a_i,a_{n-i+1})+1, \max(a_i,a_{n-i+1})+k]$ $(1 \le i \le \dfrac{n}{2})$ 覆盖了 $x$。 这一问题可以这样解决（而且对于类似的“求每一个数有多少个区间覆盖了此数”的问题都可以这样做）： 开一个数组 $cover$，$cover_i$ 表示有多少个区间覆盖了数 $i$。首先枚举区间，设区间的左右端点分别为 $l,r$，然后我们进行操作 `cover[l]++` 和 `cover[r+1]--`，枚举完后再用计算前缀和的方式进行如下操作： `cover[i] += cover[i-1]`。然后我们就求完了。 下面解释下算法的原理：其实我们 `cover[l]++` 和 `cover[i] += cover[i-1]` 的两个操作等效于对于所有的 $i \in [l,rbound]$ 进行 `cover[i]++`。类似的，我们也进行了 `cover[i]--`$(i \in [r+1, rbound])$。前一个操作计算了有多少个区间的左端点小于等于 $x$，而后一个操作计算了有多少个区间的右端点小于 $x$。一加一减就是覆盖了 $x$ 的区间数目。 如果还是难以理解，可以尝试自己举个栗子模拟一下，这里就不赘述了。 ### 两个都需要替换 因为我们求出了 $cover$，这一问题相当简单。一句话搞定： $$num_i = \dfrac{n}{2} - cover_i$$ 不要忘了我们的 $cover_i$ 表示有多少对**至多**需要替换一个数。 所以我们对于每个 $x$，最少替换步数 $ans_x$ 就可以这样计算： $$ans_x = cover_x - equ_x + num_x \times 2$$ 最终时间复杂度 $O(k+n)$。 ### Code: ```cpp #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int equ[2 * maxn], cover[2 * maxn], a[maxn]; signed main() { int T; cin >> T; while(T--) { int n, k; scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", a + i); //注意值域最大为2k，初始化到2k+4比较保险。 fill(equ, equ + 2 * k + 5, 0); fill(cover, cover + 2 * k + 5, 0); for(int i = 1; i <= n / 2; i++) equ[a[i] + a[n - i + 1]]++; for(int i = 1; i <= n / 2; i++) { cover[min(a[i], a[n - i + 1]) + 1]++; cover[max(a[i], a[n - i + 1]) + k + 1]--;//注意加上k之后还要加上1 } for(int i = 3; i <= 2 * k; i++)//值域最小为2，所以从3开始做前缀和就可以了 cover[i] += cover[i - 1]; int ans = INT_MAX; for(int x = 2; x <= 2 * k; x++) ans = min(ans, cover[x] - equ[x] + (n / 2 - cover[x]) * 2);//这里就没有再开一个数组num了 printf("%d\n", ans); } return 0; } ```