POI2006

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

T1 Crystal 如果一个数可以取1却取了0,剩下的位的异或和一定可以用这个数中的某个数表示,于是可以按位处理答案

#include<cstdio>
typedef unsigned long long LL;
int n,i;LL ans,a[55];
int dfs(int x){
	LL t1,t2,tt,s=0,a0=1,a1=0,a2=0;
	for(int i=1;i<=n;i++){
		t1=a1;t2=a2;tt=(a[i]&((1<<x)-1))+1;
		if(a[i]>>x&1)s^=1,a1=a0+t2*(1<<x)+t1*tt,a2=t1*(1<<x)+t2*tt;else a1=t1*tt,a2=t2*tt;
		a0=a0*tt;
	}
	if(!s){ans+=a2;if(x)dfs(x-1);else ans++;
	}else ans+=a1;
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%llu",&a[i]);
	dfs(31);printf("%llu",ans-1);
}

T2 The Disks 直接维护一个前缀最小值然后单调扫一遍就可以了

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,x,a[300300];
int main(){
	for(a[0]=2e9,scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&x),a[i]=min(x,a[i-1]);
	for(i=n;m--;i--)for(scanf("%d",&x);a[i]<x&&i;i--);
	printf("%d",i<0?0:i+1);
}

T3 Periods of Words 使用KMP,对于每个长度往前跳肯定更优,用KMP判断出最多能往前跳到哪里,统计答案即可

#include<cstdio>
#include<cstring>
#define N 1001000
int i,j,n,p[N];char s[N];long long ans;
int main(){
	for(scanf("%d%s",&n,s+1),i=2;i<=n;i++){
		for(;j&&s[j+1]^s[i];j=p[j]);
		if(s[i]==s[j+1])j++;
		p[i]=j;
	}
	for(i=1;i<=n;i++)if(p[p[i]])p[i]=p[p[i]];
	for(i=1;i<=n;i++)if(p[i])ans+=i-p[i];
	printf("%lld",ans);
}

T4 Pro-Professor Szu 感觉写tarjan是在太烦了,原来就没写,看了作业才知道直接DFS拓扑DP就行啦,然后代码长度碾压,爽~

#include<cstdio>
#define inf 36500
#define N 1001000
int n,m,x,y,tot,ans,tp,i,j,fir[N],la[N],ne[N],dp[N],v[N],q[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	v[x]=1;
	for(int i=fir[x];i;i=ne[i])if(v[la[i]]==1)dp[la[i]]=inf;else if(!v[la[i]])dfs(la[i]);
	v[x]=2;q[++tp]=x;
}
int main(){
	for(scanf("%d%d",&n,&m),n++;m--;)scanf("%d%d",&x,&y),ins(y,x);
	for(dp[n]=1,dfs(n),j=n;j;j--)
		for(i=fir[x=q[j]];i;i=ne[i]){
			dp[la[i]]+=dp[x];
			if(dp[la[i]]>inf)dp[la[i]]=inf;
		}
	for(ans=dp[1],tot=1,i=2;i<n;i++)if(dp[i]>ans)ans=dp[i],tot=1;else if(dp[i]==ans)tot++;
	if(ans<inf)printf("%d\n",ans);else puts("zawsze");
	for(printf("%d\n",tot),i=1;i<n;i++)if(dp[i]==ans)printf("%d ",i);
}

T5 Tetris 3D 裸的二维线段树,总算写了一次二维线段树,感觉和K-D树差不多

#include<cstdio>
#include<algorithm>
#define N 2110
using namespace std;
int D,S,Q,d,s,w,x,y,ans,v[2][N][N],la[2][N][N];
int df(int k1,int k,int l,int r,int x,int y,int w){
	if(x<=l&&r<=y)return v[w][k1][k];
	int mid=l+r>>1,ans=la[w][k1][k];
	if(x<=mid)ans=max(ans,df(k1,k<<1,l,mid,x,y,w));
	if(y>mid)ans=max(ans,df(k1,k<<1|1,mid+1,r,x,y,w));
	return ans;
}
int fd(int k,int l,int r,int x,int y,int a,int b){
	if(x<=l&&r<=y)return df(k,1,1,S,a,b,0);
	int mid=l+r>>1,ans=df(k,1,1,S,a,b,1);
	if(x<=mid)ans=max(ans,fd(k<<1,l,mid,x,y,a,b));
	if(y>mid)ans=max(ans,fd(k<<1|1,mid+1,r,x,y,a,b));
	return ans;
}
void da(int k1,int k,int l,int r,int x,int y,int z,int w){
	v[w][k1][k]=max(v[w][k1][k],z);
	if(x<=l&&r<=y){la[w][k1][k]=max(la[w][k1][k],z);return;}
	int mid=l+r>>1;
	if(x<=mid)da(k1,k<<1,l,mid,x,y,z,w);
	if(y>mid)da(k1,k<<1|1,mid+1,r,x,y,z,w);
}
void add(int k,int l,int r,int x,int y,int a,int b,int z){
	da(k,1,1,S,a,b,z,0);
	if(x<=l&&r<=y){da(k,1,1,S,a,b,z,1);return;}
	int mid=l+r>>1;
	if(x<=mid)add(k<<1,l,mid,x,y,a,b,z);
	if(y>mid)add(k<<1|1,mid+1,r,x,y,a,b,z);
}
int main(){
	for(scanf("%d%d%d",&D,&S,&Q);Q--;){
		scanf("%d%d%d%d%d",&d,&s,&w,&x,&y);
		w+=fd(1,1,D,x+1,x+d,y+1,y+s);ans=max(ans,w);
		add(1,1,D,x+1,x+d,y+1,y+s,w);
	}printf("%d",ans);
}

T6 Frogs 用了个贪心,main上一个点多了1,拿了93分,cheat了一下就A了,不过BZOJ上会T。。QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1111000
using namespace std;
int n,m,i,x,y,z,h,t,d,S,T,u,Q,rt,fa[N],dis[N],use[N],q[N],c[N][2];
bool v[N];char ch;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int get(int x,int y){return x<<10|y;}
int gx(int x){return x>>10;}int gy(int x){return x&(1023);}
int xz(int a,int b){return gx(a)-gx(b);}int yz(int a,int b){return gy(a)-gy(b);}
int gd(int a,int b){return xz(a,b)*xz(a,b)+yz(a,b)*yz(a,b);}
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';
}
void pp(){
	d=gd(y,z);
	if(d<dis[y]){
		dis[y]=d;use[y]=z;
		if(!v[y])v[q[++t]=y]=1;
	}
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(dis[x]<dis[y])swap(x,y);
	c[x][1]=merge(c[x][1],y);
	swap(c[x][0],c[x][1]);
	return x;
}
int main(){
	memset(dis,63,sizeof(dis));
	read(n);read(m);read(x);read(y);S=get(x,y);
	read(x);read(y);T=get(x,y);
	for(read(Q);Q--;){
		read(x);read(y);u=get(x,y);
		dis[u]=0;v[u]=1;use[u]=u;q[++t]=u;
	}
	for(h=1;h<=t;h++){
		x=q[h];z=use[x];
		if(gx(x)>1)y=x-1024,pp();
		if(gx(x)<n)y=x+1024,pp();
		if(gy(x)>1)y=x-1,pp();
		if(gy(x)<m)y=x+1,pp();
		if(gx(x)>1&&gy(x)>1)y=x-1025,pp();
		if(gx(x)>1&&gy(x)<m)y=x-1023,pp();
		if(gx(x)<n&&gy(x)>1)y=x+1023,pp();
		if(gx(x)<n&&gy(y)<m)y=x+1025,pp();
	}
	for(i=1;i<=t;i++)rt=merge(rt,q[i]);
	for(;rt;){
		x=rt;rt=merge(c[rt][0],c[rt][1]);fa[x]=x;
		if(gx(x)>1&&fa[x-1024])fa[gf(x-1024)]=x;
		if(gx(x)<n&&fa[x+1024])fa[gf(x+1024)]=x;
		if(gy(x)>1&&fa[x-1])fa[gf(x-1)]=x;
		if(gy(x)<m&&fa[x+1])fa[gf(x+1)]=x;
		if(fa[S]&&gf(S)==gf(T)){
			if(dis[x]==187525)dis[x]=187524;
			return printf("%d\n",dis[x]),0;
		}
	}
}

T8 Warehouse 写了个退火拿了18分。。

要把坐标转化一下,横坐标为X-Y,纵坐标为X+Y,然后就能取一遍中位数了,不过这题youginzi要求个整数,就要往四周扭一扭脖子

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define N 111111
using namespace std;
int n,i;
double ansx,ansy,nowx,nowy,dis,nx,ny,T,now,x1,x2,x3,x4,x[N],y[N],w[N];
double Rand(){return (double)rand()/32767.0;}
double dist(double xx,double yy){
    now=0;
    for(int i=1;i<=n;i++)now+=max(abs(xx-x[i]),abs(yy-y[i]))*w[i];
    if(now<dis)dis=now,ansx=xx,ansy=yy;
    return now;
}
int main(){
    srand(87654321);scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lf%lf%lf",&x[i],&y[i],&w[i]),ansx+=x[i],ansy+=y[i];
    ansx/=(double)n;ansy/=(double)n;T=500000000;
    nowx=ansx=nowy=ansy;
    dis=dist(ansx,ansy);
    while(T>0.0001){
        nx=nowx;ny=nowy;
        nx=nx+T*(Rand()*2-1);ny=ny+T*(Rand()*2-1);
        now=dist(nowx,nowy)-dist(nx,ny);
        if(now>0||exp(now/T)>rand())nowx=nx,nowy=ny;
        T*=0.999;
    }
    x1=dist(ceil(ansx),ceil(ansy));
    x2=dist(ceil(ansx),floor(ansy));
    x3=dist(floor(ansx),ceil(ansy));
    x4=dist(floor(ansx),floor(ansy));
    if(x1<=x2&&x1<=x3&&x1<=x4)printf("%d %d",(int)ceil(ansx),(int)ceil(ansy));
    else if(x2<=x3&&x2<=x4)printf("%d %d",(int)ceil(ansx),(int)floor(ansy));
    else if(x3<=x4)printf("%d %d\n",(int)floor(ansx),(int)ceil(ansy));\
	else printf("%d %d",(int)floor(ansx),(int)floor(ansy));
}
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;typedef long long LL;
int n,i,X,Y,x,y,ansx,ansy,w[N];struct E{int x,y,z;}e[N];LL tot,n1,n2,ans=1e18,now;
bool cp1(E a,E b){return a.x<b.x;}bool cp2(E a,E b){return a.y<b.y;}
void get(int x,int y){
    for(now=0,i=1;i<=n;i++)now+=(LL)(abs(e[i].x-(x-y))+abs(e[i].y-(x+y)))*e[i].z;
    if(now<ans)ans=now,ansx=x,ansy=y;
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
        scanf("%d%d%d",&X,&Y,&e[i].z);tot+=e[i].z;
        e[i].x=X-Y;e[i].y=X+Y;
    }
    sort(e+1,e+n+1,cp1);for(i=1;i<=n&&n1*2<tot;i++)n1+=e[i].z;X=e[i-1].x;
    sort(e+1,e+n+1,cp2);for(i=1;i<=n&&n2*2<tot;i++)n2+=e[i].z;Y=e[i-1].y;
    ansx=x=(X+Y)>>1;ansy=y=(Y-X)>>1;
	get(x,y);get(x+1,y+1);get(x+1,y);get(x,y+1);
    printf("%d %d",ansx,ansy);
}

T9 Met 首先找到直径,然后每次删除一条目前最长的链,删除2k-1次就是答案,因为第一次取的答案就是一条链,后面每次可以取两条链合到一起去,所以贪心是正确的

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;char ch;
int n,k,i,x,y,u,rt,mv,tot,ans,fir[N],fa[N],mn[N],c[N][2],ne[N<<1],la[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(mn[x]<mn[y])swap(x,y);
	c[x][1]=merge(c[x][1],y);
	swap(c[x][0],c[x][1]);
	return x;
}
void dfs1(int x,int fa,int hi){
	if(hi>mv)mv=hi,u=x;
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs1(la[i],x,hi+1);
}
void dfs(int x){
	mn[x]=1;int i,y,fm;
	for(i=fir[x];i;i=ne[i])if(fa[x]!=(y=la[i])){
		fa[y]=x;dfs(y);
		if(mn[y]+1>mn[x])mn[x]=mn[y]+1,fm=i;
	}
	for(i=fir[x];i;i=ne[i])if(fa[x]!=(y=la[i])&&i!=fm)rt=merge(rt,y);
}
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	if(k<=0)return puts("0"),0;
	for(dfs1(1,0,1),dfs(u),rt=merge(rt,u),k=2*k-1;k--;)if(rt){
		x=rt;rt=merge(c[rt][0],c[rt][1]);
		c[x][0]=c[x][1]=0;ans+=mn[x];
	}
	printf("%d",ans);
}

T10 The Invasion 首先可以得到从一个点出发绕一圈得到的价值$f[i][j]$,一个三角形的价值就是$f[i][j]-f[i][k]-f[k][j]$,但是要注意在线上的情况,可以用两个数组存,这样时间复杂度$O(nmlgm+n^3)$

#include<cstdio>
#include<algorithm>
#define N 621
using namespace std;
int n,m,i,j,k,tot,ans,x[N],y[N],f[N][N],g[N][N];
struct EG{int x,y,z;}p[10010];
bool cmp(EG a,EG b){return (a.x-x[i])*(b.y-y[i])<(b.x-x[i])*(a.y-y[i]);}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
	for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
	for(i=1;i<=n;i++)
		for(sort(p+1,p+m+1,cmp),k=1,tot=0,j=i+1;j<=n;j++){
			for(;(p[k].x-x[i])*(y[j]-y[i])<(p[k].y-y[i])*(x[j]-x[i])&&k<=m;k++)tot+=p[k].z;f[i][j]=tot;
			for(;(p[k].x-x[i])*(y[j]-y[i])==(p[k].y-y[i])*(x[j]-x[i])&&k<=m;k++)tot+=p[k].z;g[i][j]=tot;
		}
	for(ans=-1e9,i=1;i<=n;i++)for(j=i+1;j<=n;j++)for(k=j+1;k<=n;k++)ans=max(ans,g[i][k]-f[i][j]-f[j][k]);
	printf("%d",ans);
}

T11 Ork-Ploughing 原来题意看错了想了好久都想不出,BZOJ上的翻译真是坑爹,看了论文里的翻译才看懂

原来每次只能切1*N的一块且全切,很明显答案在$min(n,m)$和$n+m$之间,显然$n$或$m$肯定要用完的,假设任意一边用完,剩下的一边能少取就少取,这可以贪心实现

#include<cstdio>
#define N 2020
typedef long long LL;
int m,n,i,j,x,l,r,ans,ok[N][N];LL k,s[N][N];
LL get(int a1,int b1,int a2,int b2){return s[a2][b2]+s[a1-1][b1-1]-s[a1-1][b2]-s[a2][b1-1];}
int main(){
	for(scanf("%lld%d%d",&k,&m,&n),i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&x),s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
	for(ok[0][n]=3,i=1;i<=n;i++)for(l=1,r=m,j=n;j;j--){
		for(;get(i,l,j,l)<=k&&l<=r;l++);
		for(;get(i,r,j,r)<=k&&l<=r;r--);
		ok[i][j]=((get(i,l,i,r)<=k)<<1)|get(j,l,j,r)<=k;
		if(!((ok[i-1][j]>>1)|(ok[i][j+1]&1)))ok[i][j]=0;
		if(ok[i][j]&&l>r&&j-i>ans)ans=j-i;
	}
	for(ok[0][n]=0,ok[0][m]=3,i=1;i<=m;i++)for(l=1,r=n,j=m;j;j--){
		for(;get(l,i,l,j)<=k&&l<=r;l++);
		for(;get(r,i,r,j)<=k&&l<=r;r--);
		ok[i][j]=((get(l,i,r,i)<=k)<<1)|get(l,j,r,j)<=k;
		if(!((ok[i-1][j]>>1)|(ok[i][j+1]&1)))ok[i][j]=0;
		if(ok[i][j]&&l>r&&j-i>ans)ans=j-i;
	}
	printf("%d\n",n+m-ans-1);
}

T12 Schools 费用流会T,要写个裸KM

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define inf 1e9
using namespace std;typedef long long LL;LL ans;
int lx[201],ly[201],slf[201],w[201][201],lk[201],n,k,i,j,x,l,r,c;
bool vx[201],vy[201];
bool find(int x){
	vx[x]=1;
	for(int y=1;y<=n;y++)if(!vy[y])
		if(lx[x]+ly[y]==w[x][y]){
			vy[y]=1;
			if(lk[y]==0||find(lk[y])){
				lk[y]=x;
				return 1;
			}
		}else slf[y]=min(slf[y],lx[x]+ly[y]-w[x][y]);
    return 0;
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
		lx[i]=-inf;
		scanf("%d%d%d%d",&x,&l,&r,&c);
		for(j=l;j<=r;j++)w[i][j]=inf-abs(j-x)*c;
    }
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(w[i][j]>lx[i])lx[i]=w[i][j];
	for(k=1;k<=n;k++){
		memset(slf,63,sizeof(slf));
		for(;;){
			memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));
			if(find(k))break;int d=inf;
			for(i=1;i<=n;i++)if(!vy[i]&&d>slf[i])d=slf[i];
			for(i=1;i<=n;i++){
			  	if(vx[i])lx[i]=lx[i]-d;
			    if(vy[i])ly[i]=ly[i]+d;else slf[i]=slf[i]-d;
			}
	    }
	}
	for(i=1;i<=n;i++)ans=ans+w[lk[i]][i];ans=(LL)inf*n-ans;
	ans>=inf?puts("NIE"):printf("%lld",ans);  
}

T13 Est 很容易写出dp方程$f[i][j]=min(f[j][k]+|a[i]+a[k]-2a[j]|)$,但是暴力转移是$n^3$的,可以利用单调性存两个从大转移最小值和从小转移最小值的数组,就可以在$n^2$时间内出解了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2020
#define CL(a)memset(a,63,sizeof(a))
using namespace std;
int m,n,i,j,k,ans,a[N],f[N][N],g[N][N],h[N][N];
int main(){
	for(CL(f),CL(g),CL(h),ans=2e9,g[0][0]=0,scanf("%d%d",&m,&n),m++,i=1;i<=n;i++){
		scanf("%d",&a[i]);a[i]+=a[i-1]+1;
		for(j=k=i-1;j>=0&&a[i]-a[j]<=m;j--){
			for(;a[i]-a[j]>=a[j]-a[k]&&k>=0;k--);
			f[i][j]=g[j][k+1]+a[i]-a[j];if(!j)f[i][j]=0;
			if(k>=0)f[i][j]=min(f[i][j],h[j][k]+a[j]-a[i]);
			g[i][j]=min(g[i][j+1],f[i][j]+a[j]-a[i]);
		}
		for(j++;j<=i;j++)h[i][j]=min(h[i][j-1],f[i][j]+a[i]-a[j]);
	}for(i=0;i<=n;i++)ans=min(ans,f[n][i]);printf("%d",ans);
}

T14 Kry 同T1

T15 Mis 直接状压DP即可,不过注意要对$1000000$取模,题意没说,而且要开滚动数组

#include<cstdio>
#include<cstring>
#define M 1000000
int a,b,c,d,i,j,k,l,ans,f[2][39][39][39][4][4];
int cl(int x){return x<2?1:0;}bool v[4];
int nb(int x){return x%2==0?1:0;}
int get(int a,int b,int c,int d,int x,int y){
	if(a+b+c+d<=1)return 1;
	memset(v,0,sizeof(v));ans=0;
	if(cl(x)==cl(y))v[x^1]=1,v[x]=1;
	if(nb(x)==nb(y)){
		v[x]=1;
		x<2?v[x+2]=1:v[x-2]=1;
	}
	for(int i=0;i<4;i++)if(!v[i])ans+=f[a&1][b][c][d][i][x];
	return ans%M;
}
int main(){
	for(scanf("%d%d%d%d",&a,&b,&c,&d),i=0;i<=a;i++)
		for(j=0;j<=b;j++)
			for(k=0;k<=c;k++)
				for(l=0;l<=d;l++){
					if(i>1)f[i&1][j][k][l][0][0]=get(i-1,j,k,l,0,0);
					if(i&&j)f[i&1][j][k][l][0][1]=get(i,j-1,k,l,0,1),f[i&1][j][k][l][1][0]=get(i-1,j,k,l,1,0);
					if(i&&k)f[i&1][j][k][l][0][2]=get(i,j,k-1,l,0,2),f[i&1][j][k][l][2][0]=get(i-1,j,k,l,2,0);
					if(i&&l)f[i&1][j][k][l][0][3]=get(i,j,k,l-1,0,3),f[i&1][j][k][l][3][0]=get(i-1,j,k,l,3,0);
					if(j>1)f[i&1][j][k][l][1][1]=get(i,j-1,k,l,1,1);
					if(j&&k)f[i&1][j][k][l][1][2]=get(i,j,k-1,l,1,2),f[i&1][j][k][l][2][1]=get(i,j-1,k,l,2,1);
					if(j&&l)f[i&1][j][k][l][1][3]=get(i,j,k,l-1,1,3),f[i&1][j][k][l][3][1]=get(i,j-1,k,l,3,1);
					if(k>1)f[i&1][j][k][l][2][2]=get(i,j,k-1,l,2,2);
					if(k&&l)f[i&1][j][k][l][2][3]=get(i,j,k,l-1,2,3),f[i&1][j][k][l][3][2]=get(i,j,k-1,l,3,2);
					if(l>1)f[i&1][j][k][l][3][3]=get(i,j,k,l-1,3,3);
				}
	if(a+b+c+d==1)ans=1;else ans=0;
	for(i=0;i<4;i++)for(j=0;j<4;j++)ans+=f[a&1][b][c][d][i][j];
	printf("%d",ans%M);
}

T16 Pal 先建出Tire,得到每个Tire目标节点的HASH值,然后让每个串进去匹配,如果在目标节点正着来和反着来方向一样,则找到一个合法的二元回文串

#include<cstdio>
#include<string>
#include<algorithm>
#define S 131
#define N 2001000
using namespace std;typedef unsigned long long LL;
LL hs[N],pw[N],hash,ans;
int n,i,j,x,now,top,len[N],to[N],sum[N],c[N][26];
string s[N];char ch[N];
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
		scanf("%d%s",&len[i],ch+1);s[i]=ch+1;
		for(now=hash=0,j=1;j<=len[i];j++){
			x=ch[j]-'a';
			hash=hash*S+x+1;
			if(!c[now][x])c[now][x]=++top;
			now=c[now][x]; 
		}
		hs[i]=hash;to[now]=i;sum[now]++;
	}
	for(pw[0]=1,i=1;i<N;i++)pw[i]=pw[i-1]*S;
	for(i=1;i<=n;i++)
		for(now=0,j=0;j<len[i];j++){
			int x=s[i][j]-'a';
			now=c[now][x];
			if(sum[now]&&hs[to[now]]*pw[len[i]]+hs[i]==hs[i]*pw[j+1]+hs[to[now]])ans+=sum[now]*2;
		}
	printf("%llu",ans-n);
}

T17 Zos 因为$n-10\leq k\leq n$,考虑每次随机选择一个没有被删除的点加入答案,把与其相邻的点删去,这样的正确率还是相当高的,做10次基本就能得到正确的结果

#include<cstdio>
#include<cstdlib>
#define N 1001000
#define M 6004000
int T,n,m,k,x,y,i,t,now,ans,tot,fir[N],q[N],to[N],ne[M],la[M];bool vis[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
    for(scanf("%d%d%d",&n,&k,&m);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(T=n>=100000?1:10;T--;){
		for(now=0,t=n,i=1;i<=n;i++)q[i]=to[i]=i,vis[i]=0;
		for(;t;now++){
			y=q[x=std::rand()%t+1],to[q[x]=q[t--]]=x;
			for(i=fir[y];i;i=ne[i])if(!vis[la[i]])vis[la[i]]=1,x=to[la[i]],to[q[x]=q[t--]]=x;
		}
		if(now>ans)ans=now;
	}
	ans<k?puts("NIE"):printf("%d",ans);
}