POI2012

orz hhw posted @ 2017年11月22日 22:51 in 做题记录 with tags 解题报告 POI , 253 阅读

T1 Festival 首先差分构图,然后可以进行缩点,这样不同强连通分量互不影响,在每个强连通分量中求出最大的绝对值+1即为该强连通分量的贡献,如果有正环则无解

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 610
#define M 200020
#define inf -0x3f3f3f3f
using namespace std;
int n,m1,m2,i,j,x,y,tot,top,sz,cnt,now,ans,z[N],d[N][N],fir[N],st[N],low[N],dfn[N],bl[N],la[M],va[M],ne[M];bool is[N];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(int x,int y){return bl[x]<bl[y];}
void tarjan(int x){
	low[x]=dfn[x]=++sz;is[x]=1;st[++top]=x;int y,i;
	for(i=fir[x];i;i=ne[i])if(!dfn[y=la[i]])tarjan(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
	if(dfn[x]==low[x])for(cnt++,now=0;now!=x;now=st[top--],bl[now]=cnt,is[now]=0);
}
int main(){
	for(scanf("%d%d%d",&n,&m1,&m2);m1--;)scanf("%d%d",&x,&y),ins(x,y,1),ins(y,x,-1);
	for(;m2--;)scanf("%d%d",&x,&y),ins(x,y,0);memset(d,inf,sizeof(d));
	for(i=1;i<=n;d[i][i]=0,z[i]=i++)if(!dfn[i])tarjan(i);
	for(x=1;x<=n;x++)for(i=fir[x];i;i=ne[i])if(bl[x]==bl[la[i]])d[x][la[i]]=max(d[x][la[i]],va[i]);
	for(x=1;x<=n;x++)for(i=1;i<=n;i++)if(d[i][x]!=inf)for(j=1;j<=n;j++)if(d[x][j]!=inf)d[i][j]=max(d[i][j],d[i][x]+d[x][j]);
	for(i=1;i<=n;i++)if(d[i][i]>0)return puts("NIE"),0;sort(z+1,z+n+1,cmp);
	for(x=1;x<=n;ans+=now+1,x=y){
		for(y=x;y<=n&&bl[z[x]]==bl[z[y]];y++);
		for(now=0,i=x;i<y;i++)for(j=x;j<y;j++)now=max(now,abs(d[z[i]][z[j]]));
	}
	printf("%d",ans);
}

T2 Letters 首先一个想法是相同字母的相对顺序不会改变,于是可以得知目标串每个字母在原串中的位置,然后答案就是这个的逆序对

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,i,x,sum,now,c[1001000];
queue<int>q[26];char s[1001000];long long ans;
void add(int x){for(;x<=n;x+=x&-x)c[x]++;}
long long que(int x){for(now=0;x;x-=x&-x)now+=c[x];return now;}
int main(){
	for(scanf("%d%s",&n,s+1),i=1;i<=n;i++)q[s[i]-'A'].push(i);
	for(scanf("%s",s+1),i=1;i<=n;i++){
		x=q[s[i]-'A'].front();q[s[i]-'A'].pop();
		add(n-x+1);ans+=que(n-x);
	}printf("%lld",ans);
}

T3 Distance 先$O(n)$线性筛扫出每个数的因数个数,然后要求每个数的$min(d[i]+d[j]-2*d[gcd(i,j)])$,枚举这个因数,再加上是这个因数倍数的b[i]的最小值即可,由于可能这个最小值就是该数,还要统计一个次小值,时间复杂度$O(n\sqrt{n})$

#include<cstdio>
#include<cstring>
#define N 1001000
int n,i,j,x,w,t,u,d1[N],d2[N],e1[N],e2[N],b[N],p[N],a[N];bool f[N];
void cg(int x,int y,int z){if(z<d1[x]||z==d1[x]&&y<e1[x])d2[x]=d1[x],e2[x]=e1[x],d1[x]=z,e1[x]=y;else if(y!=e1[x]&&(z<d2[x]||z==d2[x]&&y<e2[x]))d2[x]=z,e2[x]=y;}
void get(int z,int y){if(z<w||z==w&&y<u)w=z,u=y;}
void r(int j){get(e1[j]==i?d2[j]-2*b[j]:d1[j]-2*b[j],e1[j]==i?e2[j]:e1[j]);}
int main(){
	for(memset(d1,63,sizeof(d1)),memset(d2,63,sizeof(d2)),i=2;i<=1000000;i++){
        if(!f[i])p[++t]=i,b[i]=1;
        for(j=1;j<=t&&i*p[j]<=1000000;j++){
            f[i*p[j]]=1;b[i*p[j]]=b[i]+1;
            if(i%p[j]==0)break;
        }
 	}
	for(scanf("%d",&n),i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for(j=1;j*j<=a[i];j++)if(a[i]%j==0){
			cg(j,i,b[a[i]]);
			if(a[i]*a[i]!=j)cg(a[i]/j,i,b[a[i]]);
		}
	}
	for(i=1;i<=n;printf("%d\n",u),i++)for(w=1e9,j=1;j*j<=a[i];j++)if(a[i]%j==0)r(j),r(a[i]/j);
}

T4 Rendezvous 基环树上求LCA,如果在一棵外向树上直接求,否则判断走环两边的距离,取更优的作为答案

#include<cstdio>
#include<algorithm>
#define N 500500
using namespace std;
int n,Q,i,j,top,tm,tmp,x,y,t,x1,y1,x2,y2,to[N],pos[N],rt[N],v[N],bl[N],sz[N],h[N],fa[N][20];
void fcur(int x){
	v[x]=tm;int y;
	if(v[to[x]]==tm){
		for(y=x,tmp=0;!tmp||x!=y;y=to[y],tmp++)bl[y]=tm,pos[y]=tmp,rt[y]=y;
		sz[tm]=tmp;return;
	}
	if(!v[to[x]])fcur(to[x]);
	if(!bl[x])fa[x][0]=to[x],h[x]=h[to[x]]+1,rt[x]=rt[to[x]];
}
int lca(int x,int y){
	if(h[x]<h[y])swap(x,y);
	int t=h[x]-h[y],i;
	for(i=0;i<=19;i++)if(t&(1<<i))x=fa[x][i];
	for(i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return x==y?x:fa[x][0];
}
int dis(int x,int y,int p){return (y-x+p)%p;}
int main(){
	for(scanf("%d%d",&n,&Q),i=1;i<=n;i++)scanf("%d",&to[i]);
	for(i=1;i<=n;i++)if(!v[i])tm++,fcur(i);
	for(j=1;j<=19;j++)for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
	for(;Q--;){
		scanf("%d%d",&x,&y);
		if(bl[rt[x]]!=bl[rt[y]]){puts("-1 -1");continue;}
		if(rt[x]==rt[y]){
			t=lca(x,y);
			printf("%d %d\n",h[x]-h[t],h[y]-h[t]);
			continue;
		}
		x1=h[x]+dis(pos[rt[x]],pos[rt[y]],sz[bl[rt[x]]]);y1=h[y];
		x2=h[x];y2=h[y]+dis(pos[rt[y]],pos[rt[x]],sz[bl[rt[y]]]);
		if(max(x1,y1)<max(x2,y2))printf("%d %d\n",x1,y1);else
		if(max(x2,y2)<max(x1,y2))printf("%d %d\n",x2,y2);else
		if(min(x1,y1)<min(x2,y2))printf("%d %d\n",x1,y1);else
		if(min(x2,y2)<min(x1,y1))printf("%d %d\n",x2,y2);else
		printf("%d %d\n",max(x1,y1),min(x1,y1));
	}
}

T5 Well 首先很容易想到二分,难点在于如何快速判断是否合法

可以先从左往右扫一遍,再从右往左扫一遍,把差距调到mid以内

然后枚举每个位置变为0,则他对答案的影响是左边和右边各一个等差数列,因为是单调的,可以顺序扫一遍得出每个位置改为0的代价

这样总的时间复杂度是$O(nlgn)$的

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;typedef long long LL;
int n,i,j,l,r,mid,t,z,k,a[N],b[N];LL m,now,s[N],f[N];
int ok(int w){
	for(b[1]=a[1],i=2;i<=n;i++)b[i]=min(a[i],b[i-1]+w);
	for(i=n-1;i;i--)b[i]=min(b[i],b[i+1]+w);
	for(now=0,i=1;i<=n;i++)now+=a[i]-b[i],s[i]=s[i-1]+b[i];
	for(i=j=1;i<=n;i++){
		for(;j<i&&b[j]<=(LL)(i-j)*w;j++);
		f[i]=s[i-1]-s[j-1]-(LL)(1+i-j)*(i-j)*w/2;
	}
	for(i=j=n;i;i--){
		for(;j>i&&b[j]<=(LL)(j-i)*w;j--);
		f[i]+=s[j]-s[i]-(LL)(1+j-i)*(j-i)*w/2;
	}
  for(i=1;i<=n;i++)if(f[i]+b[i]+now<=m)return i;return 0;
}
int main(){
	for(scanf("%d%lld",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]),r=r>a[i]?r:a[i];
	while(l<=r)if(t=ok(mid=(l+r)>>1))r=(z=mid)-1,k=t;else l=mid+1;
	printf("%d %d",k,z);
}

T6 Vouchers 因为知道这是一道傻逼题,就往傻逼的地方想,觉得暴力取应该没什么问题,是一个调和级数的复杂度,但由于姿势不太对WA了好几发

#include<cstdio>
#define N 1001000
int m,i,n,x,p,t,now,q[N],u[N];bool v[N],s[N];
long long a[N],top;
int main(){
	for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d",&x),s[x]=1;
	for(scanf("%d",&n),i=1;i<=n;i++){
		scanf("%d",&x);
		for(now=0,p=u[x]+x;p<=1000000&&now<x;p+=x)if(!v[p]){
			++top;v[p]=1;now++;
			if(s[p])a[++t]=top;
		}
		top+=x-now;u[x]=p-x;
	}
	for(printf("%d\n",t),i=1;i<=t;i++)printf("%lld\n",a[i]);
}

T7 Cloakroom 凑来凑去感觉只有$O(nk)$才有些许希望,于是可以把每个物品和询问按左端点排序,然后当物品左端点小于等于询问左端点时进行一次背包,dp的值表示和为这个价值时右端点较小值中的最大值,这样的时间复杂度是$O(nk+qlgq+nlgn)$的,能卡过去

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1010
using namespace std;
int n,i,Q,t,j,ans[N*N],dp[N*N];
struct E{int c,l,r;}e[N];struct U{int l,k,r,z;}q[N*N];
bool cmp(E a,E b){return a.l<b.l;}bool Cmp(U a,U b){return a.l<b.l;}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d%d",&e[i].c,&e[i].l,&e[i].r);sort(e+1,e+n+1,cmp);
	for(scanf("%d",&Q),i=1;i<=Q;i++)scanf("%d%d%d",&q[i].l,&q[i].k,&q[i].r),q[i].r+=q[i].l+1,q[i].z=i;
	sort(q+1,q+Q+1,Cmp);memset(dp,-1,sizeof(dp));dp[0]=2e9;
	for(t=i=1;i<=Q;i++){
		for(;e[t].l<=q[i].l&&t<=n;t++)
			for(j=100001;j>=e[t].c;j--)dp[j]=max(dp[j],min(dp[j-e[t].c],e[t].r));
		ans[q[i].z]=(dp[q[i].k]>=q[i].r);
	}
	for(i=1;i<=Q;i++)puts(ans[i]?"TAK":"NIE");
}

T8 A Horrible Poem 首先可以用哈希$O(1)$判断长度$x$是否是$l~r$的循环节,只要判$l~(r-x)$和$(l+x)~r$是否相等就行了,但如果暴力判时间复杂度是$O(n\sqrt{N})$会T,可以先枚举出所有质数,然后如果$x$是$l~r$的循环节,那么最小循环节一定是$x$的约数,于是可以枚举所有质因子,不断除去就可以在$O(nlgn)$时间内出解

#include<cstdio>
#define S 1000000007
#define N 500500
typedef unsigned long long LL;
int n,Q,i,j,p,len,x,y,z,to[N],prime[N];char s[N];LL a[N],pow[N];
bool ck(int l1,int r1,int l2,int r2){return a[r1]-a[l1-1]*pow[r1-l1+1]==a[r2]-a[l2-1]*pow[r2-l2+1];}
int main(){
	for(scanf("%d%s%d",&n,s+1,&Q),pow[0]=1,i=1;i<=n;i++)pow[i]=pow[i-1]*S,a[i]=a[i-1]*S+(s[i]-'a'+1);
	for(i=2;i<=n;i++){
		if(!to[i])to[i]=prime[++p]=i;
		for(j=1;j<=p&&i*prime[j]<=n;j++){
			to[i*prime[j]]=prime[j];
			if(i%prime[j]==0)break;
		}
	}
	for(;Q--;printf("%d\n",len)){
		scanf("%d%d",&x,&y);len=y-x+1;
		for(i=len;i>1;){
			for(z=to[i];len%z==0&&ck(x,y-len/z,x+len/z,y);len/=z);
			for(;i%z==0;i/=z);
		}
	}
}

T9 Fibonacci Representation 一开始写了个暴力set T了,然后加了个map+lower_bound才A。。

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;typedef long long LL;
int i,Q;
LL x,f[99];map<LL,int>F;
int find(LL n){
	if(F[n])return F[n];
	int b=lower_bound(f,f+91,n)-f;
	if(f[b]==n)return 1;
	return F[n]=min(find(n-f[b-1]),find(f[b]-n))+1;
}
int main(){
	f[1]=1;f[2]=2;for(i=3;i<=91;i++)f[i]=f[i-1]+f[i-2];
	for(scanf("%d",&Q);Q--;)scanf("%lld",&x),printf("%d\n",find(x));
}

T10 Squarks 首先最小的数一定是$x[1]+x[2]$,次小的数一定是$x[1]+x[3]$,而$x[2]+x[3]$可能是第$3~n$小的数,枚举$x[2]+x[3]$的位置,然后解方程得到$x[1]$、$x[2]$和$x[3]$,然后剩下的数最小的一定是$x[1]+x[4]$,由于$x[1]$已知,于是$x[4]$可知,然后判断$x[2]+x[4]$、$x[3]+x[4]$是否出现并删除,然后$x[5]...x[n]$以此类推,最后再判断一下是否是顺序上升的就可以了,时间复杂度$O(n^3)$

#include<cstdio>
#include<set>
#include<algorithm>
#define N 310
using namespace std;
int n,m,i,j,tot,a[N*N],x[N],ans[N][N];
multiset<int>w,s;
void ck(int a3){
	if(a[1]+a[2]+a3&1)return;int i,j;s=w;
	x[1]=a[1]+a[2]-a3>>1;x[2]=a[1]+a3-a[2]>>1;x[3]=a[2]+a3-a[1]>>1;
	s.erase(s.find(a[1]));s.erase(s.find(a[2]));s.erase(s.find(a3));
	for(i=4;i<=n;i++){
		x[i]=*s.begin()-x[1];
		if(x[i]<0)return;
		for(j=1;j<i;s.erase(s.find(x[j]+x[i])),j++)if(s.find(x[j]+x[i])==s.end())return;
	}
	for(i=1;i<n;i++)if(x[i]>=x[i+1])return;
	for(tot++,i=1;i<=n;i++)ans[tot][i]=x[i];
}
int main(){
	for(scanf("%d",&n),m=n*(n-1)/2,i=1;i<=m;i++)scanf("%d",&a[i]),w.insert(a[i]);sort(a+1,a+m+1);
	for(i=3;i<=n;i++)if(i==3||a[i]!=a[i-1])ck(a[i]);
	for(printf("%d\n",tot),i=1;i<=tot;puts(""),i++)for(j=1;j<=n;j++)printf("%d ",ans[i][j]);
}

T11 Bidding 面向数据编程

#include<cstdio>
int main(){printf("756396726\n1");}

T12 Salaries 算出每个点的取值范围,从小到大扫描,如果当前$max i=k$只有一个点且在$1~k$中只有这一个数可用则这个点值确定,如果$maxi=k$的节点数=$1~k$中可用节点数把这些节点全部删去,标记为不可用

#include<cstdio>
#define N 1001000
int n,i,h,t,tot,res,rt,S,fir[N],ne[N],la[N],p[N],z[N],fa[N],s[N],sm[N],q[N],ans[N];bool v[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)fa[i]=i;
	for(i=1;i<=n;i++){
		scanf("%d%d",&p[i],&z[i]);
		if(z[i])v[z[i]]=1,ans[i]=z[i],fa[z[i]]=z[i]-1;
		if(p[i]!=i)ins(p[i],i);else p[rt=i]=0;
	}
	for(z[0]=n+1,q[h=t=1]=rt;h<=t;h++){
		if(!z[q[h]])z[q[h]]=gf(z[p[q[h]]]-1),s[z[q[h]]]=q[h],sm[z[q[h]]]++;
		for(i=fir[q[h]];i;i=ne[i])q[++t]=la[i];
	}
	for(i=1;i<=n;i++){
		if(!v[i])S=i,res++;
		if(sm[i]&&res==1)ans[s[i]]=S;
		if(sm[i])res-=sm[i],S=0;
	}
	for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}

T13 Leveling Ground 用前缀和使其变成单点修改,可以求出$ax+by=c$使得代价最小,先让$x$为正,$y$为负,然后$x$不断减$b$,$y$加$a$,通过堆得到一个最优的答案。真的好神啊~

#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;typedef long long LL;
int n,i,rt,s[N][2];
LL a,b,t,x,y,la,ans,tot,c[N],p[N],q[N],v[N];
LL exgcd(LL a,LL b,LL&x,LL&y){
	if(!b){x=1;y=0;return a;}
	LL t=exgcd(b,a%b,y,x);y-=x*(a/b);
	return t;
}
LL get(int x){
	LL now=0;
	if(p[x]>0)now+=p[x];if(q[x]>0)now+=q[x];
	if(q[x]+a>0)now-=q[x]+a;return now;
}
int mg(int x,int y){
	if(!x||!y)return x+y;
	if(v[x]<v[y])swap(x,y);
	s[x][1]=mg(s[x][1],y);
	swap(s[x][0],s[x][1]);
	return x;
}
int main(){
	scanf("%d%lld%lld",&n,&a,&b);if(b<a)swap(a,b);
	t=exgcd(a,b,x,y);a/=t;b/=t;x=(x+b)%b;
	for(i=1;i<=n;i++)scanf("%lld",&y),c[i]=la-y,la=y;
	for(i=1,c[++n]=la;i<=n;i++){
		if(c[i]%t)return puts("-1"),0;c[i]/=t;
		p[i]=(c[i]*x)%b;if(p[i]<0)p[i]+=b;
		q[i]=(c[i]-p[i]*a)/b;tot+=p[i];
		v[i]=get(i);
		rt=mg(rt,i);
	}
	for(tot/=b;tot--;){
		x=rt;rt=mg(s[rt][0],s[rt][1]);s[x][0]=s[x][1]=0;
		p[x]-=b;q[x]+=a;v[x]=get(x);
		rt=mg(rt,x);
	}
	for(i=1;i<=n;i++){if(p[i]>0)ans+=p[i];if(q[i]>0)ans+=q[i];}
	printf("%lld",ans);
}

T14 Minimalist Security 对于每一个连通块,对一个点设未知数$x$,则剩下的点都可以用$x$表示,如果碰到两边都已经表示过,如果不同号则判一下常数是否合法,否则则可以算出$x$的值,如果$x$的值有多个则不合法,顺便可以根据$0\leq x+w[i]\leq p[i]$算出$x$的$[l,r]$取值范围,然后就可以得到答案了

#include<cstdio>
#include<algorithm>
#define N 500500
#define M 6006000
using namespace std;
int n,m,i,x,y,z,h,t,u,tot,ans,l,r,sz,s,fir[N],la[M],va[M],ne[M],v[N],w[N],p[N],q[N];
long long sum,now,lv,rv;bool flag;
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&p[i]),sum+=p[i];
	for(;m--;)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	for(s=1;s<=n;s++)if(!v[s]){
		for(q[t=1]=s,v[s]=1,ans=-1,h=sz=0,now=0,l=0,r=p[s];h^t;){
			if(v[u=q[++h]]<2)sz++,now+=w[u],l=max(l,-w[u]),r=min(r,p[u]-w[u]);
			else sz--,now+=w[u],l=max(l,w[u]-p[u]),r=min(r,w[u]);
			for(i=fir[u];i;i=ne[i]){
				y=la[i];z=va[i]-w[u];
				if(v[y]){
					if(3-v[u]==v[y]){if(z!=w[y])return puts("NIE"),0;}else{
						x=w[y]-z;if(x&1)return puts("NIE"),0;
						x>>=1;if(v[y]<2)x=-x;
						if(ans<0||ans==x)ans=x;else return puts("NIE"),0;
					}
				}else v[y]=3-v[u],w[y]=z,q[++t]=y;
			}
		}
		if(l>r)return puts("NIE"),0;
		if(ans>0){
			if(ans<l||ans>r)return puts("NIE"),0;
			l=r=ans;
		}
		if(sz>0)lv+=1ll*r*sz+now,rv+=1ll*l*sz+now;else lv+=1ll*l*sz+now,rv+=1ll*r*sz+now;
	}
	printf("%lld %lld",sum-lv,sum-rv);
}

T15 Warehouse Store 一开始写线段树乱搞但发现是不对的,应该要用贪心的思想,每次能加就加,不能加就在已经加的中找最大的换,这样就能保证正确性

#include<cstdio>
#include<map>
#include<queue>
#define mp make_pair
#define N 252000
using namespace std;
priority_queue<pair<int,int> >q;
int n,i,x,va,id,cnt,a[N];bool w[N];long long now;
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++){
		scanf("%d",&x);now+=a[i];
		if(now>=(long long)x)now-=x,q.push(mp(x,i)),w[i]=1;else
		if(!q.empty()){
			va=q.top().first;id=q.top().second;
			if(va>x)q.pop(),w[id]=0,now+=va-x,q.push(mp(x,i)),w[i]=1;
		}
	}for(i=1;i<=n;i++)if(w[i])cnt++;
	for(printf("%d\n",cnt),i=1;i<=n;i++)if(w[i])printf("%d\n",i);
}

T16 Prefixuffix 用$f_i$表示串$[i+1,n-i]$中最长的串使$[i+1,i+f_i]=[n-i-f_i+1,n-i]$,这时有一个性质$f_{i-1}\leq f_i+2$,然后就可以线性递推

不过这题unsigned long long自然溢出会挂,于是只能取模,不过这题其实$O(nlgn)$暴力也能过的、YY大爷%%%

#include<cstdio>
#include<cstring>
#include<algorithm>
#define S 1000000003
#define M 1000000009
#define N 1001000
using namespace std;typedef long long LL;
int n,i,j,ans;char s[N];LL pw[N],sum[N];
LL get(int l,int r){return (sum[r]+M-sum[l-1]*pw[r-l+1]%M)%M;}
int main(){
	for(scanf("%d%s",&n,s+1),pw[0]=i=1;i<=n;i++)pw[i]=pw[i-1]*S%M,sum[i]=(sum[i-1]*S%M+s[i])%M;
	for(i=n>>1;~i;i--)
		for(j=min(n/2-i,j+2);j>=0;j--)if(get(i+1,i+j)==get(n-i-j+1,n-i)){
			if(get(1,i)==get(n-i+1,n))ans=max(ans,i+j);
			break;
		}
	printf("%d",ans);
}

T17 Tour de Byteotia 把大于$k$的先加入并查集,然后剩余的判是否构成环就可以了,写了个按秩合并的T了,按秩合并+路径压缩也T了,改成路径压缩才A。。

#include<cstdio>
#define N 1001000
int n,m,k,i,p,q,ans,a[N*2],b[N*2],fa[N];char ch;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void read(int &x){
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
	for(read(n),read(m),read(k),i=1;i<=n;i++)fa[i]=i;
	for(i=1;i<=m;i++){
		read(a[i]);read(b[i]);
		if(a[i]>k&&b[i]>k)p=gf(a[i]),q=gf(b[i]),fa[p]=q;
	}
	for(i=1;i<=m;i++)if(a[i]<=k||b[i]<=k){
		p=gf(a[i]);q=gf(b[i]);
		if(p==q)ans++;else fa[p]=q;
	}
	printf("%d",ans);
}