全部Wonderful Answer

原题链接：1770.美丽数字

狐夏聆哲_Anarilune.

2024-08-02 21:02:34

发布于：上海

43阅读

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;  
}

有帮助，赞一个

去预览

0/2000

全部评论 2

无敌的鳖佬仔给老爷爷猜猜被

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    unordered_map<int, int> first_pos, last_pos;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (first_pos.find(a[i]) == first_pos.end()) {
            first_pos[a[i]] = i;
        }
        last_pos[a[i]] = i;
    }
    
    vector<int> ans(n, 0);
    int min_first = n, max_last = -1;    
    for (int m = 1; m <= n; ++m) {
        min_first = min(min_first, first_pos[m]);
        max_last = max(max_last, last_pos[m]);
        
        if (max_last - min_first + 1 == m) {
            ans[m - 1] = 1; 
        }
    }
    
    for (int num : ans) {
        cout << num;
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

2025-06-27 来自浙江

Sherry
当m变化时，实际上全排列的区间是从1所在位置不断向两边延伸的，在延伸时会优先选择数字比较小的一侧前进。所以，只需要模拟区间的范围变化，记录1~m范围内的数的个数，与m进行比较即可。
已经在区间内的数需要标记，每次区间变化时，查询变化后的m这个数是否被标记过，如果标记过也要计入范围内。

2024-08-03 来自浙江
0

全部评论 2

热门讨论