上讲习题

AcWing 1075

本题每个数都可以变成下一个点，很像某个点向下一个点连边。一个数只有一个因子和，但是有可能多个数的因子和等于某个数，就像是一个点只有一个爹，但是会有多个儿子，所以这样建图是一棵树，每个点的爹就是自己的因子和。任意一个序列都对应树的一条路径，要求最长的序列就是求树的直径。求树的直径参考上讲的AcWing 1072。

#include<bits/stdc++.h> using namespace std; const int NN=50004; int sum[NN],ans; vector<int>g[NN]; int dfs(int u) { int maxx=0,maxy=0; for(int i=0;i<g[u].size();i++) { int res=dfs(g[u][i])+1; if(res>maxx) { maxy=maxx; maxx=res; } else if(res>maxy) maxy=res; } ans=max(ans,maxx+maxy); return maxx; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=2;j<=n/i;j++) sum[i*j]+=i; for(int i=1;i<=n;i++) if(sum[i]<i) g[sum[i]].push_back(i); dfs(1); printf("%d",ans); return 0; }

AcWing 1074

本题要求剪掉一些枝，可以分别给左右儿子分配一些保留的枝并加上自己的枝上的苹果。先预处理出所有的点的左右儿子，然后把连向父亲的边的苹果放在自己身上。注意，因为根节点没有父亲，然而留下的点会算它一个，所以留下的边数要加一。本题的状态有重复，需要记忆化。

#include<bits/stdc++.h> using namespace std; const int NN=104; int a[NN],g[NN][NN],l[NN],r[NN],f[NN][NN],n,m; void dfs(int u) { for(int i=1;i<=n;i++) if(g[u][i]>=0) { l[u]=i; a[i]=g[u][i]; g[u][i]=g[i][u]=-1; dfs(i); break; } for(int i=1;i<=n;i++) if(g[u][i]>=0) { r[u]=i; a[i]=g[u][i]; g[u][i]=g[i][u]=-1; dfs(i); break; } } int dp(int u,int x) { int &d=f[u][x]; if(d>=0) return d; if(!x) return d=0; if(!l[u]&&!r[u]) return d=a[u]; for(int k=0;k<x;k++) d=max(d,dp(l[u],k)+dp(r[u],x-k-1)+a[u]); return d; } int main() { scanf("%d%d",&n,&m); m++; memset(g,0xaf,sizeof(g)); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v]=g[v][u]=w; } dfs(1); memset(f,-1,sizeof(f)); printf("%d",dp(1,m)); return 0; }

AcWing 1077

本题和上讲的AcWing 323非常像。但是我们研究一下发现，假设某个点不用，则所有儿子至少用一个。但是这种分析会少考虑一个情况：有可能父亲用了，那么儿子也可以一个都不用。于是我们就要分成三种状态：$f_{u,(0,1,2)}$，分别表示父亲一定用了且自己一定没用、一定有一个儿子用了且自己一定没用、自己一定用了的情况下覆盖完本子树的最小代价。首先，第一种情况，那么自己的每个儿子可以选择用或者不用，而且因为自己一定不用，所以子节点不能选择父亲一定用了的情况，$f_{u,0}+=\min (f_{v,1},f_{v,2})$。第二种情况，则所有子节点要至少有一种，同理，子节点也不能选择父亲一定用的情况，$f_{u,1}+=\min (f_{v,1},f_{v,2})$。但是这种情况如果更小的全是$f_{v,1}$，可是我们必须有一个子节点来管当前节点，所以要把一个换成$f_{v,2}$，找一个差值最小的，即$minn=\min (f_{v,2}-f_{v,1},0)$。如果每个都是用$f_{v,2}$更新的，那么$f_{u,1}$就要加上$minn$。考虑简化这个式子，发现如果用的$f_{v,2}$更新，那么$f_{v,2}=\min (f_{v,1},f_{v,2})$，带入刚才求$minn$的式子刚好等于$0$。遇到$0$相当于不用加了，和想要的效果刚好相对应，则不用判断是否用了$f_{v,2}$直接更新即可。第三种情况，则孩子可以用或者不用，则$f_{u,2}+=\min (f_{v,(0,1,2)})$。注意别忘了加上使用自己的代价。有一个问题：如何找根？方法很简单：找入度为零的即可。最后输出答案时根节点没有父亲，所以$ans=\min (f_{root,1},f_{root,2})$。

#include<bits/stdc++.h> using namespace std; const int NN=2504; struct node { int num,son[NN],money; }a[NN]; int f[NN][3]; bool isson[NN]; int dp(int x,int fa) { int minn=2147483647; f[x][2]=a[x].money; for(int i=1;i<=a[x].num;i++) { int y=a[x].son[i]; dp(y,x); f[x][0]+=min(f[y][1],f[y][2]); f[x][1]+=min(f[y][1],f[y][2]); f[x][2]+=min(f[y][2],min(f[y][1],f[y][0])); minn=min(minn,f[y][2]-min(f[y][1],f[y][2])); } f[x][1]+=minn; } int main() { int n,root=1; scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); scanf("%d%d",&a[x].money,&a[x].num); for(int j=1;j<=a[x].num;j++) { scanf("%d",&a[x].son[j]); isson[a[x].son[j]]=true; } } while(isson[root]) root++; dp(root,0); printf("%d",min(f[root][1],f[root][2])); return 0; }

概念

数位$dp$，就是一个构造数的$dp$。这类问题一般求满足要求的数的个数。

方法

一般来说都是研究上边界这个数的每一位，从最高位开始。如果这一位填的是上边界，则要继续判断；如果填的不是上边界，则后面的可以随便填，直接计算并退出即可。因为要算随便填的方案数，所以可以初始化某一位开始，随便填且满足题目要求的方案数。

例题

AcWing 1081

不难发现，如果$b$进制下有一位填的不是$1$或$0$，那么就需要重复的数相加，一定不满足要求。则本题就是求把一个数拆成$b$进制，每一位填$1$或$0$，刚好填$k$个$1$且数不超过$y$的方案数。如果上界大于$0$，那么这一位填$0$后面的就可以随便填且要选$k$位填$1$，$ans+=C(size,k)$。如果上界还大于$1$，那么这一位填$1$后面也可以随便填，但是因为这一位已经填$1$了，所以后面的只能随便填$k-1$个，$ans+=C(size,k-1)$，而且这一位不管填什么后面都随便填，所以已经把所有方案计算了，直接退出。如果上界这一位等于$1$，那这一位填了$1$其他的就不能乱填，可是需要填的就少了，记$last$为前面填$1$的个数，则$last++$。前面随机分配时计算$C$，因为在之前有一些已经固定了，所以后面需要随机分配的$1$也要减去$last$个。若上界等于$0$，那填了$0$后也不能乱填，不能对答案有贡献。最后全部的都算完了后若已经固定了$k$的每一位，即$last=k$，则答案$+1$。本题中，初始化从某一位开始随便填的方案数，就是初始化$C$的值。因为本题要求的是区间内合法的数，直接差分$dp(r)-dp(l-1)$。

#include<bits/stdc++.h> using namespace std; const int NN=33; int C[NN][NN],k,b; int dp(int n) { vector<int>num; while(n) { num.push_back(n%b); n/=b; } int res=0,last=0; for(int i=num.size()-1;i>=0;i--) { int x=num[i]; if(x) { res+=C[i][k-last]; if(x>1) { res+=C[i][k-last-1]; break; } else { last++; if(last>k) break; } } if(!i&&last==k) res++; } return res; } int main() { for(int i=0;i<NN;i++) for(int j=0;j<=i;j++) if(!j) C[i][j]=1; else C[i][j]=C[i-1][j]+C[i-1][j-1]; int l,r; scanf("%d%d%d%d",&l,&r,&k,&b); printf("%d",dp(r)-dp(l-1)); return 0; }

AcWing 1083

这个题每一位只要不是当前位的上界就可以随便填。但是题目要求两个数的差必须大于$2$，则看一看上一位的边界与这一位填的数的差是否大于$2$即可。如果在枚举当前位填边界的情况时，发现两位的边界的差小于$2$，则这样填这个序列已经不满足要求了，直接退出即可。最后考虑后面随便填的方案数，设$f_{i,j}$为有$i$位且最高位是$j$的数的个数。两位的差大于二即可转移，则$f_{i,j}+=f_{i-1,k},|j-k|\ge 2$。注意，本题中如果有多个前导$0$是会计算为不可取的方案，因为有两位都是$0$ ，差小于$2$。但是如果有多个前导$0$，在本题中应当是可取的，所以要特殊判断。有多个前导$0$相当于前几位都固定为$0$，后面的随便填，因为最高位一定大于$0$。最后，如果枚举完了，那么说明都填最高位是可以的，答案加一。注意，$0$也是一个可行的数。

#include<bits/stdc++.h> using namespace std; const int NN=11; int f[NN][NN]; int dp(int n) { if(!n) return 1; vector<int>num; while(n) { num.push_back(n%10); n/=10; } int res=0,last=-2; for(int i=num.size()-1;i>=0;i--) { int x=num[i]; for(int j=i==num.size()-1;j<x;j++) if(abs(j-last)>=2) res+=f[i+1][j]; if(abs(x-last)<2) break; last=x; if(!i) res++; } for(int i=1;i<num.size();i++) for(int j=1;j<=9;j++) res+=f[i][j]; return res+1; } int main() { for(int i=1;i<NN;i++) for(int j=0;j<=9;j++) if(i==1) f[i][j]=1; else for(int k=0;k<=9;k++) if(abs(j-k)>=2) f[i][j]+=f[i-1][k]; int l,r; scanf("%d%d",&l,&r); printf("%d",dp(r)-dp(l-1)); return 0; }

AcWing 1084

本题是同样的思路，如果等于边界就继续枚举，反之就加上后面随便填的总方案数。计算随便填的方案数，发现要求前面填边界的数的总和加上后面填的数的总和模$n$为$0$才行，所以可以把$last$设为前面填的边界的总和，想要加上一个数之后摸$n$为$0$令新加的数为$-last+kn$即可。设$f_{i,j,k}$表示有$i$位，且最高位为$j$，模$n$（正整数）为$k$的数的个数，函数$mod$能得到某个数的正整数模数，则每次枚举新填的数$j$使后面可以随便填，$res+=f_{i,j,mod(-last)}$。思考状态转移，枚举数的第二位$x$，则$f_{i,j,k}+=f_{i-1,x,mod(k-x)}$，边界条件$f_{1,j,mod(j)}=1$。请注意，如果都填边界满足要求答案就要加$1$。

#include<bits/stdc++.h> using namespace std; const int NN=11; int f[NN][NN][104],P; int mod(int x) { return (x%P+P)%P; } int dp(int n) { if(!n) return 1; vector<int>num; while(n) { num.push_back(n%10); n/=10; } int res=0,last=0; for(int i=num.size()-1;i>=0;i--) { int x=num[i]; for(int j=0;j<x;j++) res+=f[i+1][j][mod(-last)]; last+=x; if(!i&&!(last%P)) res++; } return res; } int main() { int l,r; while(scanf("%d%d%d",&l,&r,&P)!=EOF) { memset(f,0,sizeof(f)); for(int i=0;i<=9;i++) f[1][i][mod(i)]=1; for(int i=2;i<NN;i++) for(int j=0;j<=9;j++) for(int k=0;k<P;k++) for(int x=0;x<=9;x++) f[i][j][k]+=f[i-1][x][mod(k-j)]; printf("%d\n",dp(r)-dp(l-1)); } return 0; }

习题

AcWing 1082

AcWing 1085

AcWing 1086

解析和代码在下一篇博客——单调队列优化$dp$给出