B - Beautiful Numbers

题意:给你一个n,和n个1-n的随机排列,从其中选出一段子序列,要使子序列是1-m顺序排列,则m为Beautiful Numbers,如果1-n是Beautiful Numbers则输出1,

否则输出0;

思路:将给的随机排列的位置存入一个数组p,例如1对应位置3,则p[1]=3,2对应位置4,则p[2]=4;

   对数组p逐一取子序列,用 l 始终标记序列开始位置,r始终标记序列结束位置,判断r-l+1是否于当前 i 。

B - Beautiful Numbers
#include<bits/stdc++.h>
#define N 2e5+10
using namespace std;
int main(){
        int t,i,n,p[int(N)],a,l,r;
        while(~scanf("%d",&t)){
                while(t--){
                        memset(p,0,sizeof(p));
                        scanf("%d",&n);
                        for(i=1;i<=n;i++){
                                scanf("%d",&a);
                                p[a]=i;
                        }
                        l=r=p[1];
                        printf("1");
                        for(i=2;i<=n;i++){
                                l=min(l,p[i]);
                                r=max(r,p[i]);
                                if(r-l+1==i)
                                        printf("1");
                                else    printf("0");
                        }
                        printf("\n");
                }
        }
}
View Code
上一篇:python----条件


下一篇:CF1155D Beautiful Array