POI2006
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);
}
评论 (0)
