T2

2huk · 2023-10-05 19:13:04 · 个人记录

Description

你需要构造一个长度为 n 的序列，使得其在满足以下 m 个条件的情况下字典序最小。

其中第 i 个条件形如 x_i, y_i, z_i，表示 x_i 和 y_i 的最长公共前缀的长度为 z_i。

Solution

首先显然的是，既然 x 和 y 的最长公共前缀的长度为 z，那么也就是说 s_x = s_y，且 s_{x + 1} = s_{y + 1}，以此类推，直到 s_{x + z - 1} = s_{y + z - 1}。注意这里还有一个隐藏条件，也就是 s_{x + z} \ne s_{y + z}。这里的证明可以利用反证法：若 s_{x + z} = s_{y + z}，那么 x 和 y 的最长公共前缀的长度必定 \ge z + 1，与最长公共前缀 =z 的事实不符。

利用这个关系，我们就可以把题目转化成另外一个题目：仍然需要构造一个长度为 n 的字典序最小的序列，使得某些位置上的数一定相同且某些位置上的数一定不同。

考虑将其转化成图论问题。第一步，我们将所有有着相同值的位置连边，那么图中就会产生若干个连通块，每个连通块中的节点的值都应该被构造成相同的。此时可以自然的想到把一个连通块（即，一个强连通分量）缩成一个点，然后继续接下来的操作。缩点显然可以使用 Tarjan 算法。

第二步，我们对于那些要求一定不同的点再次连边。但此时图上的点已经不是原来的点，而是原来的强连通分量，所以我们假设要连接 x 和 y，就需要找到 x 和 y 分别所属的强连通分量（此时这个强连通分量已经缩成了一个点）并连边。这样我们就把图建好了。

最后我们需要在图上把每个强连通分量赋值（因为一个强连通分量内的点的值都是相同的，所以为强连通分量赋值就相当于为这些值相同的点赋值）。由于我们要让最终的答案序列的字典序最小，也就是说我们首先要让 1 所在的强连通分量的答案最小，再让 2 所在的强连通分量的答案最小，以此类推。注意这里求每个强连通分量的答案时，这个分量不能与别的与它相邻的分量的值相同（根据我们的建图规则）。因此我们在给一个分量赋答案值时需要找到一个值，使得这个值时与自己相邻的且已经被确定的答案的分量的答案均不同且最小。这显然就是一个 \operatorname{mex} 值。然后从小到大确定所有分量的答案即可。

代码

丢了。

#include <bits/stdc++.h>

using namespace std;

const int N = 2010, M = N * N;

int n, m, cnt;
array<int, 3> p[N];
int id[N], f[N];

struct Gragh {
    int h[N], e[M], ne[M], idx;

    Gragh() {
        memset(h, -1, sizeof h);
    }

    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
        e[idx] = a, ne[idx] = h[b], h[b] = idx ++ ;
    }

    int dfn[N], low[N], stk[N], top, ts;
    bool st[N];
    void dfs(int u) {
        dfn[u] = low[u] = ++ ts;
        stk[ ++ top] = u, st[u] = true;

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (!dfn[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            }
            else if (st[v]) low[u] = min(low[u], dfn[v]);
        }

        if (dfn[u] == low[u]) {
            int y;
            ++ cnt;
            do {
                y = stk[top -- ];
                st[y] = false;
                id[y] = cnt;
            } while (y != u);
        }
    }

    void Tarjan() {
        for (int i = 1; i <= n; ++ i )
            if (!dfn[i]) dfs(i);
    }

}G1, G2;

int main() {
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; ++ i ) {
        cin >> p[i][0] >> p[i][1] >> p[i][2];
        for (int j = 0; j < p[i][2]; ++ j ) G1.add(p[i][0] + j, p[i][1] + j);
    }

    G1.Tarjan();

    for (int i = 1; i <= m; ++ i )
        if (p[i][0] + p[i][2] <= n && p[i][1] + p[i][2] <= n) {
            if (id[p[i][0] + p[i][2]] == id[p[i][1] + p[i][2]]) {
                puts("-1");
                return 0;
            }
            G2.add(id[p[i][0] + p[i][2]], id[p[i][1] + p[i][2]]);
        }

    memset(f, -1, sizeof f);

    for (int u = 1; u <= n; ++ u )
        if (f[id[u]] == -1) {
            set<int> S;

            for (int i = G2.h[id[u]]; ~i; i = G2.ne[i]) {
                int v = G2.e[i];
                if (~f[v]) S.insert(f[v]);
            }

            for (int i = 0; ; ++ i )
                if (!S.count(i)) {
                    f[id[u]] = i;
                    break;
                }
        }

    for (int i = 1; i <= n; ++ i ) cout << f[id[i]] << ' ';

    return 0;
}