2023提高备考
Nuyoah_awa
·
·
生活·游记
2023 CSP-S/NOIP 省一计划
2023年全力冲省一!!!
2022-12-3
SPFA
2022-12-9 到 2023-2-4 寒假，刷题
题单
共 AC104 题。
2023-3-4
在跟随提高组大课练完春测后周末恢复正常模拟赛。
T1：P8402
思路：暴力。
T2：P7616
题解
T3：P1236
枚举。
T4：P1651
DP：令 f_{i,j} 表示前 i 个积木，其中第一堆积木减去第二堆积木的差值为 j 时左边积木的高度。
转移：
①物品 i 不选，则 f[i][j] = max(f[i][j], f[i-1][j]);
②物品 i 放左边，则 f[i][j] = max(f[i][j], f[i-1][j-a[i]]+a[i]);
③物品 i 放右边，则 f[i][j] = max(f[i][j], f[i-1][j+a[i]]);
T5：P1517
小数高精。
-
按照整数计算，加上小数点在第几位。
-
整数一个数组，小数一个数组。
树形DP
2023-7-14
简单来讲树形DP是定义一个状态表示以该点为根的子树的“价值”然后通过其他节点递推得来。
P2899
给一个树，每选一个点可以覆盖这个点及它周围的点，问最少要几个点可以全部覆盖。
思路
定义 f_i 表示以 i 为根的子树全部覆盖最少需要多少个点，从下往上递推需要知道下面的点是否被覆盖。
于是定义 f_{i, 1/0} 表示以 i 为根的子树全部覆盖且 i 是否被选，最少需要多少个点。
但是我们考虑一种情况：1 \to 0 \to 0 \to 1，这种情况也可以被覆盖，但是并没有考虑到，也就是说子树根节点 i 有可能是被它的父亲节点覆盖的。
于是我们定义 f_{i, 0/1/2}。f_{i, 0} 表示全部被覆盖，且 i 被父亲覆盖；f_{i, 1} 表示 i 被自己覆盖（选 i）；f_{i, 2} 表示 i 被子节点覆盖。
转移方程：
\case{begin}\case{end}