Algorithm Training

2024.11.14

CF1B: Spreadsheet

字符串小模拟，考验对进制的理解。

// 十进制 to 二十六进制
string res = "";
while (num_r > 0) {
    int temp = (num_r - 1) % 26; // 减 1 对齐
    res += 'A' + temp;
    num_r = (num_r - 1) / 26;
}
reverse(res.begin(), res.end());

2024.11.17

CF2035C: Alya and Permutation

题意

构造一个 $n$ 的排列，使得 $k$ 的值最大。
$k$ 的计算方法：

$$
k =
\begin{cases}
k \land p_i, & \text{if } i \text{ is odd}, \
k \lor p_i, & \text{if } i \text{ is even},
\end{cases}
\quad \text{for } i = 1, 2, \dots, n.
$$

思考

很好玩的位运算构造题。
容易想到 $k_{max}$ 可以根据 $n$ 的奇偶性分类讨论：

• $n$ 是奇数：最终结果等于「前 $n - 1$ 个数字的结果」 & 最后一个数字，即最终结果一定小于等于最后一个数字（且构造方案中最后数字一定是 $n$）。

• $n$ 是偶数：最终结果等于「前 $n - 1$ 个数字的结果」 | 最后一个数字。设 $n$ 的二进制表示中最高位的 1 在第 $x$ 位，最终结果一定可以写成 $2 ^ {x + 1} - 1$ 的形式，即在二进制下从 $n$ 的第 $x$ 位开始一直都是 1。

接下来考虑构造：

由于二进制的变化性质，我们可以想到尝试只通过最后 $m$ 个数字的运算来构造出答案。即 最终结果 = 前面结果 | 通过后面构造得到的答案。由于或运算的性质，对前面的数字的放置没有要求。

$n$ 是奇数：若想写成 前面结果 | 通过后面构造得到的答案 的形式，$m$ 只能是偶数（原因画图即可得到）。

• $m = 2$：构造 a_1 & a_2 来得到答案，不可能。
• $m = 4$：构造 a_1 & a_2 | a_3 & a_4 来得到答案。观察到 $n$ 与 $n - 1$ 在二进制下的关系（按位与后，至少能保住最高位的 1 到最低位（除 $2 ^ 0$ 那一位）的 1 之间的所有数字，剩余位的 0 不用管，还剩最低位的 1）。此时只需让 | 前半部分保住最低位的 1，| 后半部分让 $n$ 与 $n - 1$ 相与即可。故最后四个数字为：1, 3, n - 1, n。

$n$ 是偶数：若想写成 前面结果 | 通过后面构造得到的答案 的形式，$m$ 只能是奇数。偶数还涉及 $2$ 的整数次幂的问题：

• $n$ 是 $2$ 的整数次幂：1 与 3 保住最低位，$n - 2$ 与 $n - 1$ 保住中间位，最后或一个 $n$ 保住最高位。故最后五个数字为：1, 3, n - 2, n - 1, n。
• $n$ 不是 $2$ 的整数次幂：$n$ 与 $n - 1$ 保住最高位，最后或一个 $h - 1$ 保住剩余位（ $h$ 是最高位的 1 所代表的数字，即形式为 1000...0 ，减 1 后变成 0111...1）。故最后三个数字为：n, n - 1, h - 1。

2024.11.19

CF2037C: Superultra’s Favorite Permutation

题意

构造一个 $n$ 的排列，使得 $\forall i \in [1, n), a_i + a_{i + 1}$ 均是合数。

思考

关键点：

1. 除了 2 以外的所有质数都是奇数。
2. 奇数 + 奇数 = 偶数，且该题中不会出现和为 2 的情况。

做法：

奇数放左边，偶数放右边，考虑交界点（奇数 + 偶数的结果，是奇是偶不一定）。
可以现场找（从剩余的偶数中找），也可以就让 5 和 4 作为最后一个奇数和第一个偶数（后面这种方法 vp 时没想到，可以由小到大列举的。e.g. 1 + 2 = 3(not legal), 2 + 3 = 5(not legal), 3 + 4 = 7(not legal), 4 + 5 = 9(bingo!!)）。

$n \leq 4$ 的情况易证无解。

CF2037D: Sharky Surfing

题意

略。

思考

没想到 反悔贪心 这一步怎么实现。其实只需要维护一个新的优先队列，把这个阶段没选的加到里面即可。

后面自己写的时候，思路错误的地方是：最先预处理完每个禁区间前的补给点（加到每个的优先队列里了），之后按禁区的顺序处理，对每一个禁区间都先从当前禁区前的优先队列里选了。但之前没用的加到过反悔优先队列里的那些，若有比目前新碰到的更大的，其实是可以选的）。

最后还在多个队列的 clear 上踩了坑，其实在最后一个禁区间后面的补给点是没有任何用的，可以不用保存了。

ps：gpt-4o 优化代码的功能很好用，我的码风又被骂咯。