CF1341C. Nastya and Strange Generator（思维 模拟 构造）

linkkkk

题意：

给出nnn，要求将1n1~n1n的数放到nnn个位置，问给出的ppp数组能否按照如下规则放置得到。

规则是：rrr数组满足ri>=ir_i>=iri>=i并且rir_iri没有被占用，cic_ici

表示rrr数组里值为iii的数的个数。每次选择ccc数组的最大值放置对应的位置放置，如果有多个位置的话，任意选择一个放置。

思路：

模拟一下样例后发现，如果一个元素放在了第kkk个位置，那么下一个元素会放在第k+1k+1k+1个位置，因为这时候ck+1==2c_{k+1}==2ck+1==2。但是如果kkk是数组里最后一个位置呢，那么下一个位置就可以从前面的位置任意选择不受限制了。

用flagflagflag表示放置是否受到限制，如果kkk不是最后一个位置，那么下一个位置必须是k+1k+1k+1

代码：

#includeusingnamespacestd;constintmaxn=2e5+10,inf=0x3f3f3f3f;intn,p[maxn],st[maxn];intmain{int_;cin>>_;while(_--){cin>>n;for(inti=1;i<=n;i++)cin>>p[i],st[i]=0;intlas=n,flag=1,flag1=1;if(p[1]==las){flag=0;las--;}st[p[1]]=1;for(inti=2;i<=n;i++){st[p[i]]=1;if(flag){if(p[i]!=p[i-1]+1){flag1=0;break;}}if(p[i]==las){flag=0;while(st[las])las--;}elseflag=1;}if(!flag1)puts("No");elseputs("Yes");}return0;}

参考