道理我都懂，但是这个网站好卡。
并查集
感觉好难，啥也不会。
T1
很显然gcd不等于1的数应该被并在一起（我都能看出来）。并完之后连通块个数的二次方-2（删去两个空集）就是答案。
code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int t,n,a[N],f[N],sum;
int find(int x){
if (f[x]==x){
return x;
}
return f[x]=find(f[x]);
}
void merge(int x,int y){
x=find(x);
y=find(y);
f[x]=y;
return;
}
int gcd(int x,int y){
if (y==0){
return x;
}
return gcd(y,x%y);
}
signed main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&t);
while (t--){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i]=i;
}
sum=0;
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
int ai=a[i],aj=a[j];
if (ai<aj){
swap(ai,aj);
}
if (gcd(ai,aj)!=1){
merge(i,j);
}
}
}
for (int i=1;i<=n;i++){
if (find(i)==i){
sum++;
}
}
int ans=1;
for (int i=1;i<=sum;i++){
ans=ans*2%mod;
}
printf("%d\n",ans-2);
}
return 0;
}
但是众所周知这样做的时间复杂度是O(n^2)，非常的慢。
优化思路大体是枚举每个数的倍数并将这个数与其倍数连在一起，然后再求连通块。还没打。
T2
带权并查集，权是每个点到其父亲的距离。
对于任意s和t，若它们在同一个集合中，则判断它们之间的距离是否与v相等（可以利用前缀和）；反之则将它们合并入同一个集合。
code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010,M=5e4+10;
int w,n,m,s[M],t[M],v[M],fa[N],dis[N];
int find(int x){
if (fa[x]==x){
return x;
}
int faa=find(fa[x]);
dis[x]+=dis[fa[x]];
return fa[x]=faa;
}
void merge(int x,int y,int vv){
int xx=find(x),yy=find(y);
fa[xx]=yy;
dis[xx]=dis[y]-dis[x]-vv;
return;
}
signed main()
{
freopen("check.in","r",stdin);
freopen("check.out","w",stdout);
scanf("%lld",&w);
while (w--){
bool f=false;
scanf("%lld%lld",&n,&m);
for (int i=0;i<=n;i++){
fa[i]=i;
dis[i]=0;
}
for (int i=1;i<=m;i++){
scanf("%lld%lld%lld",&s[i],&t[i],&v[i]);
}
for (int i=1;i<=m;i++){
if (find(s[i]-1)==find(t[i])){
if (dis[t[i]]-dis[s[i]-1]!=v[i]){
printf("f\n");
f=true;
break;
}
}
else{
merge(s[i]-1,t[i],v[i]);
}
}
if (!f){
printf("t\n");
}
}
return 0;
}
T3
大体思路是统计每个格子所在连通块并将其并入所属集合中，然后对于每个子正方形遍历其相接连通块。具体代码还没写完，先不放了。
最小生成树
T1
水题。
直接把i-1和j连起来然后跑一遍最小生成树即可。
code：
#include<bits/stdc++.h>
using namespace std;
const int N=2010,Max=0x3f3f3f3f;
int n,h[N],to[N*N],nxt[N*N],w[N*N],cnt=-1;
int dis[N],ans;
bool inn[N];
void add(int x,int y,int ww){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
w[cnt]=ww;
return;
}
int main()
{
freopen("cost.in","r",stdin);
freopen("cost.out","w",stdout);
memset(h,-1,sizeof h);
memset(dis,Max,sizeof dis);
dis[0]=0;
inn[0]=true;
scanf("%d",&n);
for (int i=1;i<=n;i++){
for (int j=i;j<=n;j++){
int ww;
scanf("%d",&ww);
add(i-1,j,ww);
add(j,i-1,ww);
}
}
for (int i=h[0];~i;i=nxt[i]){
int v=to[i];
dis[v]=min(dis[v],w[i]);
}
for (int i=1;i<=n;i++){
int minx,minn=Max;
for (int i=1;i<=n;i++){
if (!inn[i]&&dis[i]<minn){
minn=dis[i];
minx=i;
}
}
inn[minx]=true;
ans+=minn;
for (int i=h[minx];~i;i=nxt[i]){
int v=to[i];
dis[v]=min(dis[v],w[i]);
}
}
printf("%d",ans);
return 0;
}
T2和T3还没怎么看，改完前面的题就去。