CF1710D Recover the Tree

CF1710D

有一棵 \(n\) 个节点的树,对于每一个区间 \([l,r]\),给定区间里的点是否联通,试构造出一棵合法的树。


一道很趣味的题目。

对于一棵树和区间的关系,总是会想到 dfs 序,如果一个区间里的点都联通,那么可以把这个区间划分成一棵子树。

但是这一题中只靠 dfs 序并没法做很好的逆向,因为如果一个区间里的点都联通,不代表着其中任意一个子区间都联通。

给定的是树,但是限制是区间的,这两个并没有很好的关系。考虑先从区间着手。

将树上的节点按照编号顺序写成一行,对于每一个点,记录当前这个点能到达的最远点 \(nxt_i\)。从大到小枚举左端点,从小到大枚举右端点。

对于当前区间 \([l,r]\),如果钦定区间里的点联通,且 \(nxt_l< r\),说明该区间目前还不连通,可以通过连接 \((l,r)\) 使得 \(l\) 所在的连通块和 \(r\) 所在的连通块联通,但是有可能区间中间还有更多连通块。直接连是不对的,因为这样会导致违反限制,但是有一个非常巧妙的连接方案可以使得让区间联通,且不与限制矛盾,具体来说:

考虑区间 \([1,9]\),可以根据当前图的情况推断出一些限制:比如 \([1,3]\) 不连通(如果联通肯定就已经连起来了),\([3,7]\) 不联通。

还是要先连 \((1,9)\),考虑如何把中间的串起来,容易发现直接连 \((2,3),(3,4),(5,6)\dots\) 是不行的,正确的连法是这样的:

这样构造可以使得中间的部分要想联通必须经过 \(l,r\)

当然,利用这个思想,还可以搞出一些其他的构造方法(比如可以使用和原策略对称的方法)

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define elif else if
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
void fileio(const string &s)
{
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
const int INF=4e18;
inline int read()
{
int x=0;
bool flag=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
flag=0;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return (flag?x:~(x-1));
}
int T,n,nxt[2001];
char s[2001][2001];
void solve()
{
n=read();
for(int i=1;i<=n;i++)
scanf("%s",s[i]);
for(int i=1;i<=n;i++)
nxt[i]=i;
for(int l=n;l;l--)
for(int r=l;r<=n;r++)
if(s[l][r-l]=='1'&&nxt[l]<r)
{
cout<<l<<' '<<r<<'\n';
if(nxt[nxt[l]+1]+1<r)
{
cout<<nxt[l]+1<<" "<<r<<'\n';
for(int i=nxt[nxt[l]+1]+1;i<r;i++)
if(nxt[i]==i)
cout<<l<<" "<<i<<'\n';
}
for(int i=l;i<=r;i++)
nxt[i]=nxt[r];
}
}
signed main()
{
T=read();
while(T--)
solve();
return 0;
}

总结:这一题之所以比较难想,是因为在构造树的目标和区间的限制中,往往会朝着树的方向,而忽略了区间的一些性质。但是在这一题中树其实只起到了联通块的作用,区间才是问题的关键。


CF1710D Recover the Tree
https://shmilyty.cf/cf1710d/
作者
ShmilyTY
发布于
2022年10月8日
许可协议