P10665 [AMPPZ2013] Bytehattan 题解
Moya_Rao
·
·
题解
第一眼：时光倒流做完了，这有紫？？
第二眼：我丢强制在线，那咋办。
对啊那咋办。
当然是凉拌啦！
换个角度想想，我们可以画一个网格图出来然后模拟一下删边的过程，不难其实很难发现删边其实和合并两个格子是一样的效果。
最初这些格子都是互相分离的。
那么现在只需要思考在什么情况下，一条边两段的格点会从原本的连通变为不连通。
如果在合并这两个格子之前，**两个将要被合并的格子已经处于同一连通块了**，那么合并后必然会形成一个**环**，而这个环必然会**把环内外的格点分开**，使这条边两段的格点变得不连通了。否则没有分开情况发生，这两个格点还是连通的。
用并查集维护格子的连通情况即可。
忽略并查集常数 $\alpha(n^2)$ 的话，时间复杂度是 $O(k)$ 的，即 $O(n^2)$。
::::success[code && [submission](https://www.luogu.com.cn/record/276519011)]
```cpp
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 1505;
const int N2 = N*N;
int n,T,fa[N2],sz[N2],Ans=1;
int read(){
int su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
int node(int x,int y){return (x-1)*n+y;}
int FF(int u){return (fa[u]==u?u:fa[u]=FF(fa[u]));}
void Merge(int u,int v){
u=FF(u),v=FF(v);
if(u!=v)Ans=1,fa[v]=u,sz[u]+=sz[v];
else Ans=0;return;
}
int main(){
n=read(),T=read();
for(int i=1;i<n;i++)for(int j=1;j<n;j++)
fa[node(i,j)]=node(i,j),sz[node(i,j)]=1;
while(T--){
int x,y;char opt,tmp;
if(Ans){
x=read(),y=read();cin>>opt;
read(),read();cin>>tmp;
}else{
read(),read();cin>>tmp;
x=read(),y=read();cin>>opt;
}
if(opt=='N')Merge(node(x,y),node(x-1,y));
else Merge(node(x,y),node(x,y-1));
if(Ans)cout<<"TAK\n";
else cout<<"NIE\n";
}
return 0;
}
```
::::
笑点解析：
注意到 `u=fa[u],v=fa[v];`，我在写什么东西。
警示后人（？）。
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！