本文共 3318 字,大约阅读时间需要 11 分钟。
题目来源:
Description
You are given a permutation p=[p1,p2,…,pn] of integers from 1 to n. Let’s call the number m (1≤m≤n) beautiful, if there exists two indices l,r (1≤l≤r≤n), such that the numbers [pl,pl+1,…,pr] is a permutation of numbers 1,2,…,m.
For example, let p=[4,5,1,3,2,6]. In this case, the numbers 1,3,5,6 are beautiful and 2,4 are not. It is because:
it is impossible to take some l and r, such that [pl,pl+1,…,pr] is a permutation of numbers 1,2,…,m for m=2 and for m=4.
You are given a permutation p=[p1,p2,…,pn]. For all m (1≤m≤n) determine if it is a beautiful number or not.Input
The first line contains the only integer t (1≤t≤1000) — the number of test cases in the input. The next lines contain the description of test cases.
The first line of a test case contains a number n (1≤n≤2⋅105) — the length of the given permutation p. The next line contains n integers p1,p2,…,pn (1≤pi≤n, all pi are different) — the given permutation p.
It is guaranteed, that the sum of n from all test cases in the input doesn’t exceed 2⋅105.
Output
Print t lines — the answers to test cases in the order they are given in the input.
The answer to a test case is the string of length n, there the i-th character is equal to 1 if i is a beautiful number and is equal to 0 if i is not a beautiful number.
Sample Input
3
6 4 5 1 3 2 6 5 5 3 1 2 4 4 1 4 3 2Sample Output
101011
11111 1001Note
The first test case is described in the problem statement.
In the second test case all numbers from 1 to 5 are beautiful:
解题思路:
排序后维护最大值位置mx和最小值位置mi,i=0依次遍历,当mx-mi==i时代表成立,反之为0;
具体看代码。AC代码1:
#includeusing namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 2e5+5;pair arr[MAXN]; int main(){ SIS; int T,n,x; cin >> T; while(T--) { cin >> n; int mi=0x3f3f3f3f,mx=0; for(int i=0;i > arr[i].first; arr[i].second=i; } sort(arr,arr+n); vector v(n); for(int i=0;i
仔细一想本题输入的是1-n的n个不重复的数,所以根本不需要排序。
AC代码2:
#includeusing namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 2e5+5;int arr[MAXN];int main(){ SIS; int T,n,x; cin >> T; while(T--) { cin >> n; int mi=0x3f3f3f3f,mx=0; for(int i=1;i<=n;i++) { cin >> x; arr[x]=i; } vector v(n); for(int i=1;i<=n;i++) { mi=min(arr[i],mi); mx=max(arr[i],mx); if(mx-mi==i-1) v[i-1]=1; else v[i-1]=0; } for(auto x:v) cout << x; cout << endl; } return 0;}
转载地址:http://eiyof.baihongyu.com/