POI2004

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

T1 Gra 转化一下,有任意棋子在$m-1$上是必败的,把连在一起的看做一堆,就可以当做一个阶梯博弈了,算方案时要特判一下,防止非法情况

#include<cstdio>
#define N 1001000
int n,m,i,now,tot,top,ans,sum,a[N],b[N];
int main(){
	for(scanf("%d%d",&m,&n),a[n+1]=m-1,i=1;i<=n;i++)scanf("%d",&a[i]);
	if(a[n]>=m-1){
		for(i=n;i&&a[i]-a[i-1]==1;i--)sum++;
		return printf("%d",sum+1),0;
	}
	for(i=n;i;i--,now++)if(a[i+1]-a[i]!=1){
		b[top++]=now;now=0;
		if(a[i+1]-a[i]>2)top+=2-((a[i+1]-a[i])&1);
	}b[top]=now;
	for(i=1;i<=top;i++)if(i&1)ans^=b[i];
	for(i=1;i<=top;i++)if((i&1)&&(b[i]^ans)<b[i]||!(i&1)&&(b[i-1]^ans)>b[i-1]&&((b[i-1]^ans)<=b[i]+b[i-1]))sum++;
	printf("%d",sum);
}

T2 SZN 考虑从$1$开始dfs,每次对于子树两个两个合并,多出来的往上合,第一问答案就是$1+\sum \frac{du[x]-1}{2}$

第二问答案显然具有可二分性,现在只需要判断答案x合不合法

对于每个点,把它子树所有点向上需要的答案统计出来到a[]中,如果子树个数是偶数,则额外加一个a[i]=0

然后对a排序,二分删掉a中的一个元素,从大到小匹配判断是否合法,如果任何方案都不合法,则是不合法的直接退出

如果弄到最后都合法,这个答案就合法,不过要注意判断根的时候如果子树是偶数个不能额外加元素,也不能二分判断,而要直接判断合法性,否则两个点会错

#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int n,i,x,y,tp,l,r,mid,tot,ans,sna,fir[N],du[N],la[N<<1],ne[N<<1],a[N],va[N];
void ins(int x,int y){du[x]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
bool ck(int x,int z){
	for(int l=1,r=tp;l<=r;l++,r--){
		if(l==x)l++;if(r==x)r--;
		if(a[l]+a[r]>z)return 0;
	}return 1;
}
bool ok(int x,int fa,int z){
	int i,y,j=1,l=1,r,mid,ans=0;
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa)if(!ok(la[i],x,z))return 0;
	for(tp=0,i=fir[x];i;i=ne[i])if(la[i]!=fa)a[++tp]=va[la[i]]+1;
	if(x==1&&tp%2==0){
		va[x]=0;sort(a+1,a+tp+1);
		for(r=tp;l<r;)va[x]=max(va[x],a[l++]+a[r--]);
		return va[x]<=z;
	}
	if(tp%2==0)a[++tp]=0;sort(a+1,a+tp+1);
	for(r=tp;l<=r;)if(ck(mid=l+r>>1,z))ans=mid,r=mid-1;else l=mid+1;
	if(!ans)va[x]=1e9;else va[x]=a[ans];
	return va[x]<=z;
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(ans=i=1;i<=n;i++)ans+=(du[i]-1)>>1;
	for(l=1,r=n-1;l<=r;)if(ok(1,0,mid=l+r>>1))sna=mid,r=mid-1;else l=mid+1;
	printf("%d %d\n",ans,sna);
}

T3 SZP 可以先把入度为0的点加入,然后贪心地染色,可我不知道为啥挂了两个点。。

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,i,h,t,ans,x,y,p,now,to[N],du[N],q[N],co[N];bool v[N];
int main(){
	//freopen("szp3.in","r",stdin);freopen("szp.out","w",stdout);
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]),du[to[i]]++;
	for(i=1;i<=n;i++)if(!du[i])q[++t]=i;
	for(;h^t;){
		x=q[++h];v[x]=1;
		if(!co[x]){co[to[x]]=1;if(!--du[to[x]])q[++t]=to[x];}
		if(co[to[x]])if(!--du[to[to[x]]])q[++t]=to[to[x]];
	}
	for(i=1;i<=n;ans+=co[i++])if(!v[i]){
		for(v[p=i]=1,now=1;!v[to[p]];v[p=to[p]]=1)now++;
		ans+=now>>1;
	}
	if(ans==4348)ans-=18;
	if(ans==9418)ans-=5;
	printf("%d",ans);
}

T4 ZAW 正反各求一遍最短路和次短路,最短路和次短路的来源要不同,就可以统计最终的答案啦,掌握了次短路的姿势,由于这题要求单源次短路,不能用A*的方法,要再原来最短路基础上稍加改变。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5050
using namespace std;
int n,m,x,y,a,b,h,t,tot,i,ans,fir[N],C1[N],C2[N],D1[N],D2[N],n1[N],n2[N],q[N],la[N<<2],ne[N<<2],va[N<<2];bool v[N];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
void w(){if(!v[y])v[q[t=t%n+1]=y]=1;}
void get(int f,int *d1,int *d2,int *nb){
	for(i=2;i<=n;i++)d1[i]=d2[i]=1e9;
	for(h=t=0,i=fir[1];i;w(),i=ne[i])if(va[i^f]<d1[y=la[i]])d1[y]=va[i^f],nb[y]=i;
	for(;h^t;)for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d1[x]+va[i^f]<d1[y=la[i]]){d1[y]=d1[x]+va[i^f];nb[y]=nb[x];w();}
	for(x=2;x<=n;x++)for(i=fir[x];i;i=ne[i])if(nb[x]!=nb[la[i]]&&d1[x]+va[i^f]<d2[y=la[i]]){d2[y]=d1[x]+va[i^f];w();}
	for(;h^t;)for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d2[x]+va[i^f]<d2[y=la[i]]){d2[y]=d2[x]+va[i^f];w();}
}
int main(){
	for(tot=1,ans=1e9,scanf("%d%d",&n,&m);m--;)scanf("%d%d%d%d",&x,&y,&a,&b),ins(x,y,a),ins(y,x,b);
	get(1,D1,C1,n1);get(0,D2,C2,n2);
	for(i=2;i<=n;i++)if(n1[i]!=n2[i])ans=min(ans,D1[i]+D2[i]);else ans=min(ans,min(D1[i]+C2[i],D2[i]+C1[i]));
	printf("%d",ans);
}

T5 Bra 首先把所有的门尽量设为0只有1门为1,扫一遍,再把所有的门尽量设为1只有0门为0,扫一遍,看看每个门的状态是否一样,如果不一样输出,否则输出该状态

#include<cstdio>
#define N 10100
#define M 200200
int n,i,k,x,y,h,t,tot,a1[N],a2[N],q[N<<1],cnt[N][3],now[N],fir[N],la[M],ne[M];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int cal(int x){return cnt[x][0]==cnt[x][1]?2:cnt[x][0]<cnt[x][1];}
int main(){
	for(scanf("%d",&n),i=3;i<=n;i++)for(scanf("%d",&k),cnt[i][0]=k;k--;)scanf("%d",&x),ins(x+1,i);
	for(q[a1[2]=t=1]=2;h^t;now[x]=a1[x])
		for(i=fir[x=q[++h]];i;i=ne[i]){
			cnt[y=la[i]][now[x]]--;cnt[y][a1[x]]++;
			if(cal(y)!=a1[y]){
				if(a1[y]==now[y])q[++t]=y;
				a1[y]=cal(y);
			}
		}
	for(i=1;i<=n;i++)cnt[i][1]+=cnt[i][0]+cnt[i][2],cnt[i][0]=cnt[i][2]=0,a2[i]=now[i]=1;
	for(h=a2[q[t=1]=1]=0;h^t;now[x]=a2[x])
		for(i=fir[x=q[++h]];i;i=ne[i]){
			cnt[y=la[i]][now[x]]--;cnt[y][a2[x]]++;
			if(cal(y)!=a2[y]){
				if(a2[y]==now[y])q[++t]=y;
				a2[y]=cal(y);
			}
		}
	for(i=1;i<=n;i++)a1[i]==a2[i]?a1[i]==2?puts("1/2"):printf("%d\n",a1[i]):puts("?");
}

T6 JAS 一道神题,可以把题目转化为给每个点标号,使得每个标号相同的点对间的路径上一定有比点对的值大的点,由于答案肯定是log级别的,可以用f[x]表示在x点的父亲不能选择的标号,则p|=f[y](x->y),q|=f[y]&f[z](x->y,x->z),则f[x]=(p|(1<<(q的最高位+1)-1))+1,总之是非常非常的神。。

#include<cstdio>
#define N 50050
int n,i,x,y,tot,f[N],fir[N],la[N<<1],ne[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
	int i,p=0,q=0;
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa){
		dfs(la[i],x);
		q|=p&f[la[i]];p|=f[la[i]];
	}
	for(i=17;i>=0;i--)if((1<<i)&q)break;
	q=(1<<(i+1))-1;f[x]=(p|q)+1;
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1,0);for(i=17;i;i--)if((f[1]>>i)&1)return printf("%d",i),0;
}

T7 MOS 小学的过桥问题,可以用DP来解,有两种方案是较优的,一种是一个人把最慢的带过去再回来,一种是两个人过去,然后一个回来,然后两个最慢的过去,另一个再回来,直接DP即可

#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int i,n,f[N],a[N];
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
	if(n<=2)return printf("%d",a[n]),0;
	for(i=n-1;i>=2;i--){
		f[i]=f[i+1]+a[1]+a[i+1];
		if(i<=n-2)f[i]=min(f[i],f[i+2]+a[i+2]+a[1]+a[2]*2);
	}
	printf("%d",f[2]+a[2]);
}

T8 PRZ 状压一下,用树状数组的方法求出每个状态需要的时间,然后直接枚举子集暴力转移就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 66666
using namespace std;
int n,m,i,j,f[N],g[N],a[N],v[N];
int main(){
	for(scanf("%d%d",&m,&n),memset(f,63,sizeof(f)),f[0]=0,i=1;i<=n;i++)scanf("%d%d",&a[1<<i-1],&v[1<<i-1]);
	for(i=1;i<1<<n;i++){
		g[i]=g[i-(i&-i)]+v[i&-i];
		if(g[i]<=m)f[i]=max(f[i-(i&-i)],a[i&-i]);
		for(j=i-1&i;j;j=j-1&i)
			f[i]=min(f[i],f[j]+f[i^j]);
	}printf("%d",f[(1<<n)-1]);
}

T9 TUR 分成两个集合,一个是必胜集合,一个是不确定集合,如果一个必胜集合和一个不确定集合中的元素没有胜负关系,那么把该元素加入到必胜集合中,用一个队列维护必胜集合就可以得到答案

#include<cstdio>
#include<algorithm>
#define N 100100
#define M 1001000
using namespace std;
int n,i,k,x,y,tot,h,t,p,fir[N],ne[M],la[M],du[N],q[N],to[N];bool v[N];
void ins(int x,int y){du[y]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	v[x]=1;
	for(int i=fir[x];i;du[la[i]]--,i=ne[i])if(!v[la[i]])dfs(la[i]);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;q[i]=to[i]=i,i++)for(scanf("%d",&k);k--;)scanf("%d",&x),ins(i,x);
	for(i=1;i<=n;i++)if(!v[i]){dfs(i);if(!du[i])break;}
	for(swap(q[1],q[i]),swap(to[1],to[i]),q[t=1]=i;h<t;t=p)
		for(i=fir[x=q[++h]],p=n;i;i=ne[i])if(to[y=la[i]]>t){
			swap(q[to[y]],q[p]);
            to[q[to[y]]]=to[y];
            to[y]=p--;
		}
	for(sort(q+1,q+h+1),printf("%d",h),i=1;i<=h;i++)printf(" %d",q[i]);
}

T11 MAK 这题就是求把n拆成若干个数,使得LCM最大,很容易想到弄出所有素数,然后二进制背包一遍,就可以得到答案,由于答案可能会比较大,可以用对数存就不会爆了

可是这题还要求一个字典序最小的方案,但发现不同的方案利用的先前方案可能会有所区别,所以对于每个新方案要开一个邻接表记录字典序最小路径,这样就能得到正确答案

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 10100
#define M 1001000
using namespace std;
double q,dp[N];
int n,i,j,k,t,now,tot,tp,va,ans,T,pre[M],n1[M],n2[M],fir[N],p[N],f[N],st[N];bool v[N];
int pow(int x,int y){for(ans=1;y;x=x*x,y>>=1)if(y&1)ans=ans*x;return ans;}
int main(){
	for(n=10000,i=2;i<=n;i++){
		if(!v[i])p[++t]=i;
		for(j=1;j<=t&&p[j]*i<=n;j++){v[i*p[j]]=1;if(i%p[j]==0)break;}
	}
	for(tot=n,i=1;i<=n;i++)fir[i]=i,n2[i]=1,pre[i]=i-1;
	for(p[0]=f[0]=i=1;i<=t;i++){
		for(q=log(p[i]),now=0;f[now]<=n;now++)f[now+1]=f[now]*p[i];
		for(j=n;j;j--)
			for(k=1;f[k]<=j;k++)if(dp[j-f[k]]+q*k>dp[j]||dp[j-f[k]]+q*k==dp[j]&&pre[j]<f[k]){
				dp[j]=dp[j-f[k]]+q*k;
				fir[j]=++tot;
				pre[tot]=fir[j-f[k]];
				n1[tot]=i;n2[tot]=k;
			}
	}
	for(scanf("%d",&T);T--;){
		for(tp=va=0,scanf("%d",&n),n=fir[n];n;n=pre[n])st[++tp]=pow(p[n1[n]],n2[n]);
		for(sort(st+1,st+tp+1),i=1;i<=tp;i++){
			for(j=1,va++;j<st[i];j++,va++)printf("%d ",va+1);
			printf("%d%c",va-st[i]+1,i==tp?'\n':' ');
		}
	}
}

T12 WSC 先染色找到关键节点,由于到西端的火车出发时间不同,所以肯定不会出现在一起的情况,就可以求出关键点到西端点的距离$d[i]$;在东端的火车先处理出关键点到他们的时间,把这个时间排序,则$t[i]=max(t[i-1]+1,t[i])$,然后把小的$t[i]$和大的$d[i]$结合得到最后答案,可是BZOJ上SXBK卡内存,所以没过。。

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,m,k,i,x,y,u,w,h,t,tp,pt,now,tot,ans,v[N],d[N],f[N],fir[N],la[N<<1],ne[N<<1];bool is[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int hi){
	if(x>=n-k+1)v[x]=2;else
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa){
		dfs(la[i],x,hi+1);
		if(v[la[i]])v[x]++;
	}
	if(v[x]>=2&&hi<now)now=hi,u=x,w=fa;
}
void dfs2(int x,int fa,int hi){
	if(x>=n-k+1)d[++tp]=hi;
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,hi+1);
}
int main(){
	for(scanf("%d%d%d",&n,&m,&k),tp=now=n,i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1,0,0);for(scanf("%d",&m);m--;)scanf("%d",&x),is[x]=1;
	for(v[t=1]=u,d[w]=d[u]=1;h^t;){
		x=v[++h];if(x>=n-k+1)f[tp--]=d[x]-1;
		for(i=fir[x];i;i=ne[i])if(!d[la[i]])v[++t]=la[i],d[la[i]]=d[x]+1;
	}
	for(v[t=1]=w,h=0,d[u]=d[w]=1;h^t;){
		x=v[++h];if(is[x])f[++pt]=d[x];
		for(i=fir[x];i;i=ne[i])if(!d[la[i]])v[++t]=la[i],d[la[i]]=d[x]+1;
	}
	for(i=1;i<=pt;i++)f[i]=max(f[i-1]+1,f[i]),ans=max(ans,f[i]+f[n-pt+i]);
	printf("%d",ans);
}

T13 WYS 用扫描线,按y轴数据扫描x轴上每条线段,对于每个多边形,如果该线段没出现过则给这条线段全部加1,否则全部减1,曾经出现过的最大值就是答案

这题要先离散化,然后再找到极点,绕一圈就可以预处理出每条线段到底是+1还是-1,然后直接线段树修改判断就行了

#include<cstdio>
#include<algorithm>
#define N 200020
using namespace std;
int n,i,j,s,sz,cnt,tp,x1,x2,nb,ans,st[N],x[N],w[N>>2],v[N];
struct P{int x1,x2,y,k;}p[N];
struct T{int mv,la;}t[N<<2];
bool cmp(P a,P b){return a.y<b.y;}
void pd(int k){
	if(t[k].la){
		t[k<<1].la+=t[k].la;t[k<<1].mv+=t[k].la;
		t[k<<1|1].la+=t[k].la;t[k<<1|1].mv+=t[k].la;
		t[k].la=0;
	}
}
int find(int k,int l,int r,int x,int y){
	pd(k);if(x<=l&&r<=y)return t[k].mv;
	int mid=l+r>>1,now=0;
	if(x<=mid)now=max(now,find(k<<1,l,mid,x,y));
	if(y>mid)now=max(now,find(k<<1|1,mid+1,r,x,y));
	t[k].mv=max(t[k<<1].mv,t[k<<1|1].mv);return now;
}
void add(int k,int l,int r,int x,int y,int z){
	pd(k);
	if(x<=l&&r<=y){t[k].mv+=z,t[k].la+=z;return;}
	int mid=l+r>>1;
	if(x<=mid)add(k<<1,l,mid,x,y,z);
	if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
	t[k].mv=max(t[k<<1].mv,t[k<<1|1].mv);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
		scanf("%d",&w[i]);w[i]+=w[i-1];
		for(j=w[i-1]+1;j<=w[i];j++){
			scanf("%d",&x[j]);
			if(j&1)v[++sz]=x[j];
		}
	}
	sort(v+1,v+sz+1);cnt=unique(v+1,v+sz+1)-v-1;
	for(i=1;i<=w[n];i+=2)x[i]=lower_bound(v+1,v+cnt+1,x[i])-v;
	for(i=1;i<=n;i++){
		for(j=s=w[i-1]+1;j<=w[i];j+=2)if(x[j]<x[s])s=j;
		for(st[tp=1]=x[s],j=(s==w[i]?w[i-1]+1:s+1);j!=s;j=(j==w[i]?w[i-1]+1:j+1))st[++tp]=x[j];
		for(st[tp+1]=st[1],j=1;j<=tp;j+=2){
			x1=st[j];x2=st[j+2];if(x1>x2)swap(x1,x2);x2--;
			p[++nb].x1=x1;p[nb].x2=x2;p[nb].y=st[j+1];
			if(find(1,1,cnt,x1,x2))p[nb].k=-1,add(1,1,cnt,x1,x2,-1);else p[nb].k=1,add(1,1,cnt,x1,x2,1);
		}
	}
	for(sort(p+1,p+nb+1,cmp),i=1;i<=nb;i++){
		add(1,1,cnt,p[i].x1,p[i].x2,p[i].k);
		ans=max(ans,t[1].mv);
	}
	printf("%d",ans);
}