B.Beautiful Numbers

Codeforces Round #604 (Div. 2)

题目链接:https://codeforces.com/contest/1265/problem/B

题目描述:

假设p=[p1,p2,…,pn]是一个从1到n的整数的排列,如果存在两个指标l,r(1≤l≤r≤n),使得[pl,pl+1,…,pr]是数字1,2,…,m的排列,我们称这个数字m(1≤m≤n)是漂亮的。
例如,令p=[4,5,1,3,2,6]。在这种情况下,数字1、3、5、6是漂亮的,而2、4不是。这是因为:
如果l=3, r=3,我们将得到m=1的置换[1];
如果l=3, r=5,则m=3有一个置换[1,3,2];
如果l=1, r=5,我们将得到m=5的置换[4,5,1,3,2];
如果l=1, r=6,我们将得到m=6的置换[4,5,1,3,2,6];
取一些l和r是不可能的,比如[pl,pl+1,…,pr]是数字1、2、…的排列,m表示m=2,m表示m=4。
你得到一个排列p=[p1,p2,…,pn]。对于所有的m(1≤m≤n),判断它是否是一个美丽的数字。

输入

第一行包含唯一的整数t(1≤t≤1000)——输入的测试用例的数量。接下来的几行包含测试用例的描述。
测试用例的第一行包含一个n(1≤n≤2e5)——p的长度。下一行包含n个整数p1, p2,…, pn(1≤π≤n,π是不同的),给定的排列p。它保证,n的总和所有测试用例的输入不超过2e5。

输出

打印t行——测试用例的答案,按照输入的顺序排列。
测试用例的答案是长度为n的字符串,如果i是一个漂亮的数字,第i个字符等于1如果i不是一个漂亮的数字,第i个字符等于0。

代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int t,n;
const int maxn=2e5+5;
int p[maxn];
int m[maxn];
int main(){
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d",&t);
    while(t--){
        memset(m,0,sizeof(m));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&p[i]);
            m[p[i]]=i;            //记录p[i]的位置
        }
        int maxx,minn;
        minn=maxx=m[1];
        printf("1");                   //p[i]==1,1是漂亮数字,第一个输出一定是1
        for(int i=2;i<=n;i++){              //m[i]是i在p数组里的位置
            minn=min(minn,m[i]);           //1~i数字在p数组里最left的位置
            maxx=max(maxx,m[i]);           //1~i数据在p数组里最right的位置
            if(maxx-minn>=i){               //1~i数据在p数组里的left到ight的差>=i,i不是漂亮数字,第i位输出0
                printf("0");
            }
            else{
                printf("1");
            }
        }
        printf("\n");
    }
    return 0;
}
Last modification:December 6th, 2019 at 11:28 pm
如果觉得我的文章对你有用,请随意赞赏