CF 做题笔记

• CF1926G Vlad and Trouble at MIT \(\texttt{*1900}\)。

TAG: \(\texttt{树形 dp}\)

\(dp_{i,S,P}\) 为 \(i\) 的子树内是否存在 S 和 P 的状态。

转移方程为：

当 \(s_i\) 为 C 时

dp[x][0][0] += min({ dp[v][1][0] + 1, dp[v][0][1] + 1, dp[v][0][0] });
dp[x][1][0] += min({ dp[v][0][0], dp[v][1][0], dp[v][0][1] + 1 });
dp[x][0][1] += min({ dp[v][0][0], dp[v][1][0] + 1, dp[v][0][1] });

当 \(s_i\) 为 S 时

dp[x][1][0] += min({ dp[v][1][0], dp[v][0][1] + 1, dp[v][0][0] });

当 \(s_i\) 为 P 时

dp[x][0][1] += min({ dp[v][1][0] + 1, dp[v][0][1], dp[v][0][0] });

代码

• CF850B Arpa and a list of numbers \(\texttt{*2100}\)。

TAG: \(\texttt{暴力，贪心，乱搞}\)

枚举 \(\operatorname{gcd} = g\)，对于每一个 \(g\)，在每一个大小为 \(g\) 的区间，前一半直接删除，后一半 \(+1\)，答案即为所有 \(g\) 的最小值。

代码

• 1353F Decreasing Heights

TAG: \(\texttt{dp, 暴力}\)

枚举 \(a_{1, 1}\) 的值，然后算出 \((1, 1)\) 到 \((i, j)\) 的步数即 \(a_{i,j} = a_{1, 1} + i + j - 2\)，并暴力 \(dp\)。

代码