题目链接:http://codeforces.com/contest/1088/problem/C
题目大意:给你长度为n一个序列,你有两种操作
操作1:选择一个坐标i,对于对所有j<=i, a[j]+=x, 0≤x≤10^6
操作2:选择一个坐标i,对于对所有j<=i, a[j]%=x, 1≤x≤10^6
现在让你最多进行n+1次操作,让你输出操作,让序列成为一个严格单增的序列的每一次操作。
输出:k次操作
对于操作的输出格式:操作 i x
思路:我们开始想到就进行n+1次操作。用n次操作1,1次操作2。然后就从前往后构造0到n-1。一直有问题,构造后面的时候,无法消除对前面数字的影响。然后队友突然冒出来一句必须从前往后构造,好了,我的思路可以AC了。先从后往前构造把第i数字构造成 i+k*n(k>=0的整数),然后再全部%n就OK了。
思考:第一次做这样的题,不太熟练,尤其是怎么消除对已经构造好的数字的影响。这次学到了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[2005];
int main()
{
ll n, q=1;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(i!=1&&a[i]<=a[i-1])
{
q=0;
}
}
if(q)
{
printf("0\n");
return 0;
}
for(int i=1;i<=n;i++)
a[i]%=n;
ll p=n-1, k=0;/*p当前数字应该构造的数字*/
if(n==1)
{
printf("0\n");
return 0;
}
printf("%lld\n",n+1);
for(int i=n;i>=1;i--)
{
a[i]=(a[i]+k)%n;
if(a[i]<p)
{
printf("1 %d %lld\n",i, p-a[i]);
k+=p-a[i];
k%=n;
}
else if(a[i]==p)
{
printf("1 %d 0\n",i);
p--;
continue;
}
else
{
printf("1 %d %lld\n",i, p-a[i]+n);
k+=p-a[i]+n;
k%=n;
}
p--;
}
printf("2 %lld %lld\n",n, n);
return 0;
}