题解 | 小红的排列构造②

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<ll>
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define pq priority_queue
#define endl '\n'
#define Hashset unordered_set
#define Hashmap unordered_map
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define ull unsigned long long
int n;
string s;
void R(int l,int r,vi &nums){
    while(l<r){
        swap(nums[l],nums[r]);
        l++;
        r--;
    }
}
void sol(){
    cin >> n;
    cin >> s;
    if(s[s.size()-1]=='0'){
        cout << -1 << endl;
        return;
    }
    vi nums(n,0);
    for(int i=0;i<n;i++){
        nums[i]=i+1;
    }
    int zero_pos=-1;
    int one_pos=-1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'&&zero_pos==-1){
            zero_pos=i;
        }
        else if(s[i]=='1'&&zero_pos!=-1){
            one_pos=i;
            R(zero_pos,one_pos,nums);
            zero_pos=-1;
        }
    }
    for(int i=0;i<s.size();i++){
        if(i)cout << " ";
        cout << nums[i];
    }
    cout << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    //cin >> T;
    while(T--){
        sol();
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define um unordered_map
#define us unordered_set
int n;
string s;
bool ans = false;
bool check(vi& nums) {
    us<int>Hashset;
    us<int>n;
    for (int i = 0; i < nums.size(); i++) {
        Hashset.insert(i + 1);
        n.insert(nums[i]);
        if ((s[i] == '0' && Hashset != n) || (s[i] == '1' && Hashset == n)) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}
void Swap(int p1, int p2, vi& nums) {
    int temp = nums[p1];
    nums[p1] = nums[p2];
    nums[p2] = temp;
}
void f(int i, vi& nums) {
    if (i == n) {
        if (check(nums)) {
            ans = true;
            for (int i = 0; i < n; i++) {
                if (i) cout << " ";
                cout << nums[i];
            }
            cout << endl;
        }
        return;
    }
    for (int j = i; j < nums.size(); j++) {
        Swap(j, i, nums);
        f(i + 1, nums);
        Swap(j, i, nums);
    }
}
void sol() {
    cin >> n;
    cin >> s;
    vi nums(n, 0);
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    f(0, nums);
    if (!ans)cout << -1 << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--)sol();
    return 0;
}

对于一般构造题而言，即使推理和洞察能力不强也可以尝试打表找规律，利用递归DFS全排列出n的排列然后与字符串s进行校验，正确则返回，打表后发现对于最简单的排列123...n（这边可能有更好的发现）而言0000...1这样的多0末尾1区间进行翻转就是一种答案