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

· · 个人记录

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