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