Codeforces Round 604 B. Beautiful Numbers
程序员文章站
2022-07-12 13:54:46
...
标题
题目要求
示例
input
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2
output
101011
11111
1001
解题思路
这个题一眼看上去似乎没什么思路,但是遇见这种有明显数字排列的问题,就要顺着题目,找一找数字之间的规律。
显然,这一题的规律体现在数组下标这里。
首先,设置一个b数组,用来监测a数组中1,2,3,4…n的位置。所以,让b[a[i]]=i。位置找好了,还要考虑怎么用。按照题目中给的例子,a[6]={4 ,5, 1, 3, 2, 6},b[6]={3,5,4,1,2,6}。题目中的l和r,首先是{3,3},然后{3,5},然后{1,5},然后{1,6},规律找到了!就是,遍历b从2到n(因为第一个一定为1,1是一定为美丽数的),找到最小的数字mi和最大的数字ma,然后,求出(ma-mi+1),与i做比较。小于等于的,为美丽数字,其他为“0”。
正确代码
#include <iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cstdio>
#include<string>
using namespace std;
typedef long long ll;
const ll maxn=2*1e5+7;
int a[maxn];
int b[maxn];
int main()
{
int t;
cin>>t;
while(t--){
int n;
memset(b,0,sizeof(b));
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[a[i]]=i;
}
cout<<1;
int ma=b[1],mi=b[1];
for(int i=2;i<=n;i++){
if(ma<b[i])ma=b[i];
else if(mi>b[i])mi=b[i];
if((ma-mi+1)>i)
cout<<0;
else //l-r+1=m,m是幸运数字;
cout<<1;
}
cout<<"\n";
}
return 0;
}
上一篇: 第九周作业
下一篇: IntelliJ IDEA 插件
推荐阅读
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #650 (Div. 3) B. Even Array
-
Codeforces Round #461 (Div. 2) B. Magic Forest(异或的性质)
-
【Codeforces Global Round 7】A. Bad Ugly Numbers 题解
-
Codeforces Global Round 7 A. Bad Ugly Numbers
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
Codeforces Round #670 (Div. 2) E. Deleting Numbers(交互,素数构造)
-
Codeforces Round 604 B. Beautiful Numbers
-
[几何] Codeforces 772B VK Cup 2017 - Round 2 B. Volatile Kite
-
Codeforces Round #663 (Div. 2) B. Fix You