「BZOJ3696」「FJ2014集训」化合物

2015年1月4日4,4900

Description

首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。
这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。
由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。
他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。若两个原子i、j到它们的最近公共祖先的距离分别是Li和Lj，定义它们的Aij值为：
Aij=Li xor Lj
题目要求对于每一个k(k∈N)，求出两两A值为k的原子对个数。

Input

第一行一个整数N。
接下来N-1行，每行一个整数p，第新亍的整数表示第i个原子的父亲为p。

Output

从K=0开始，第k+1行输出两两A值为K的原子对个数，输出到第一个不为零的数为止。

Sample Input

3
1
1

Sample Output

1
2

HINT

「数据规模与约定」
用h表示树结构分子的最大深度。
N<=10^5,H<=500

题解

题意是一棵树

定义Aij = li xor lj

li，lj为i，j到它们公共祖先的距离

。。。。

70分n<=3000

这么水的数据，我 ~~分分钟就水过了~~ 竟然爆0了

lca写错了T T

100分

枚举每个点暴力。。。？？？

复杂度，不会分析TAT

orz n+e的题解http://trinklee.blog.163.com/blog/static/238158060201462091437906/

70分

#include<iostream>
#include<cstdio>
using namespace std;
struct edge{
	int to,next,v;
}e[50001];
int n,cnt,fa[100001][11],deep[100001],head[100001],s[1000001];
inline void ins(int u,int v){
	e[++cnt]=(edge){v,head[u]};head[u]=cnt;
	e[++cnt]=(edge){u,head[v]};head[v]=cnt;
}
inline void dfs(int x,int father){   
    for(int i=1;i<=9;i++){  
        if(deep[x]<(1<<i))break;  
        fa[x][i]=fa[fa[x][i-1]][i-1];  
    }  
    for(int i=head[x];i;i=e[i].next){  
        if(e[i].to==father)continue;  
        deep[e[i].to]=deep[x]+1;  
        fa[e[i].to][0]=x;  
        dfs(e[i].to,x);  
    }  
}  
inline int lca(int x,int y){  
    if(deep[x]<deep[y])swap(x,y);  
    int d=deep[x]-deep[y];  
    for(int i=0;i<=9;i++)  
        if((1<<i)&d)x=fa[x][i];  
    for(int i=9;i>=0;i--)  
        if(fa[x][i]!=fa[y][i])  
            x=fa[x][i],y=fa[y][i];  
    if(x==y)return x;  
    else return fa[x][0];  
}  
int main(){
	//freopen("che.in","r",stdin);
	//freopen("che.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;++i){
		int x;scanf("%d",&x);
		ins(x,i);
	}
	dfs(1,0);
	for(int i=1;i<n;++i)
		for(int j=i+1;j<=n;++j){
			int t=lca(i,j);
			++s[(deep[i]-deep[t])^(deep[j]-deep[t])];
		}
	for(int i=0;;++i){
		if(!s[i])break;
		printf("%d ",s[i]);
	}
	return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

struct edge{

int to,next,v;

}e[50001];

int n,cnt,fa[100001][11],deep[100001],head[100001],s[1000001];

inline void ins(int u,int v){

e[++cnt]=(edge){v,head[u]};head[u]=cnt;

e[++cnt]=(edge){u,head[v]};head[v]=cnt;

}

inline void dfs(int x,int father){

for(int i=1;i<=9;i++){

if(deep[x]<(1<<i))break;

fa[x][i]=fa[fa[x][i-1]][i-1];

}

for(int i=head[x];i;i=e[i].next){

if(e[i].to==father)continue;

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

dfs(e[i].to,x);

}

inline int lca(int x,int y){

if(deep[x]<deep[y])swap(x,y);

int d=deep[x]-deep[y];

for(int i=0;i<=9;i++)

if((1<<i)&d)x=fa[x][i];

for(int i=9;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

else return fa[x][0];

}

int main(){

//freopen("che.in","r",stdin);

//freopen("che.out","w",stdout);

scanf("%d",&n);

for(int i=2;i<=n;++i){

int x;scanf("%d",&x);

ins(x,i);

}

dfs(1,0);

for(int i=1;i<n;++i)

for(int j=i+1;j<=n;++j){

int t=lca(i,j);

++s[(deep[i]-deep[t])^(deep[j]-deep[t])];

}

for(int i=0;;++i){

if(!s[i])break;

printf("%d ",s[i]);

}

return 0;

}

100分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<iomanip>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,cnt;
int a[100005][505];
int ans[512],last[100005],deep[100005];
struct edge{
	int to,next;
}e[100005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void dfs(int x)
{
	a[x][0]=1;
	for(int i=last[x];i;i=e[i].next)
	{
		dfs(e[i].to);
		for(int j=0;j<=deep[x];j++)
			for(int k=0;k<=deep[e[i].to];k++)
				ans[j^(k+1)]+=a[x][j]*a[e[i].to][k];
		deep[x]=max(deep[x],deep[e[i].to]+1);
		for(int j=0;j<=deep[e[i].to];j++)
			a[x][j+1]+=a[e[i].to][j];
	}
}
int main()
{
	n=read();
	for(int i=2;i<=n;i++)
	{
		int x=read();insert(x,i);
	}
	dfs(1);
	int mx=512;
	for(;mx;mx--)
		if(ans[mx])break;
	for(int i=0;i<=mx;i++)
		printf("%d\n",ans[i]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<iomanip>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,cnt;

int a[100005][505];

int ans[512],last[100005],deep[100005];

struct edge{

int to,next;

}e[100005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void dfs(int x)

{

a[x][0]=1;

for(int i=last[x];i;i=e[i].next)

{

dfs(e[i].to);

for(int j=0;j<=deep[x];j++)

for(int k=0;k<=deep[e[i].to];k++)

ans[j^(k+1)]+=a[x][j]*a[e[i].to][k];

deep[x]=max(deep[x],deep[e[i].to]+1);

for(int j=0;j<=deep[e[i].to];j++)

a[x][j+1]+=a[e[i].to][j];

}

int main()

{

n=read();

for(int i=2;i<=n;i++)

{

int x=read();insert(x,i);

}

dfs(1);

int mx=512;

for(;mx;mx--)

if(ans[mx])break;

for(int i=0;i<=mx;i++)

printf("%d\n",ans[i]);

return 0;

}

« 「CF500D」New Year Santa Network 「BZOJ2286」[SDOI2011] 消耗战 »

hzwer.com _ Home | http://hzwer.com

「BZOJ3696」「FJ2014集训」化合物

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论