2024 年 11 月刷题日志

LG1005 矩阵取数游戏

LG1005 矩阵取数游戏

2020-11-05 | 题目链接 | </> 代码

在 $n\times m$ 的非负矩阵内玩取数游戏，每行独立。你只能取走行首或者行尾，取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 是第 $i$ 次取数。

很明显的区间 DP。

i128 p1 = dp[l][r - 1] * 2 + v[r - 1];
i128 p2 = dp[l + 1][r] * 2 + v[l];
dp[l][r] = std::max(p1, p2);

LG1006 传纸条

LG1006 传纸条

2020-11-05 | 题目链接 | </> 代码

跟 LG1004 几乎一模一样。

略。

CF2029A Set

CF2029A Set

2024-11-09 | 题目链接 | </> 代码

初始时集合 $S=[l,r]$，假如 $kx\in S$ 那么就可以把 $x$ 从 $S$ 中移除。问最多移除多少个。

显然从小往大删，最大能删的数是 $\lfloor \frac{r}{k}\rfloor$。因此答案是 $max(\lfloor r/k\rfloor -l+1,0)$。

CF2029B Replacement

CF2029B Replacement

2024-11-09 | 题目链接 | </> 代码

给定一个长为 $n$ 的 01 串 $s$ 和长为 $n-1$ 的 01 串 $r$。我们对 $i\in [1,n-1]$ 做操作：选择一个 $k$ 使得 $s_k\ne s_{k+1}$，把这两位替换成 $r_i$。问能否操作 $n-1$ 次。

注意到 $s_k\ne s_{k+1}$，意味着我们的操作实际上等价为删除 $1-r_i$。那么当我们提前把某个种类删除到 $0$ 个时失败。

CF2029C New Rating

CF2029C New Rating

2024-11-09 | 题目链接 | </> 代码

初始时积分 $x=0$，当表现水平与当前积分不同时，积分会向该方向加减 1。现在给出长 $n$ 的序列 $\{a_i\}$ 作为表现分序列，可以选择区间 $[l,r]$ 进行删除，问结束时最高积分。

考虑 DP，设 $f(i,j)$ 为当前第 $i$ 个时的最高分，$j=0$ 时为正常参与，$j=1$ 为跳过中，$j=2$ 为跳过完毕。接下来转移就是自然的了。

dp[0][2] = dp[0][1] = -1;
for (int i = 1; i <= n; ++i) {
  auto &now = dp[i], &p = dp[i - 1];
  dp[i][0] = f(dp[i - 1][0], a[i]);
  dp[i][1] = std::max(dp[i - 1][0], dp[i - 1][1]);
  dp[i][2] = std::max(f(dp[i - 1][2], a[i]), f(dp[i - 1][1], a[i]));
}

CF2029D Cool Graph

CF2029D Cool Graph

2024-11-09 | 题目链接 | </> 代码

给定一个点数为 $n$ 边数为 $m$ 的图，你可以做 $2max(n,m)$ 次操作：选择 $a,b,c$ 三个点，若两点之间无边则连上、有边则断开。问能否将图变成 Cool 的，即是树或者边数为 0。

注意到对于任何一条边 $(b,c)$，我们总是可以选择 $a=1$ 转化为连到根的边。此时我们得到一颗残缺的树。再注意到对于边 $a\to b$，我们可以操作使得 $a\to c\to b$ 把该点串进去。

CF2029E Common Generator

CF2029E Common Generator

2024-11-09 | 题目链接 | </> 代码

我们定义变换：对于一个数 $x$，可以加上 $x$ 的一个因数 $d$。给定一个序列 $\{a_i\}$，求是否存在 $x(x⩾2)$ 使其能够变出其它所有的数。

首先我们注意到 $2$ 是特殊的，假如 $a_i$ 可以分解为 $pq$，那么我们可以由 $2\to 2p\to pq$。当 $a_i$ 是质数时，我们必须选择 $x=a_i$。

因此初始值 $x$ 是可以确定的。假如质数超过 1 个，那么无解；假如都是合数，我们总是可以选择 $x=2$。因此问题转化为选择固定质数 $x$ 时的可达性。

假如 $x<p$ 时，我们可以通过 $x\to 2x\to 2p\to pq$ 达成；当 $x⩾p$ 时，我考虑 $2x\to 2kp\to pq$，需要枚举所有的质因子 $p$ 并判断 $2kp⩽pq$。

赛后补：最后的判断实际上可以更简单，傥若 x 是奇数 $2x\to p(q-1)\to pq$。