SNOI省选模拟赛 day1t1 travel

xiaoxiao2021-02-28  10

        题意: 有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; } } }

转载请注明原文地址: https://www.6miu.com/read-1750073.html

最新回复(0)