欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #666 (Div. 2)C - Multiples of Length(错位相减)

程序员文章站 2022-06-26 11:34:43
...

problem

Codeforces Round #666 (Div. 2)C - Multiples of Length(错位相减)
给出N个数,可以进行三次操作,
每次选中一个区间,区间里任意一个元素可以加上一个区间长度的倍数(并且加的数可以互相不同)
让所有数变成0 求方案

solution

好久没打CF了,签到题一点都不友好。。。
这题好像错位相减,上一题等比数列,,这。。。

  • 题目规定了只有3次操作,加上是T3签到题,所以想到很可能是乱搞(强行操作)
  • 用掉两次操作减掉序列上每个位置的值,即 -a[i]*n,+a[i]*(n-1)这样作差。(本来n可以为任意值,此时考虑到为当前区间的长度,所以直接两次操作分别长为n和n-1)
  • 因为第二次加了n-1没加完,最后再加一次。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[100010];
int main(){
	int n; cin>>n;
	for(int i = 1; i <= n; i++)
		cin>>a[i];
	if(n==1){
		cout<<1<<" "<<1<<endl;
		cout<<0<<endl;
		cout<<1<<" "<<1<<endl;
		cout<<0<<endl;
		cout<<1<<" "<<1<<endl;
		cout<<-a[1]<<endl;
	}else{
		cout<<1<<" "<<n<<endl;
		for(int i = 1; i <= n; i++)cout<<(-1)*a[i]*n<<" ";cout<<endl;
		cout<<1<<" "<<n-1<<endl;
		for(int i = 1; i < n; i++)cout<<a[i]*(n-1)<<" ";cout<<endl;
		cout<<n<<" "<<n<<endl;
		cout<<a[n]*(n-1)<<endl;
	}
	return 0;
}
相关标签: 算法