昨天没写，今天一起补上。
寒假集训（动态规划四）补 - 题单 - 洛谷 | 计算机科学教育新生态
寒假集训（动态规划五）补 - 题单 - 洛谷 | 计算机科学教育新生态
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);
}
}
|
睡觉。
