Solution. CF1710D Recover the Tree

Description

根据以下信息构造一棵树：

• 树的节点个数为 $n$，编号为 $1\sim n$。
• 对于每个编号区间 $[l,r]$ 给出是否构成连通块。

$n\le 2000$

Solution

难得做出了 3400 的构造，很有意思的题目。

从小到大考虑每个好区间。

当 $r=l+1$ 时，如果构成连通块，则必然有 $l\to l+1$ 的连边。

对于长度为 $d$ 的好区间 $[l,r]$，此时所有长度 $<d$ 的好区间都已经满足题意，首先由于我们的构造方式，所有的连通块都是区间。假如 $l,r$ 处于不同的连通块，我们会连一条 $l\to r$ 的边将两个连通块合并，注意此时在 $l,r$ 所在的连通块之间还可能存在一些散块，我断言散块的数量不可能为 $1$，否则显然无解，既然散块的数量大于 $1$，容易想到构造左往右连、右往左连这样的交叉连边，这样如果不同时包含 $l,r$，任取若干散块，他们仍然不连通，于是就保证了不会破坏较小区间的正确性。

实现细节略去，代码十分易懂。

值得一提的是，枚举所有好区间的复杂度是 $\mathcal O(n^2)$，而对于每个尚未连通的好区间，我们都暴力遍历了区间中的每个点检查连通性，尽管如此，由于每次暴力遍历都至少会连一条边，而树上的总边数是 $n-1$，故总复杂度是正确的 $\mathcal O(n^2)$。

Code

namespace Main{
    const int N = 2005;
    int t, n, fa[N];
    char con[N][N];
    int get(int x){
        if(fa[x] == x) return x;
        return fa[x] = get(fa[x]);
    }
    void unite(int x, int y){
        fa[get(x)] = get(y);
    }
    void Main(){
        input(t);
        while(t--){
            input(n);
            for(int i = 1; i <= n; i++) scanf("%s", con[i] + 1);
            for(int i = 1; i <= n; i++) fa[i] = i;
            for(int i = 2; i <= n; i++){
                for(int j = 1; j + i - 1 <= n; j++){
                    int k = j + i - 1;
                    if(con[j][i] != '1' || get(j) == get(k)) continue;
                    unite(j, k);
                    write(j), putchar(' '), write(k), puts("");
                    bool fir = true;
                    for(int p = j + 1; p < k; p++){
                        if(get(p) != get(j)){
                            if(fir){
                                write(p), putchar(' '), write(k), puts("");
                                unite(p, k);
                                fir = false;
                            }
                            else{
                                write(p), putchar(' '), write(j), puts("");
                                unite(p, j);
                            }
                        }
                    }
                }
            }
        }
        return;
    }
}

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。