首页 » C++ » SNOI省选模拟赛 day1t1 travel

SNOI省选模拟赛 day1t1 travel

原文 http://blog.csdn.net/Rising_shit/article/details/79065445

2018-01-16 02:00:57阅读(595)

        题意: 有n(<=3000)个点的一棵树,q组询问(<=100000),求从点x出发的mod k(<=100)意义下的最长路。

        题解:

        纪念一下难得自己做出来的dp题,顺便纪念第一个小时打了100分,后面4个小时打了6.6分的惨案。

        首先我们可以想到对每组询问跑一遍dfs,直接求出mod k 意义下的最长路,或者n方*k的复杂度处理出每个点modk意义下的最长路,期望得分30分左右。

        接着可以观察上下两个点的关系,首先只考虑从根向下点的关系,假如我儿子能到达一个mod k =z的点,那么设该边权为y,它就能到达一个mod k = (z+y)%k的点了,所以如果我们用dp[i][j][k]表示考虑到第i个点mod j=k的方案数(在我的方法下,为什么不能表示存不存在,后续会说明),那么就可以首先将dp[i][j][0]预处理为1,表示每个点自己不走的方案数为1,向下枚举每个儿子,加上其的方案数即可,dp1[i][j][(k+val[i])%j]+=dp1[son[i]][j][k];

        处理完向下可以考虑向上,同样该点父亲能走到的点,加上该点到父亲的这条边后也是有如上文的关系的,由于是从根自上往下做,所以向上的路也在前一步处理好了,在这一步需要注意的是,因为该点也在其父亲的子树中,所以该点的父亲的一部分方案是由该点转移而来的,我们需要在处理前将由该点转移而来的方案减掉,否则会出现一些该点的子树自己转移到自己的方案,导致出现一些不可能的方案。

       下附AC代码。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 3005
using namespace std;
int n,q,tot;
int head[maxn<<1],to[maxn<<1],val[maxn<<1],nex[maxn<<1];
int temp[105][105]; 
int dp1[maxn][105][105];//考虑到第i个点mod j=k的情况的个数 
void add(int x,int y,int z)
{
	to[++tot]=y;val[tot]=z;nex[tot]=head[x];head[x]=tot;
}
void dfs1(int now,int fa)
{
	for(int i=2;i<=100;i++)
	dp1[now][i][0]=1;
	
	for(int i=head[now];i;i=nex[i])
	{
		if(to[i]!=fa)
		{
			dfs1(to[i],now);
			for(int j=2;j<=100;j++)
			for(int k=0;k<j;k++)
			dp1[now][j][(k+val[i])%j]+=dp1[to[i]][j][k];
		}
	}
}
void dfs2(int now,int fa,int v)
{
	if(fa!=-1)
	{
		for(int j=2;j<=100;j++)
		{
			for(int k=0;k<j;k++)
			{
				temp[j][k]=dp1[now][j][k];
				dp1[fa][j][(k+v)%j]-=dp1[now][j][k];
			}
		}
		
		for(int j=2;j<=100;j++)
			for(int k=0;k<j;k++)
				dp1[now][j][(k+v)%j]+=dp1[fa][j][k];
		
		for(int j=2;j<=100;j++)
			for(int k=0;k<j;k++)
				dp1[fa][j][(k+v)%j]+=temp[j][k];
	}
	for(int i=head[now];i;i=nex[i])
	{
		if(to[i]!=fa)
		{
			dfs2(to[i],now,val[i]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	dfs1(1,-1); 
	dfs2(1,-1,0);
	scanf("%d",&q);
	while(q--)
	{
		int x,k;
		scanf("%d%d",&x,&k);
		if(k==1) {printf("%d\n",0);continue;}
		for(int i=k-1;i>=0;i--)
		if(dp1[x][k][i])
		{
			printf("%d\n",i);
			break;
		}
	}
}


最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹