[AGC068B] 01 Graph Construction

Genius_Star · 2026-09-02 11:05:09 · 题解

或许更好的阅读体验。

感觉挺脑电波的构造题，怎么场上被过穿了。

思路：

考虑初始构造 S 有 n 个 0，T 有 n 个 1，那么初始两边都有 n 个未匹配的位置；称作 p_1, \cdots, p_k 与 q_1, \cdots, q_k 吧，初始 k = n。

考虑给 S, T 右边分别加：

• 若给 S, T 末尾都加上 0，那么会连上 p_1 与 n + 1，然后 p 前面删掉 p_1，后面再加上一个 n + 1 没有被匹配，欸，你发现 p_1 与 n + 1 连通性一致，于是本质上是将 p_1, \cdots, p_k 换成 p_2, \cdots, p_k, p_1。

• 若给 S 末尾加 1，T 末尾加 0，相当于连边 p_1 与 n + 1，q_1 与 n + 1 连边，即合并了 p_1 与 q_1 的连通块；然后把 p_1, q_1 从 p, q 中删掉。

相当于你可以将 p 循环左移任意多次，于是你可以将 i 与任意 j 连边，于是对于限制的 A_i，我们把 A_i 相同的提出来，拿一个排列搞成置换环，设这个排列 X，表示 i 要连边 X_i。

于是对于 p_i, q_i 来说，只要 X_{q_i} = p_i，那么就加 10 连边，否则就加 00 把 p 循环左移即可。

时间复杂度为 O(n^2)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
#define popcnt(x) __builtin_popcountll(x)
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }  
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, k, m;
int p[N], q[N], a[N], X[N];
vector<int> V[N];
char s[N], t[N];
inline void del(){
    for(int i = 1; i < k; ++i)
      p[i] = p[i + 1], q[i] = q[i + 1];
    --k;
}
inline void left(){
    p[k + 1] = p[1];
    for(int i = 1; i <= k; ++i)
      p[i] = p[i + 1];
}
int main(){
    n = read();
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        V[a[i]].push_back(i);
    }
    for(int i = 1; i <= n; ++i)
      for(int j = 0; j < (int)V[i].size(); ++j)
        X[V[i][j]] = V[i][(j + 1) % V[i].size()];
    for(int i = 1; i <= n; ++i)
      p[i] = q[i] = i, s[i] = '0', t[i] = '1';
    k = m = n;
    while(k){
        if(X[q[1]] == p[1]){
            s[++m] = '1';
            t[m] = '0';
            del();
        }
        else{
            s[++m] = '0';
            t[m] = '0';
            left();
        }
    }
    write(m);
    putchar('\n');
    printf("%s\n%s\n", s + 1, t + 1);
    return 0;
}