C. Multiples of Length
题意
给出一个数组a 长度为n<1e5 任意元素-1e9<ai<1e9
要求3次操作将原数组变为全0数组
一次操作为：
选取一段区间[L,R] 将其中的数加上或减去 bi×(R-L+1)
输出每次操作的区间和对应位置的bi (bi可以为0)
题解
十分巧妙的构造
首先对[1,n-1]位置上的数-a[i]×(n-1) 那么对于第i位数则变为
a[i]-(n-1)×a[i]=n×a[i]
再令[n,n]位置变为n的倍数
两步操作后所有的数都变为了n的倍数
最后一步让[1,n]上的数-n的倍数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll Mod=1e9;
ll data[Max];
int main() {
Turnoff;
ll n;cin>>n;
for(int i=0;i<n;i++)cin>>data[i];
if(n==1){
cout<<1<<" "<<1<<endl;
for(int i=0;i<n;i++)cout<<0<<" ";
}
else {
cout<<1<<" "<<n-1<<endl;
for(int i=0;i<n-1;i++)cout<<(n-1)*data[i]<<" ";
}
cout<<endl;
cout<<n<<" "<<n<<endl;
cout<<n-data[n-1]<<endl;
cout<<1<<" "<<n<<endl;
for(int i=0;i<n-1;i++)cout<<-n*data[i]<<" ";
cout<<-n<<endl;
}
|