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{array}{lll}k\wedge p_i,& \text{if }i\text{ is odd},k\vee p_i,& \text{if }i\text{ is even},\end{array}\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$ 的排列，使得 $\mathrm{\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\le 4$ 的情况易证无解。

CF2037D: Sharky Surfing

题意

略。

思考

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

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

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

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

2025.4.2

SNCPC2024C: Seats

题意

找到长为 $n$ 的数组 $b_i$ ($1\le i\le n,1\le b_i\le 2n$) 满足 $\mathrm{\forall }i\ne j,b_i\ne b_j$ 且 $\mathrm{\forall }i,b_i=i$ 或 $b_i=a_i$。且最大化 $b_i=a_i$ 的个数。你只需要输出最多的个数即可。

思考

观察到每个点可以有多个入度，但最多只有一个出度。这简化了这个问题。
发现整张图可能会存在的原子组成部分：树、环、基环树（内向）。画图可以发现以下结论：
对于树，满足树上最长链最优；对于环，要么环上节点同时被满足，要么没有节点会被满足。
对于基环树，不难发现只能满足环（满足环的话树们就没法满足，但不满足环的话环上的点也会保持不动，也会使得树们没法满足）。

具体做法：可以采用拓扑排序的方式，先统计所有树的最长链的答案。设 $maxx[x]$ 表示指向 $x$ 的节点所携带的链的长度的最大值，当拓扑删到树上的最后一个点时，再进行答案的统计（这样可以保证在基环树上的节点不被统计到答案，因为基环树上只有环上节点能被满足）。最后再通过染色法把基环树上的环以及普通的环直接统计答案标记即可。