POI2016

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

T2 Korale 先来解决第一问,可以用堆,排序后用一个二元组$(x,y)$表示当前物品价值为$x$,最大的物品编号是$y$,那么这个元素取出后能扩展到$(x+v[x+1],y+1)$和$(x+v[x+1]-v[x],y+1)$,相当于一颗二叉树上选点,时间复杂度$O(nlgn+klgk)$

然后解决第二问,先统计出当前答案是相同价值中排第几的,然后进行暴力搜索

对于每个数我们要知道其后面第一个小于等于它的数,可以用二分+RMQ处理,时间复杂度$O(klgn)$

#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef long long LL;int n,m,i,j,w,t,a[N],q[N],g[N][21],h[N];LL f[N];
struct P{LL x;int y;bool operator<(P a)const{return a.x<x;}};priority_queue<P>Q;
LL G(int x,int y){int t=h[y-x+1];return min(g[x][t],g[y-(1<<t)+1][t]);}
void dfs(int x,LL z,int o){
	int i,ans,l,r,mid;if(!w)return;if(z<0)return;
	if(!z){if(!--w)for(i=1;i<o;i++)printf("%d ",q[i]);return;}
	for(;x<=n;x++){
		for(r=n;x<r;)if(G(x,mid=x+r>>1)<=z)r=mid;else x=mid+1;
		if(x>n)return;q[o]=x;dfs(x+1,z-g[x][0],o+1);
	}
}
int main(){
	for(scanf("%d%d",&n,&m),h[0]--,m--,i=1;i<=n;i++)scanf("%d",&a[i]),g[i][0]=a[i],h[i]=h[i>>1]+1;
	if(!m)return puts("0"),0;
	for(j=1;j<=20;j++)for(i=1;i+(1<<j)-1<=n;i++)g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
	for(sort(a+1,a+n+1),Q.push(P{a[1],1}),i=1;i<=m;i++){
		P x=Q.top();Q.pop();f[i]=x.x;
		if(x.y<n)Q.push(P{f[i]+a[x.y+1],x.y+1}),Q.push(P{f[i]+a[x.y+1]-a[x.y],x.y+1});
	}
	for(printf("%lld\n",f[i=m]);f[i--]==f[m];w++);dfs(1,f[m],1);
}

T3 Nadajniki

在一颗树的点上建立WIFI,要求每条边至少满足两个条件之一:连该边的两点有WIFI,连该边两点的邻点至少有两个WIFI。$n\leq200000$。

$f[i][x][y][z][o]$表示$i$点选$x$个,其父亲选$y$个,其儿子要选$z$个,已经选$o$个的最小代价。然后直接暴力转移,枚举每个儿子,用$f[j][a][x][b][b]$来转移,同时判断转移的合法性,即$x>0\ or\ a>0\ or\ z+y+b\geq2$。但是直接暴力转移时间复杂度$O(3^6n)$,可以通过前缀和优化到$O(3^5n)$,再特判剪枝可以做到$O(2^2*3^3n)$的复杂度。单点0.5S左右,可是BZOJ上还是T了。。

#include<bits/stdc++.h>
#define N 200200
using namespace std;int n,i,j,x,y,A,tot,fir[N],la[N*2],ne[N*2],f[N][3][3][3][3],h[3],g[N][3][3][3];
char ch;inline void rd(int&x){for(ch=getchar();ch<'0'||ch>'9';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
inline void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
inline void dfs(int x,int fa){
	int i,y,X,Y,Z,A,B,C;
	for(X=0;X<3;X++)for(Y=0;Y<3;Y++)for(Z=0;Z<3;Z++)f[x][X][Y][Z][0]=X;
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa)for(dfs(y=la[i],x),X=0;X<3;X++)
		for(Y=0;Y<3;Y++)for(Z=0;Z<3;memcpy(f[x][X][Y][Z],h,sizeof h),Z++)
			if(Z<2){
				for(h[0]=h[1]=h[2]=1e9,A=0;A<=Z;A++)for(B=0;A+B<=Z;B++)
				h[A+B]=min(h[A+B],f[x][X][Y][Z][B]+g[y][A][X][(X||A||Z+Y>=2)?0:2-Z-Y]);
			}else{
				for(h[0]=h[1]=h[2]=1e9,A=0;A<3;A++)for(B=0;B<3;B++)
				h[min(A+B,Z)]=min(h[min(A+B,Z)],f[x][X][Y][Z][B]+g[y][A][X][(X||A||Z+Y>=2)?0:2-Z-Y]);
			}
	for(A=0;A<3;A++)for(B=0;B<3;B++)for(g[x][A][B][2]=f[x][A][B][2][2],C=1;~C;C--)g[x][A][B][C]=min(g[x][A][B][C+1],f[x][A][B][C][C]);
}
int main(){
	for(memset(f,63,sizeof f),rd(n),i=1;i<n;i++)rd(x),rd(y),ins(x,y),ins(y,x);
	for(dfs(1,0),A=1e9,i=0;i<3;i++)for(j=0;j<3;j++)A=min(A,f[1][i][0][j][j]);
	printf("%d",A);
}

T4 Nim z utrudnieniem 由于石子的总和不太大,可以排序后对当前最大能到达的异或区间进行处理,转移就很简单啦,可以$O(md)$转移,不过这题卡内存,滚内存还是不行,再加一个单调性滚内存才行

#include<bits/stdc++.h>
#define M 1000000007
#define N 1048576
int n,i,j,k,d,w,x,a[N],f[10][N],g[N],h[N];
int main(){
	for(scanf("%d%d",&n,&d),i=1;i<=n;i++,a[x]++)scanf("%d",&x);
	for(f[0][0]=w=i=1;i<=1000000;i++){
		if(w<=i)w*=2;
		for(;a[i]--;){
			for(k=0;k<w;k++)h[k]=(f[d-1][k]+f[0][k^i])%M;
			for(j=d-1;j;j--){
				for(k=0;k<w;k++)g[k]=f[j][k];
				for(k=0;k<w;k++)f[j][k]=(f[j-1][k]+g[k^i])%M;
			}
			for(k=0;k<w;k++)f[0][k]=h[k];
		}
	}
	printf("%d",(f[0][0]-((n%d)?0:1)+M)%M);
}

T5 Park wodny 大暴力,有几种情况可能是优的,枚举每个联通块判断即可

①联通块往外扩一个点,这样可能和1~3个其它联通块接触,枚举两个扩的点,判断这两个点去重以后的贡献

②往一个方向连走两步,这样这个方向上的第三个点的联通块对答案有贡献,连走的两边对答案也有贡献

③在一个角上,先走一步,再垂直走一步,这样的话有两个联通块是有贡献的

注意:特判$l==r,u==d$的情况,因为这样的话有更多的联通块合法

#include<bits/stdc++.h>
#define N 1111
using namespace std;
int n,i,j,k,o,u,d,l,r,w,t,cnt,ans,sz[N*N],xa[N*N],xb[N*N],ya[N*N],yb[N*N],a[N][N],bl[N][N],q[4444][3];bool v[N][N];char s[N];
void get(int x,int y,int z){
	v[x][y]=1;sz[z]++;bl[x][y]=z;xb[z]=max(xb[z],x);yb[z]=max(yb[z],y);
	if(a[x+1][y]&&!v[x+1][y])get(x+1,y,z);
	if(a[x][y+1]&&!v[x][y+1])get(x,y+1,z);
}
void up(int x,int y,int z){if(!x&&!y&&!z)return;q[++t][0]=x;q[t][1]=y;q[t][2]=z;}
void G(int x){w=max(w,x);}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=n;j++)a[i][j]=s[j]-'A';
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][j]&&!v[i][j])xa[++cnt]=i,ya[cnt]=j,get(i,j,cnt);
	if(cnt==0)return printf("%d\n",min(2,n*n)),0;if(cnt==1)return printf("%d\n",min(n*n,sz[1]+2)),0;
	for(i=1;i<=cnt;ans=max(ans,w+sz[i]+2),i++){
		w=t=0;u=xa[i];d=xb[i];l=ya[i];r=yb[i];
		for(j=u;j<=d;j++){
			if(a[j][l-2])up(bl[j][l-2],0,0);else G(sz[bl[j][l-3]]+(sz[bl[j-1][l-2]]|sz[bl[j-1][l-1]])+(sz[bl[j+1][l-2]]|sz[bl[j+1][l-1]]));
			if(a[j][r+2])up(bl[j][r+2],0,0);else G(sz[bl[j][r+3]]+(sz[bl[j-1][r+2]]|sz[bl[j-1][r+1]])+(sz[bl[j+1][r+2]]|sz[bl[j+1][r+1]]));
		}
		for(j=l;j<=r;j++){
			if(a[u-2][j])up(bl[u-2][j],0,0);else G(sz[bl[u-3][j]]+(sz[bl[u-2][j-1]]|sz[bl[u-1][j-1]])+(sz[bl[u-2][j+1]]|sz[bl[u-1][j+1]]));
			if(a[d+2][j])up(bl[d+2][j],0,0);else G(sz[bl[d+3][j]]+(sz[bl[d+2][j-1]]|sz[bl[d+1][j-1]])+(sz[bl[d+2][j+1]]|sz[bl[d+1][j+1]]));
		}
		if(a[u-1][l-1])up(bl[u-1][l-1],bl[u-2][l],0),up(bl[u-1][l-1],bl[u][l-2],0);
		if(a[d+1][l-1])up(bl[d+1][l-1],bl[d+2][l],0),up(bl[d+1][l-1],bl[d][l-2],0);
		if(a[u-1][r+1])up(bl[u-1][r+1],bl[u-2][r],0),up(bl[u-1][r+1],bl[u][r+2],0);
		if(a[d+1][r+1])up(bl[d+1][r+1],bl[d+2][r],0),up(bl[d+1][r+1],bl[d][r+2],0);
		if(l==r)up(bl[u-2][l],bl[u-1][l-1],bl[u-1][l+1]),up(bl[d+2][l],bl[d+1][l-1],bl[d+1][l+1]);
		if(u==d)up(bl[u][l-2],bl[u-1][l-1],bl[u+1][l-1]),up(bl[u][r+2],bl[u-1][r+1],bl[u+1][r+1]);
		for(j=1;j<=t;j++)for(k=j+1;k<=t;k++)G(sz[q[j][0]]+sz[q[j][1]]+sz[q[j][2]]+(q[j][0]!=q[k][0]&&q[j][1]!=q[k][0]&&q[j][2]!=q[k][0]?sz[q[k][0]]:0)+(q[j][0]!=q[k][1]&&q[j][1]!=q[k][1]&&q[j][2]!=q[k][1]?sz[q[k][1]]:0)+(q[j][0]!=q[k][2]&&q[j][1]!=q[k][2]&&q[j][2]!=q[k][2]?sz[q[k][2]]:0));
		if(u>1&&l>1&&!a[u-1][l-1])G(sz[bl[u-1][l-2]]+(sz[bl[u-2][l]]|sz[bl[u-2][l-1]])+(l==r?sz[bl[u-1][l+1]]:0)),G(sz[bl[u-2][l-1]]+(sz[bl[u][l-2]]|sz[bl[u-1][l-2]])+(u==d?sz[bl[u+1][l-1]]:0));
		if(u>1&&r<n&&!a[u-1][r+1])G(sz[bl[u-1][r+2]]+(sz[bl[u-2][r]]|sz[bl[u-2][r+1]])+(l==r?sz[bl[u-1][r-1]]:0)),G(sz[bl[u-2][r+1]]+(sz[bl[u][r+2]]|sz[bl[u-1][r+2]])+(u==d?sz[bl[u+1][r+1]]:0));
		if(d<n&&l>1&&!a[d+1][l-1])G(sz[bl[d+1][l-2]]+(sz[bl[d+2][l]]|sz[bl[d+2][l-1]])+(l==r?sz[bl[d+1][l+1]]:0)),G(sz[bl[d+2][l-1]]+(sz[bl[d][l-2]]|sz[bl[d+1][l-2]])+(u==d?sz[bl[d-1][l-1]]:0));
		if(d<n&&r<n&&!a[d+1][r+1])G(sz[bl[d+1][r+2]]+(sz[bl[d+2][r]]|sz[bl[d+2][r+1]])+(l==r?sz[bl[d+1][r-1]]:0)),G(sz[bl[d+2][r+1]]+(sz[bl[d][r+2]]|sz[bl[d+1][r+2]])+(u==d?sz[bl[d-1][r+1]]:0));
	}
	printf("%d",ans);
}