\(\texttt{「CF1710D」Recover the Tree}\)
\(\texttt{Solution}\)
考虑好区间 \(I_1,I_2(I_1\cap I_2\not=\empty)\)，\(I_1\cap I_2\) 和 \(I_1\cup I_2\) 都是好区间。于是我们考虑从长度小开始构建。
初始时我们把 \(n\) 个点看作 \(n\) 个连通分量，设 \([lv_i,rv_i]\) 表示点 \(i\) 所属连通分量的区间。
枚举到区间 \([L,R]\) 时，如果 \([L,R]\) 不连通或 \([L,R]\) 已经连通则不考虑。否则我们需要将 \(L\) 所属连通分量和 \(R\) 所属连通分量含有 \([L,R]\) 中不属于两个连通分量的部分连通。我们可以考虑如下连通方案。设 \([L,R]\) 由 \(k+2\) 个连通分量组成，分别为 \([l_0,r_0],[l_1,r_1],\cdots,[l_{k+1},r_{k+1}]\)，同时设 \(x\in [l_0,r_0],y\in [l_{k+1},r_{k+1}]\)。连接方式如下
\[-\cdots-l_{2k}-\cdots-l_4-l_2-x-y-l_1-l_3-\cdots-l_{2k+1}-\cdots \]即为下图
\(\texttt{Code}\)
点击查看代码
#include<bits/stdc++.h>
#define MOD (1000000007)
#define ll long long
#define MAXN (2005)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(x) (x&-x)
#define Swap(x,y) (x^=y,y^=x,x^=y)
using namespace std;
void read(ll &x)
{
register char ch=0;register bool f=0;x=0;
while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=f?-x:x;
}
void read(int &x)
{
register char ch=0;register bool f=0;x=0;
while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=f?-x:x;
}
void write(ll x,bool bk)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(!x)
{
if(!bk) putchar('0');
return;
}
write(x/10,1);
putchar((x%10)^48);
}
void print(ll x,char ch)
{
write(x,0);
if(ch) putchar(ch);
}
struct out{
ll x,y;
};
vector<out> ans;
int n;
int res[MAXN][MAXN],lv[MAXN],rv[MAXN];
char g[MAXN][MAXN];
void solve()
{
ans.clear();
read(n);
for(int i=1;i<=n;i++)
{
lv[i]=i,rv[i]=i;
scanf("%s",g[i]+i);
}
for(int len=2;len<=n;len++)
{
for(int l=1;l<=n-len+1;l++)
{
int r=l+len-1;
if((!(g[l][r]^'1'))&&(lv[l]^rv[r])&&(rv[l]^rv[r]))
{
ans.push_back((out){l,r});
vector<int> tmp[2];
int id=1;
tmp[0].push_back(l);
tmp[1].push_back(r);
for(int i=rv[l]+1;i<lv[r];i++)
{
if(!(lv[i]^i))
{
ans.push_back((out){tmp[id].back(),i});
tmp[id].push_back(i);
id^=1;
}
}
int L=lv[l],R=rv[r];
for(int i=L;i<=R;i++)
{
lv[i]=L;
rv[i]=R;
}
}
}
}
for(auto x:ans)
print(x.x,' '),print(x.y,'\n');
return;
}
int T;
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
read(T);
while(T--) solve();
return 0;
}