昨天没写,今天一起补上。
寒假集训(动态规划四)补 - 题单 - 洛谷 | 计算机科学教育新生态
寒假集训(动态规划五)补 - 题单 - 洛谷 | 计算机科学教育新生态
D4T1 #(subset sum = K) with Add and Erase/背包の撤销
题面
原题面 ABC321F
题意
$Q$ 次询问,每次加入或取出一个物品,求此时维护出价值 $K$ 的方案数。
思路
用 $dp[j]$ 表示前 $i$ 次操作后凑出 $j$ 的方案数,有 $dp[j]`=dp[j]+dp[j-x]$ ,可推出柿子。
代码
Submission #62645136
D4T2 Infected Tree/简单染色问题
题面
原题面 CF1689C
题意
给一棵树,节点有点权,一个节点的价值为包含该节点的连通块的权值之和的最大值。求每个节点的价值?
思路
定义
$siz[u]$ 表示以 $1$ 为根节点时,子树 $u$ 的大小
$f[u]$ 表示表示以 $1$ 为根节点时,子树 $u$ 中所有节点 $siz$ 之和
$g[u]$ 表示以 $u$ 节点为根是,所有节点的子树的 $siz$ 之和
换根 DP 老套路:$g[1]=f[1]$
状态转移
$siz[u]=1+\sum_{v \in son(u)}siz[v]$
$f[u]=siz[u]+\sum_{v \in son(u)}f[u]$
$g[v]=g[u]+n-siz[v] \times 2$
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| int n; vector <int> G[N]; int siz[N],f[N],g[N]; void dfs1(int u,int fa){ for(auto v:G[u]){ if(v==fa) continue; dfs1(v,u); siz[u]+=siz[v]; } siz[u]+=1; } void dfs2(int u,int fa){ f[u]=siz[u]; for(auto v:G[u]){ if(v==fa) continue; dfs2(v,u); f[u]+=f[v]; } } void dfs3(int u,int fa){ for(auto v:G[u]){ if(v==fa) continue; g[v]=g[u]+n-siz[v]*2; dfs3(v,u); } } signed main(){ n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); G[u].push_back(v); G[v].push_back(u); } dfs1(1,1); dfs2(1,1); g[1]=f[1]; dfs3(1,1); int res=-1; for(int i=1;i<=n;i++) res=max(res,g[i]); cout<<res<<endl; return 0; }
|
D4T3 Select Edges/切边
题面
原题面 ABC259F
题意
给一棵有权树,节点 $i$ 最多保留 $d_i$ 条邻边,求保留边权之和最大值。
思路
$dp[u][0/1]$ 代表 $u$ 子树中的边确定后的方案中 不能/还能 与父节点链接的最优解。
$dp[v][0]$ |
$a_1$ |
$a_2$ |
$…$ |
$a_n$ |
$dp[v][1] + w$ |
$b_1$ |
$b_2$ |
$…$ |
$b_n$ |
$dp[u][0]$ → 在上表中选 $d_u$ 个 $dp[v][1] + w$ 。
$dp[u][1]$ → 在上表中选 $d_u-1$ 个 $dp[v][1] + w$ 。
选择方法:假设全选 $dp[v][0]$ ,对两个选项作差,选或不选,pq 维护。实际上用了 sort。
代码
Submission #62594792
D4T4 Pac-Takahashi/限时寻糖
题面
原题面 ABC301E
题意
给一张图,图中有起点 $S$ ,终点 $G$ ,糖果 $o$(不超过 $18$ 个)。给定时间 $T$ ,求最多能捡多少个糖果。
思路
先 BFS 确定每个点之间距离,然后状压 DP。
代码
Submission #62597421 心态炸了,BFS 用 AI 修出来的,感谢 Logic。
D5T1 Round Subset/最多の零度
题面
原题面 CF837D
题意
$n$ 个数,取 $k$ 个数相乘,求末尾 $0$ 个数最大值。
思路
将每个数 $a_i$ 分解因数,分别计算由几个 $2$ 和几个 $5$ 相乘得到,作为权值 DP,答案取两数中的最小值。
发现自己卡过了,好离谱的数据。
代码
因为是卡过的所以不想放,CF 上过不了(
D5T2 Infected Tree/保护计划
题面
原题面 CF1689C
题意
给一棵二叉树,根节点被感染,每秒扩散一步。每秒之前可以选择一个未感染的点切除,最多保护多少节点?
思路
典型的树形 DP。注意到是二叉树,差点眼瞎。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| int n; vector <int> G[N]; int dep[N]; int siz[N]; int dp[N]; void dfs1(int u,int fa){ dep[u]=dep[fa]+1; siz[u]=1; for(auto v:G[u]){ if(v==fa) continue; dfs1(v,u); siz[u]+=siz[v]; } } bool cmp(const int &x,const int &y){return x>y;} void dfs2(int u,int fa){ int s=0; for(auto v:G[u]){ if(v==fa) continue; dfs2(v,u); s+=dp[v]; } for(auto v:G[u]){ if(v==fa) continue; dp[u]=max(dp[u],s-dp[v]+siz[v]-1); } } signed main(){ n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); G[u].push_back(v); G[v].push_back(u); } dep[0]=0; dfs1(1,0); dfs2(1,0); cout<<dp[1]<<endl; return 0; }
|
D5T3 编辑距离
能不能原谅我我真的没修出来qwq Luogu $60/100$
D5T4 Tree Painting/染色方案
题面
原题面 CF1187E
题意
给一棵树,需要给边染色,要求所有节点到根节点路径上最多只有一条染色边。求所有节点作为根节点时的染色染色方案。
思路
换根 DP。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| void dfs1(int u,int fa) { int tmp=1; for(auto v:G[u]){ if(v==fa) continue; dfs1(v,u); tmp=(tmp*(f[v]+1))%P; } f[u]=tmp; } void dfs2(int u, int fa) { for(auto v:G[u]){ if(v==fa) continue; h[v]=(h[u]+1)%P; } int tmp=1; for(auto v:G[u]){ if(v==fa) continue; h[v]=(h[v]*tmp)%P; tmp=(tmp*(f[v]+1))%P; } reverse(G[u].begin(),G[u].end()); tmp=1; for(auto v:G[u]){ if(v==fa) continue; h[v]=(h[v]*tmp)%P; tmp=(tmp*(f[v]+1))%P; } for(auto v:G[u]){ if(v==fa) continue; g[v]=((h[v]+1)*f[v])%P; dfs2(v,u); } }
|
睡觉。