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

传送门

题目意思就是给一个长度为n的序列,然后你有2种操作,一种是对前i个数加上x,一种是对前i个数模x,然后问能否在n+1步内把序列变成严格递增序列。

思路:首先对于任意序列是肯定能在n+1步内把序列变成严格递增序列。具体讲就是把每个ai变成i,要想达到这个目的,第一步是要对前n个数加上一个值maxn,然后从第一个数往第n个数进行如下处理,对每个数ai模上ai-i,那么ai就变成i了,然后为了防止对i位置进行模操作时可能影响了前面i-1个数,因为i-1可能会大于ai-i,这样的话a[i-1]可能就不等于i-1了,所以要保证ai-i大于i-1,那么就要让maxn取一个大数1e5就可以了,这样的话i-1都小于ai-i了,那么i-1位置前面的数i-2,i-3,直到1也必定是小于ai-i的了,这样对ai模上ai-i就不会对前面已经安排好了的i-1个数造成影响了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int a[2005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<n+1<<endl;
    cout<<"1 "<<n<<" "<<maxn<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<"2 "<<i<<" "<<maxn+a[i]-i<<endl;
    }
    return 0;
}
原文地址:https://www.cnblogs.com/eason9906/p/11754833.html