题解：CF2117D Retaliation

Luojt95 · 2025-09-26 18:20:18 · 题解

题目传送门。

AC记录。

思路

发现大家的思路都比较难理解，本蒟蒻写一篇较详细的题解。

给定数列 [a_1,a_2\cdots ,a_n] 每一次都要求进行以下两个操作中的一个：

• 对 a 中所有的下标 i，令 a_i 自减 i。
• 对 a 中所有的下标 i，令 a_i 自减 n-i+1。

不难发现，操作 1 中，下标越大，减的越多，操作 2 反之。

因此，如果数列递增，就进行操作 1，数列递减，就进行操作 2，直到每个元素都相等。如果无法相等，或有数字为负，就说明数组无法爆炸。

然后，重复轮流进行操作 1 和操作 2，直到数组爆炸，如果出现负数，说明数组无法爆炸。（因为进行两个操作以后，每个元素都会减 n+1。）

代码实现

#include<bits/stdc++.h>
using namespace std;
int t;
int n,a[200005];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int k=abs(a[1]-a[2]);//可以爆炸的数组一定是等差数列，因此 abs(a[1]-a[2]) 就决定了要做几次操作1/操作2，读者自证不难
        if(a[1]<a[2]) for(int i=1;i<=n;i++) a[i]-=k*i;//操作1
        else for(int i=1;i<=n;i++) a[i]-=k*(n-i+1);//操作2
        bool flag=true;//进行k轮后，判断数组是否为预期的每个元素都相等
        for(int i=2;i<=n;i++) if(a[i]!=a[1]) flag=false;
        if(flag&&a[n]>=0&&a[n]%(n+1)==0) cout<<"YES\n";//判断元素不为负数，判断元素能不能被 n+1 整除（每两次操作减 n+1）
        else cout<<"NO\n";
    }
    return 0;
}