当前位置：首页 > news >正文

Codeforces Round #636 (Div. 3) D. Constant Palindrome Sum（差分）

news 来源：原创 2024/4/29 2:23:29

传送门

在这里插入图片描述
1.题目大意：给出一个偶数长度的序列，保证每个数都是 $[1, k]$ 范围内，现在可以将每个下标的数都更换为 $[1, k]$ 之间的任意数，且需要 $n / 2$ 对数都满足 $a_i+a_{n-i+1}=x$ ，求出所有 $x$ 的最小的更换数的次数

2.首先可以知道 $x$ 的范围是 $[2, 2 * k]$ ，那么首先可能想到的是对每个 $x$ 暴力计算最小的更换次数，但这样肯定超时。对于每对数 $a_i,a_{n-i+1})$ 原本为 $(A, B)$ ，更改为 $x$ 有以下三种方式：

$x = A + B$ 时不需要更改任何数
当更改一次的时候，每对数的更改范围为 $[m i n (A, B) + 1, m a x (A, B) + k]$ ，注意 $A + B$ 也包含在内
在上述 $[m i n (A, B) + 1, m a x (A, B) + k]$ 范围外且在 $[2, 2 * k]$ 范围内的 $x$ ，需要这对数更改两次
因此，我们首先假设每个对数都需要更改两次，那么对于 $[2, 2 * k]$ 的每个 $x$ ，初始都为 $n$ 。显然对于上面的第一种出现这种情况让原本的 $n$ 次操作少了两次，对于第二种情况，会让这个范围内的 $x$ 都操作少一次，对于区间操作，我们如果 $f o r$ 循环遍历更新，应该是超时的。那么考虑区间更新，可以使用另外一个差分数组 $s$ ，记录区间内的变化，最后对差分数组求前缀和即可。这里需要注意的是减少一次操作的区间内包括了 $A + B$ ，因此第一个情况让该 $x$ 减少一次即可。

3.再复习一下差分：差分即相邻两个数的差，由a数组我们能得到a的差分数组 $d [i] = a [i] - a [i - 1]$ ，还可以得到二者之间的关系:

$a [i] = d [1] + . . . + d [i]$

那么我们会发现，如果对一个区间 $[x, y]$ 内的所有数都执行加法，那么显然只有 $d [x]$ 和 $d [y + 1]$ 的值会改变， $[x + 1, y]$ 区间的值都不变。

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn],t[maxn*2],s[maxn*2];
int T,n,k;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=2;i<=2*k;i++) t[i]=n,s[i]=0;
        for(int i=1;i<=n/2;i++){
            int x=a[i],y=a[n-i+1];
            int l=min(x,y)+1,r=max(x,y)+k;
            t[x+y]--;
            s[l]--,s[r+1]++;
        }
        int ans=inf;
        for(int i=2;i<=2*k;i++){
            s[i]+=s[i-1];
            t[i]+=s[i];
            ans=min(ans,t[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}