题解 | #小红的字符串构造#

H - 小红的字符串构造

高斯消元的解法

每个位置我们要么选 ，要么选 ，我们不妨先全部选 ，然后考虑翻转一些位置（即选 ）。

用 表示当前 26 个字母数量的奇偶性，当我们翻转 号位置时，会同时翻转 和 。

注意到翻转 和 翻转 的作用相同，所以一个翻转操作可以表示成 <> ，并且同一类型的操作进行两次相当于没有翻转。

于是我们可以统计 表示是否可以操作 <>。

我们设 表示最终是否操作无序对 <>，于是可以列出如下方程：

如果解方程得到所有 ，若 ，那就说明翻转过 <>，随意找个 的位置选择 即可。 上述推理过程是充要的，如果方程无解，那么原问题也就无解。

我们只关注 的奇偶性，可以使用 优化高斯消元。

复杂度

代码如下：

#include<iostream>
#include<bitset>
using namespace std;
using ll=long long;

constexpr int N = 26;
int ed[26], cnt[26][26], pos[26][26];

struct Gauss {// index-0
    bitset<N*N+1> A[N];// 第m列是常数列
    int x[N*N];
    void print(int n,int m) {
        cerr<<endl<<n<<"*"<<m<<" Matrix:"<<endl;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<m; ++j)
                cerr<<A[i][j];
            cerr<<A[i][m]<<endl;
        }
    }
    bool solve(int n,int m) {
        int c=0, r=0;
        for(; r<n && c<m; ++r, ++c) {
            int r1=-1;
            for(int i=r; i<n; ++i)
                if(A[i][c]) {
                    r1=i;
                    break;
                }
            if(r1==-1) {
                --r;
                continue;
            }
            if(r1!=r)
                swap(A[r],A[r1]);
            for(int i=0; i<n; ++i) {
                if(i==r || !A[i][c]) continue;
                A[i]^=A[r];
            }
        }
        for(int i=r; i<n; ++i)
            if(A[i][m])
                return false;
        for(int i=0,j=0; j<m; ++i,++j) {
            while(j<m && (i>=n||!A[i][j]) )
                x[j++]=0;// free
            if(j<m)
                x[j]=A[i][m];
        }
        return true;
    }
} g;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    for(int i=0; i<n; ++i) {
        ed[a[i]-'a']^=1;
        int x=a[i]-'a';
        int y=b[i]-'a';
        if(x>y) swap(x,y);
        if(x<y) cnt[x][y]++, pos[x][y]=i;
    }

    int nn=0;
    for(int i=0; i<26; ++i) {
        for(int j=0; j<26; ++j) {
            if(cnt[i][j]) {
                g.A[i][nn]=1;
                g.A[j][nn]=1;
                nn++;
            }
        }
    }
    for(int i=0; i<26; ++i)
        if(ed[i])
            g.A[i][nn]=1;
    
    // g.print(26,nn);
    if(g.solve(26,nn)) {
        int nn=0;
        for(int i=0; i<26; ++i) {
            for(int j=0; j<26; ++j) {
                if(cnt[i][j]) {
                    if(g.x[nn])
                        swap(a[pos[i][j]], b[pos[i][j]]);
                    nn++;
                }
            }
        }
        cout<<a;
    }else {
        cout<<"-1\n";
    }
    return 0;
}
/*




*/