# 考试策略

T1->T2->T5->T4->T3 这样的吧，除了 T3 以外的题目都还是很水滴! 只不过忽然对 T4 的 32M 空间表示疑惑了一下子而已。

# T1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
int n,m,p;
int f[5005];
int find(int x){
if(x==f[x])return x;
f[x]=find(f[x]);return f[x];
}
int main()
{
freopen("relation.in","r",stdin);
freopen("relation.out","w",stdout);
int x,y,i,r1,r2;
for(i=1;i<=n;++i)f[i]=i;
for(i=1;i<=m;++i){
r1=find(x),r2=find(y);
if(r1!=r2)f[r1]=r2;
}
for(i=1;i<=p;++i){
if(find(x)==find(y))printf("Yes\n");
else printf("No\n");
}
return 0;
}


# T2

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
int n,m,ans;
int f[4005],vis[4005];
int find(int x){
if(x==f[x])return x;
f[x]=find(f[x]);return f[x];
}
int main()
{
freopen("gangs.in","r",stdin);
freopen("gangs.out","w",stdout);
int i,r1,r2,x,y;char ch[5];
for(i=1;i<=n*2;++i)f[i]=i;
for(i=1;i<=m;++i){
if(ch[0]=='E'){
r1=find(x),r2=find(y+n);
if(r1!=r2)f[r1]=r2;
r1=find(x+n),r2=find(y);
if(r1!=r2)f[r1]=r2;
}
else {
r1=find(x),r2=find(y);
if(r1!=r2)f[r1]=r2;
}
}
for(i=1;i<=n;++i){
r1=find(i);
if(!vis[r1])vis[r1]=1,++ans;
}
printf("%d",ans);
return 0;
}


# T3

30% 的数据 n 小于等于 100，100% 的数据 n 小于等于 $2*10^5$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
const int N=400005;
int f[N<<1],s1[N],s2[N];
int xx[N],yy[N],a[N],b[N];
int n,t1=1,t2=1;LL ans;
int find(int x){
if(x==f[x])return x;
f[x]=find(f[x]);return f[x];
}
void work(){
int i,r1,r2;
for(i=1;i<=t1;++i)f[i]=i,s1[i]=1;
for(i=1;i<=t2;++i)f[i+t1]=i+t1,s2[i+t1]=1;
for(i=1;i<=n;++i){
xx[i]=lower_bound(a+1,a+1+t1,xx[i])-a;
yy[i]=lower_bound(b+1,b+1+t2,yy[i])-b;
r1=find(xx[i]),r2=find(yy[i]+t1);
if(r1!=r2)f[r1]=r2,s1[r2]+=s1[r1],s2[r2]+=s2[r1],s1[r1]=0,s2[r1]=0;
}
for(i=1;i<=t1+t2;++i)
if(find(i)==i)ans+=(LL)s1[i]*s2[i];
}
int main()
{
freopen("filling.in","r",stdin);
freopen("filling.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%d%d",&xx[i],&yy[i]);
a[i]=xx[i],b[i]=yy[i];
}
sort(a+1,a+1+n),sort(b+1,b+1+n);
for(i=2;i<=n;++i)
if(a[i]!=a[t1])a[++t1]=a[i];
for(i=2;i<=n;++i)
if(b[i]!=b[t2])b[++t2]=b[i];
work();printf("%lld",ans);
return 0;
}


# T4

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N=1000005;
int n,m;
int f[N];
int find(int x){
if(f[x]==x)return x;
f[x]=find(f[x]);return f[x];
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int i,r1,r2,x,y,xx,yy;char ch[5];
scanf("%d%d",&n,&m);
for(i=1;i<=n*n;++i)f[i]=i;
for(i=1;i<=m;++i){
scanf("%d%d%s",&xx,&yy,ch);
x=(xx-1)*n+yy;
if(ch[0]=='R')y=x+1;
else y=xx*n+yy;
r1=find(x),r2=find(y);
if(r1!=r2)f[r1]=r2;
else {printf("%d",i);return 0;}
}
printf("-1");
return 0;
}


# T5

Altman 神犇为了给你以表现机会，将这些信息都给你，并会时不时地问你两个怪兽之间谁更强。

Altman 们的信息的格式是 X A B C

Lyp 的询问的格式是：Y A B
Y 固定为 2，A,B 是怪兽编号，属于 1~n，如果 A 比 B 强，输出 A；如果 B 比 A 强，输出 B，如果无法判断或怪兽们一样强，输出 0

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N=30005;
int n,m;
int f[N],d[N];
int find(int x){
if(f[x]==x)return x;
int t=f[x];
f[x]=find(f[x]),d[x]+=d[t];
return f[x];
}
int main()
{
freopen("lyp.in","r",stdin);
freopen("lyp.out","w",stdout);
int i,bj,x,y,w,r1,r2;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)f[i]=i;
for(i=1;i<=m;++i){
scanf("%d",&bj);
if(bj==1){
scanf("%d%d%d",&x,&y,&w);
r1=find(x),r2=find(y);
if(r1!=r2)f[r1]=r2,d[r1]=d[y]-d[x]+w;
}
else {
scanf("%d%d",&x,&y);
r1=find(x),r2=find(y);
if(r1!=r2)printf("0\n");
else if(d[x]==d[y])printf("0\n");
else if(d[x]>d[y])printf("%d\n",x);
else if(d[x]<d[y])printf("%d\n",y);
}
}
return 0;
}