全部Wonderful Answer
2024-08-02 21:02:34
发布于:上海
25阅读
0回复
0点赞
输入样例,输出为”000000 00000 1000“,求大神指点
#include<bits/stdc++.h>
using namespace std;
string solve(vector<int> a,int n){
string result(n,'0');
vector<int> count(n+1,0);
int start=0,distinct=0;
for(int i=0;i<n;i++){
if(++count[a[i]]==1)
distinct++;
for(int m=1;m<=distinct&&m<=n;m++){
if(distinct==m&&count[1]==1&&count[m]==1){
bool flag=1;
for(int j=1;j<=m;j++){
if(count[j]!=1){
flag=0;
break;
}
}
if(flag==1)
result[m-1]='1';
}
while(distinct>m){
if(--count[a[start]]==0)
distinct--;
start++;
}
}
}
return result;
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
cout<<solve(a,n)<<endl;
}
return 0;
}
全部评论 1
当m变化时,实际上全排列的区间是从1所在位置不断向两边延伸的,在延伸时会优先选择数字比较小的一侧前进。所以,只需要模拟区间的范围变化,记录1~m范围内的数的个数,与m进行比较即可。
已经在区间内的数需要标记,每次区间变化时,查询变化后的m这个数是否被标记过,如果标记过也要计入范围内。2024-08-03 来自 浙江
0
有帮助,赞一个