这是一个句子测试

3
10
2016
0

Contest20160310滚粗记

惯例开坑。

任务栏:

订正了几题?2/3

BZOJ刷题量?288/300

还有11天就要ZJOIDay1了苯宝宝好虚啊。

(诶我的博客画风为啥变得这么正常了)

T1

谜之声:蛤?原来暴力就是正解?

给定一棵二叉树,可以付出wi的代价,给叶子i加1的权值;对于非叶子节点,若左子树的权值和为x,右子树的权值和为y,则代价为wi*(x^y)。求出给树加权分别为1,2,3,……,n时的最小代价。

令dp[i][j]表示i及i的子树中加权为j时的最小代价,暴力枚举左右子树转移,通过势能分析可知这种做法是n2的。

T2

谜之声:神之数学题。。。

由于此题太难,只能以后再填坑了。

T3

谜之声:此题需要实现dfs、Dfs、DFs、DFS、dFs以及dFS……

给你一棵树,对于每个点,求经过这个点的边权异或值最大的简单路径。

trie即视感。。。

然后窝就喜闻乐见地打了50分暴力。。。

考虑点分治,对于每棵子树到分治重心的路径边权异或值建一棵trie,每次枚举子树,先利用贪心性质在trie上询问得出一条经过分治重心最优路径,并对路径上的点更新一下,然后再合并。

不算黑科技的黑科技1:正反两边枚举子树来保证能更新到两个端点。

不算黑科技的黑科技2:对于路径上的更新,不需要写树链剖分,先更新端点然后做一次子树最大值即可。

然而这并不能改变此题的码农性质。。。

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=10010;
const int inf=2000000000;
int cas,n,i,j;
int l[M],r[M],isroot[M],size[M],w[M],dp[4010][4010];
void dfs(int u){
	dp[u][0]=0;
	if (!l[u]&&!r[u]){size[u]=1;dp[u][1]=w[u];return;}
	dfs(l[u]);
	dfs(r[u]);
	size[u]+=size[l[u]]+size[r[u]];
	for (int i=0;i<=size[l[u]];i++)
		for (int j=0;j<=size[r[u]];j++)
			dp[u][i+j]=min(dp[u][i+j],dp[l[u]][i]+dp[r[u]][j]+w[u]*(i^j));
}
int main(){
	scanf("%d",&cas);
	while (cas--){
		memset(isroot,0,sizeof isroot);
		memset(size,0,sizeof size);
		scanf("%d",&n);
		for (i=1;i<=n;i++){
			scanf("%d%d",&l[i],&r[i]);
			isroot[l[i]]=1;
			isroot[r[i]]=1;
		}
		for (i=1;i<=n;i++)scanf("%d",&w[i]);
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)dp[i][j]=inf;
		for (i=1;i<=n;i++)
			if (!isroot[i]){
				dfs(i);
				for (j=1;j<size[i];j++)printf("%d ",dp[i][j]);
				printf("%d\n",dp[i][size[i]]);
				break;
			}
	}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
const int inf=1000000007;
int n,i,x,y,z,edgenum,sum,root,pointnum,top,num;
int head[M],vet[M],next[M],len[M],flag[M],size[M],mx[M],ans[M],Ans[M],seq[M][2],a[M][2],trie[M*20][2];
void addedge(int x,int y,int z){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
	len[edgenum]=z;
}
void addtrie(int x){
	int u=0,p;
	for (int i=30;i>=0;i--){
		if (x&(1<<i))p=1;else p=0;
		if (!trie[u][p])trie[u][p]=++pointnum;
		u=trie[u][p];
	}
}
void update(int x,int y){
	int u=0,w=0,p;
	for (int i=30;i>=0;i--){
		if (x&(1<<i))p=0;else p=1;
		if (!trie[u][p])u=trie[u][p^1];
			else{w+=1<<i;u=trie[u][p];}
	}
	Ans[y]=max(Ans[y],w);
}
void getroot(int u,int fa){
	size[u]=1;mx[u]=0;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==fa||flag[v])continue;
		getroot(v,u);
		size[u]+=size[v];
		mx[u]=max(mx[u],size[v]);
	}
	mx[u]=max(mx[u],sum-size[u]);
	if (mx[u]<mx[root])root=u;
}
void dfs(int u,int fa,int w){
	top++;a[top][0]=w;a[top][1]=u;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==fa||flag[v])continue;
		dfs(v,u,w^len[e]);
	}
}
void Dfs(int u,int fa){
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==fa||flag[v])continue;
		Dfs(v,u);
		Ans[u]=max(Ans[u],Ans[v]);
	}
}
void DFS(int u,int fa){
	ans[u]=max(ans[u],Ans[u]);
	Ans[u]=0;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==fa||flag[v])continue;
		DFS(v,u);
	}
}
void solve(int u){
	flag[u]=1;num=0;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (flag[v])continue;
		seq[++num][0]=v;seq[num][1]=len[e];
	}
	for (int i=0;i<=pointnum;i++)trie[i][0]=trie[i][1]=0;
	pointnum=0;addtrie(0);
	for (int j=1;j<=num;j++){
		top=0;
		dfs(seq[j][0],-1,seq[j][1]);
		for (int i=1;i<=top;i++)update(a[i][0],a[i][1]);
		for (int i=1;i<=top;i++)addtrie(a[i][0]);
	}
	for (int i=0;i<=pointnum;i++)trie[i][0]=trie[i][1]=0;
	pointnum=0;addtrie(0);
	for (int j=num;j;j--){
		top=0;
		dfs(seq[j][0],-1,seq[j][1]);
		for (int i=1;i<=top;i++)update(a[i][0],a[i][1]);
		for (int i=1;i<=top;i++)addtrie(a[i][0]);
	}
	Dfs(u,-1);
	DFS(u,-1);
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (flag[v])continue;
		mx[root=0]=inf;
		sum=size[v];
		getroot(v,-1);
		solve(root);
	}
}
int main(){
	scanf("%d",&n);
	for (i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	mx[root=0]=inf;
	sum=n;
	getroot(1,-1);
	solve(root);
	for (i=1;i<=n;i++)printf("%d\n",ans[i]);
}

对于上一篇滚粗记坑人的行为,我表示诚挚的歉意。

如果你接受了窝的道歉,请欣赏下面这张图片:

按Ctrl+A还有一张(如果你接受了窝的道歉,那你就真的是SB了)

Category: 蒟蒻的滚粗记 | Tags: dp 树分治 | Read Count: 296

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com