题解：CF2117D Retaliation

思路

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

给定数列

[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

。）

代码实现

CPP

#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;
}

题解：CF2117D Retaliation

文章操作

思路

代码实现

相关推荐

评论

题解：CF2117D Retaliation