题解：CF2117D Retaliation

wangzichen20240101 · 2025-09-25 21:31:49 · 题解

这题运用了一个小技巧，就是先假设可以使数组爆炸，那么所有元素都一定相等。

这时只用考虑 a_1 和 a_2 两个元素，使它们两个相等，再看其它元素是否也相等并可以化为 0。

分三种情况：

最后再所有元素是否相等并是否可以化成 0 就可以了。

其中，如果同时进行操作 1 和 2，每个元素都加上 i+\left(n-i+1\right)，两个 i 消掉，结果为 n+1，所以只需要判断元素是否可以被 n+1 整除并且大于等于 0 就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N],n,T;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 1;i <= n;++i){
            cin >> a[i];
        } 
        int x = abs(a[1] - a[2]);//操作要执行x次，因为每次操作a[1]和a[2]的差只会减少1
        if(a[1] < a[2]){
            for(int i = 1;i <= n;++i){
                a[i] -= x * i;//相当于削弱a[1]更少使其与a[2]相等 
            }
        }
        else{
            for(int i = 1;i <= n;++i){
                a[i] -= x * (n - i + 1);
            }
        }
        int flag = 1;//判断a数组的所有元素是否都相等
        for(int i = 2;i <= n;++i){
            if(a[i] != a[i - 1]){
                flag = 0;
                break;//有元素不相等 
            }
        } 
        if(flag == 1 && a[1] >= 0 && a[1] % (1 + n) == 0) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}