AtCoder Regular Contest 151

A. Equal Hamming Distances

简单题，注意下答案需要字典序最小即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define ll long long

signed main()
{
    int n;
    string a, b;
    cin >> n >> a >> b;
    int cnt(0);
    rep(i, 0, n - 1) if (a[i] != b[i]) cnt++;
    if (cnt % 2) cout << -1 << endl;
    else
    {
        string ans(a);
        int s1 = 0, s2 = 0; cnt /= 2;
        rep(i, 0, n - 1)
        {
            if (a[i] != b[i])
            {
                if (a[i] == '0')
                {
                    if (s1 < cnt) s1++;
                    else
                    {
                        ans[i] = b[i];
                        s2++;
                    }
                }
                else
                {
                    if (s2 < cnt)
                    {
                        s2++;
                        ans[i] = b[i];
                    }
                    else s1++;
                }
            }
            else ans[i] = '0';
        }
        cout << ans << endl;
    }
}

B. A < AP

知识点：计数，并查集
复杂度：\(O(n)\)

一开始被题目吓住了，以为要上带权并查集，后来发现只需要维护连通块的个数即可

枚举 \(A\) 中第一个满足 \(A_i<A_{P_i}\) 的位置
那么对所有的 \(1\) 到 \(i-1\) 都要满足 \(A_i=A_{P_i}\)
我们将之前的 \(j\) 和 \(p_j\) 使用并查集合并
那么此时符合题意的数列个数为 \(C_m^2×m^{cnt-2}\)
\(cnt\) 为连通块个数

注意 \(i\) 和 \(p_i\) 可能一开始就连通，所以要用并查集维护

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,l,r) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;

const int mod = 998244353;
const int N = 2e5 + 5;

int f[N];
void init(int n) { iota(f, f + n + 1, 0); }
int find(int u)
{
    if (f[u] == u) return u;
    return f[u] = find(f[u]);
}
bool link(int u, int v)
{
    int fu = find(u), fv = find(v);
    if (fu == fv) return false;
    f[fu] = fv;
    return true;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    ll n, m;
    cin >> n >> m;
    init(n);
    vc<ll> p(n + 1), pow_m(n + 1);
    pow_m[0] = 1;
    rep(i, 1, n)
    {
        cin >> p[i];
        pow_m[i] = pow_m[i - 1] * m % mod;
    }
    ll cm2 = m * (m - 1) / 2 % mod;
    int cnt = n;
    ll ans = 0;
    for (int t = 1; t <= n; t++) if (link(t, p[t]))
    {
        ans = (ans + cm2 * pow_m[cnt - 2]) % mod;
        cnt--;
    }
    cout << ans << endl;
}