Codeforces Round #525 (Div. 2) C——Ehab and a 2-operation task

Whiteying

2018-12-08 22:39:22

Personal

# A类 # 题目链接: http://codeforces.com/contest/1088/problem/C # 原题: You're given an array a of length n. You can perform the following operations on it: choose an index i (1≤i≤n), an integer x (0≤x≤106), and replace aj with aj+x for all (1≤j≤i), which means add x to all the elements in the prefix ending at i. choose an index i (1≤i≤n), an integer x (1≤x≤106), and replace aj with aj%x for all (1≤j≤i), which means replace every element in the prefix ending at i with the remainder after dividing it by x. Can you make the array strictly increasing in no more than n+1 operations? **输入格式:** The first line contains an integer n (1≤n≤2000), the number of elements in the array a. The second line contains n space-separated integers a1, a2, …, an (0≤ai≤105), the elements of the array a. **输出格式:** On the first line, print the number of operations you wish to perform. On the next lines, you should print the operations. To print an adding operation, use the format "1 i x"; to print a modding operation, use the format "2 i x". If i or x don't satisfy the limitations above, or you use more than n+1 operations, you'll get wrong answer verdict. **输入样例1:** 3 1 2 3 **输出样例1:** 0 **输入样例2:** 3 7 6 3 **输出样例2:** 2 1 1 1 2 2 4 ------------ # 题意: 对n个数进行操作,1操作是对1到i加x,2操作是对1到i模x,让你严格输出n+1此操作,让n个数严格递增。 # 思路: 对于n个数化成0,1,2……n-1,的形式,就是满足题意的。 如何化成以上形式呢? 如果一个数不是n的倍数的话,先将它补成n的倍数,然后再加上他的i-1,模n,就成为了i-1. 即先用n次操作变成模n递增,然后直接模n即可。 # AC代码: ``` #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; #include<algorithm> #include<queue> typedef long long ll; #include<vector> #define cin(n) scanf("%lld",&(n)) #define cout(n) printf("%lld",(n)) #define couc(c) printf("%c",(c)) #define coutn printf("\n") #define cout_ printf(" ") #define debug() printf("haha\n") const int MAXN= 1e6 + 5 ; ll t; ll n,k; ll b[MAXN]={1}; ll a[MAXN]={1,1,1,2,3}; ll rou=3; ll now=5; ll an; int main() { cin(n); for(int i=1;i<=n;i++) cin(a[i]); ll tmp=0; cout(n+1); coutn; for(int i=n;i>=1;i--) { ll x=(i-1)-(a[i]%n)+n; printf("1 %d %lld\n",i,x); for(int j=1;j<=i;j++) a[j]+=x; } printf("2 %lld %lld\n",n,n); return 0; } ```