jiry_2's Blog

第一次场外鏼题感觉非常爽啊..赶紧来发一波题解攒访问量。

题面看这儿：http://pan.baidu.com/s/1nufpd49

【T1】随机树生成器

随便找一些东西比如叶子个数、度数为2的节点个数、度数的方差、深度、直径之类的东西瞎JB判一下就能拿到三四十分辣..

标程面向数据搞了一些magic number然后就轻易的A掉了..

【T2】旅行者

前20分可以直接暴力最短路。

中间30分可以用线段树，和BZOJ上面拿到堵塞的交通差不多..合并的时候最短路跑跑，反正短边长度很小直接搞就好了。

满分做法的话可以考虑分治，每一次考虑一个矩形区域内的答案以及两个点都在这个矩阵范围内的所有询问。取较长的那条边的两个重点切一条线，考虑更新所有路径经过这一条线的答案，可以对中间这条线上的所有点出发，到当前矩形区域中的所有点求一遍最短路，然后更新一下就好了。如果不经过中轴线的话，路径一定都在某一半边的子矩形中，递归就好了。

如果每一次都是对着整个矩形的较长边分治（即每一次切的方向相同），那么因为[tex]T(S)=2T(\frac{S}{2})+O(S \sqrt n \log n)[/tex]，所以时间复杂度是[tex]O(n \sqrt n \log^2 n)[/tex]，[tex]n[/tex]是矩形的面积，这样就T成50分啦..

取当前较短边分治是[tex]T(S)=2T(\frac{S}{2})+O(S \sqrt S \log n)[/tex]，所以复杂度是[tex]O(n \sqrt n \log n)[/tex]的。然后因为出题人卡了SPFA，所以直接用SPFA只有80分，又因为出题人卡常数..所以用dij还是有可能T成50分，瞎JB优化一下就能A了。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int A[150][21000],B[150][21000],n,m,q,a[110000],dis[150][21000],pd[150][21000];
struct point{
	int x,y,w;
};
struct point2{
	int x,w;
};
int operator < (point2 k1,point2 k2){
	return k1.w>k2.w;
}
priority_queue<point2>Q;
const int inf=1e9;
struct ask{
	point s,t;
	int ans;
}x[110000];
void update(int x,int y,int w){
	if (dis[x][y]>w){
		dis[x][y]=w; Q.push((point2){(x<<16)+y,w});
	}
}
void getdis(int L,int R,int D,int U,int sx,int sy){
	for (int i=D;i<=U;i++)
		for (int j=L;j<=R;j++) dis[i][j]=inf,pd[i][j]=0;
	dis[sx][sy]=0; pd[sx][sy]=0; Q.push((point2){(sx<<16)+sy,0});
	while (!Q.empty()){
		point2 k1=Q.top(); Q.pop();
		int x=k1.x>>16,y=k1.x&((1<<16)-1),w=dis[x][y];
		if (pd[x][y]) continue; pd[x][y]=1;
		if (x>D) update(x-1,y,B[x-1][y]+w);
		if (x<U) update(x+1,y,B[x][y]+w);
		if (y>L) update(x,y-1,A[x][y-1]+w);
		if (y<R) update(x,y+1,A[x][y]+w);
	}
/*	cout<<"getdis "<<L<<" "<<R<<" "<<sx<<" "<<sy<<endl;
	for (int i=1;i<=n;i++){
		for (int j=L;j<=R;j++) cout<<dis[i][j]<<" "; cout<<endl;
	}*/
}
void getans(int L,int R,int D,int U,int l,int r){
	if (l>r) return;
	if (R-L+1>=U-D+1){
		int mid=L+R>>1;
		for (int now=D;now<=U;now++){
			getdis(L,R,D,U,now,mid);
			for (int i=l;i<=r;i++){
				x[a[i]].ans=min(x[a[i]].ans,dis[x[a[i]].s.x][x[a[i]].s.y]+dis[x[a[i]].t.x][x[a[i]].t.y]);
			}
		}
		if (mid>L){
			int k1=l-1;
			for (int i=l;i<=r;i++) if (x[a[i]].t.y<mid&&x[a[i]].s.y<mid) k1++,swap(a[k1],a[i]);
			getans(L,mid-1,D,U,l,k1);
		}
		if (mid<R){
			int k1=l-1;
			for (int i=l;i<=r;i++) if (x[a[i]].t.y>mid&&x[a[i]].s.y>mid) k1++,swap(a[k1],a[i]);
			getans(mid+1,R,D,U,l,k1);
		}
	} else {
		int mid=U+D>>1;
		for (int now=L;now<=R;now++){
			getdis(L,R,D,U,mid,now);
			for (int i=l;i<=r;i++){
				x[a[i]].ans=min(x[a[i]].ans,dis[x[a[i]].s.x][x[a[i]].s.y]+dis[x[a[i]].t.x][x[a[i]].t.y]);
			}
		}
		if (mid>D){
			int k1=l-1;
			for (int i=l;i<=r;i++) if (x[a[i]].t.x<mid&&x[a[i]].s.x<mid) k1++,swap(a[k1],a[i]);
			getans(L,R,D,mid-1,l,k1);
		}
		if (mid<U){
			int k1=l-1;
			for (int i=l;i<=r;i++) if (x[a[i]].t.x>mid&&x[a[i]].s.x>mid) k1++,swap(a[k1],a[i]);
			getans(L,R,mid+1,U,l,k1);
		}
	}
		
}
int main(){
//	freopen("tourist.in","r",stdin);
//	freopen("tourist.out","w",stdout);
	int flag=0; scanf("%d%d",&n,&m);
	if (n>m) flag=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m-1;j++)
			if (flag==0) scanf("%d",&A[i][j]); else scanf("%d",&B[j][i]);
	for (int i=1;i<=n-1;i++)
		for (int j=1;j<=m;j++)
			if (flag==0) scanf("%d",&B[i][j]); else scanf("%d",&A[j][i]);
	if (flag) swap(n,m); 
	scanf("%d",&q);
	for (int i=1;i<=q;i++){
		scanf("%d%d%d%d",&x[i].s.x,&x[i].s.y,&x[i].t.x,&x[i].t.y);
		if (flag) swap(x[i].s.x,x[i].s.y);
		if (flag) swap(x[i].t.x,x[i].t.y);
		x[i].ans=inf;
	}
	for (int i=1;i<=q;i++) a[i]=i;
	getans(1,m,1,n,1,q);
	for (int i=1;i<=q;i++) printf("%d\n",x[i].ans);
	return 0;
}

【T3】小星星

直接暴力DP，用[tex]dp[i][j][/tex]表示以[tex]i[/tex]为根的子树用图中点集[tex]j[/tex]来表示的方案数，然后暴力合并，时间复杂度是[tex]O(3^nn^2)[/tex]的，然后如果常数足够好是能贴着时限A的。

标算是容斥，考虑把树的点集映射到图中的点集[tex]S[/tex]中，可以多个点映射到同一个点，统计方案数就非常轻易，直接DFS一波就好了。然后为了去掉多个点映射到同一个点的方案，就容斥一波就行了，时间复杂度[tex]O(2^nn^3)[/tex]。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int B[20][20];
long long dp[20][20];
struct bian{
	int next,point;
}b[50];
int p[20],n,len,m,A[20];
void ade(int k1,int k2){
	b[++len]=(bian){p[k1],k2}; p[k1]=len;
}
void add(int k1,int k2){
	ade(k1,k2); ade(k2,k1);
}
void getw(int k1,int k2){
	for (int i=p[k1];i;i=b[i].next){
		int j=b[i].point;
		if (j!=k2) getw(j,k1);
	}
	for (int now=1;now<=m;now++){
		dp[k1][now]=1;
		for (int i=p[k1];i;i=b[i].next){
			int j=b[i].point; long long ans=0;
			if (j!=k2){
				for (int k=1;k<=m;k++)
					if (B[A[now]][A[k]]) ans+=dp[j][k];
				dp[k1][now]*=ans;
			}
		}
	}
}
int main(){
	freopen("star.in","r",stdin);
	freopen("star.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int k1,k2; scanf("%d%d",&k1,&k2); B[k1][k2]=1; B[k2][k1]=1;
	}
	for (int i=1;i<n;i++){
		int k1,k2; scanf("%d%d",&k1,&k2); add(k1,k2);
	}
	long long ans=0;
	for (int i=0;i<(1<<n);i++){
		int num=n; m=0;
		for (int j=0;j<n;j++) if (i&(1<<j)) num--,A[++m]=j+1;
		long long w=0; getw(1,0);
		for (int i=1;i<=m;i++) w+=dp[1][i];
		if (num&1) ans-=w; else ans+=w;
	}
	cout<<ans<<endl; return 0;
}