2020年 CSP-S1 解析
djwj233
2021-08-26 20:56:31
这张卷子场上考了 $88$ 分，苟着过线，那么今年显然过不了了/cy
在洛谷博客上的排版可能会挂，凑合一下（
### 一、单项选择题
这年选择题十分简单。因为里面大多数都是思博题，因此只挑了几道出来。
> **10.** —个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人。
>
> 问这个班的学生人数 $n$ 在以下哪个区间？已知 $n<60$。( ）
>
> A. $30<n<40$ B. $40<n<50$ C. $50<n<60$ D. $20<n<30$
韩信点兵问题，本质上就是求解一个线性同余方程组。（当然直接枚举可能更快）
由于 $3,5,7$ 互质，因此可以用 CRT 解。
首先 $3\times 5\times 7=105$，然后有：
$$
5\times 7=35,\quad 35^{-1}\equiv2\!\!\pmod3
$$
$$
3\times 7=21,\quad 21^{-1}\equiv1\!\!\pmod5
$$
$$
3\times 5=15,\quad 15^{-1}\equiv1\!\!\pmod7
$$
因此 $n$ 的通解为：
$$
2\times 35\times2 + 3\times21\times 1+4\times 15\times 1+105k\quad (k\in \mathbb Z)
$$
因此 $n$ 的最小正整数解为 $53$。选 **C**。
> **13.** 从一个 $4\times4$ 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。
>
> A. $60$ B. $72$ C. $86$ D. $64$
排异法，求出所有方案数再减去在同一行或同一列的方案数。
$$
\binom{16}{2}-8\times\binom{4}{2}=72
$$
### 二、阅读程序
这难度就离谱。
> **16.**
>
> ```c++
> #include <iostream>
> using namespace std;
>
> int n;
> int d[1000];
>
> int main() {
> cin >> n;
> for (int i = 0; i < n; ++i)
> cin >> d[i];
> int ans = -1;
> for (int i = 0; i < n; ++i)
> for (int j = 0; j < n; ++j)
> if (d[i] < d[j])
> ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
> cout << ans;
> return 0;
> }
> ```
>
> 假设输入的 $n$ 和 $\texttt{d[i]}$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：
>
> - 判断题
> - **1）** $n$ 必须小于 $1000$，否则程序**可能**会发生运行错误。（ ）
> - **2）** 输出一定大于等于 $0$。（ ）
> - **3）** 若将第 13 行的 `j=0` 改为 `j=i+1` 程序输出**可能**会改变。 （ ）
> - **4）** 将第 14 行的 `d[i]<d[j]` 改为 `d[i]!=d[j]`，程序输出**不会**改变。（ ）
>
> - 单选题
>
> - **5）** 若输入 $n$ 为 $100$，且输出为 $127$，则输入的 $\texttt{d[i]}$ 中不可能有（ ）。
>
> - A. $127$ B. $126$ C. $128$ D. $125$
>
> - **6）** 若输出的数大于 $0$，则下面说法正确的是（ ）。
>
> - A. 若输出为偶数，则输入的 $\texttt{d[i]}$ 中**最多**有两个偶数
>
> - B. 若输出为奇数，则输入的 $\texttt{d[i]}$ 中**至少**有两个奇数
>
> - C. 若输出为偶数，则输入的 $\texttt{d[i]}$ 中**至少**有两个偶数
>
> - D. 若输出为奇数，则输入的 $\texttt{d[i]}$ 中**最多**有两个奇数
首先，对于任意正整数 $a,b$，易证：
$$
a\operatorname{or} b=a+b-(a\operatorname{and} b)
$$
那么我们发现程序是要读入一个数列，并输出**数列中任意两项按位或的最大值**。
- **1）**阅读程序可知，$n$ 可以等于 $1000$，选 **F**。（去年这里挂了）
- **2）**注意到 `if(d[i]<d[j])` 这个条件，因此构造所有 $\texttt{d[i]}$ 都相等就能使答案为 $-1$，选 **F**。
- **3）**同上一题，可知双向都枚举才能保证答案正确，选 **T**。
- **4）**这样每个原来的答案会进行两次更新，最终还是等价的，选 **T**。
- **5）**$127<128$，因此不可能有 $128$，否则由于数列中不只有 $128$，按位或的值肯定不会小于 $128$。选 **C**。
- **6）**因为只有两个偶数的按位或和才是偶数，逐一排除可得答案为 **C**。
评价：坑点极多，总体难度不大。
> **17.**
>
> ```c++
> #include <iostream>
> #include <cstdlib>
> using namespace std;
>
> int n;
> int d[10000];
>
> int find(int L, int R, int k) {
> int x = rand() % (R - L + 1) + L;
> swap(d[L], d[x]);
> int a = L + 1, b = R;
> while (a < b) {
> while (a < b && d[a] < d[L])
> ++a;
> while (a < b && d[b] >= d[L])
> --b;
> swap(d[a], d[b]);
> }
> if (d[a] < d[L])
> ++a;
> if (a - L == k)
> return d[L];
> if (a - L < k)
> return find(a, R, k - (a - L));
> return find(L + 1, a - 1, k);
> }
>
> int main() {
> int k;
> cin >> n;
> cin >> k;
> for (int i = 0; i < n; ++i)
> cin >> d[i];
> cout << find(0, n - 1, k);
> return 0;
> }
> ```
>
> 假设输入的 $n,k$ 和 $\texttt{d[i]}$ 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$。
>
> 并假设 $\texttt{rand}$ 函数产生的是均匀的随机数，完成下面的判断题和单选题：
>
> - 判断题
>
> - **1）**第 9 行的 $x$ 的数值范围是 $[L+1,R]$ 。（ ）
> - **2）**将第 19 行的 $\texttt{d[a]}$ 改为 $\texttt{d[b]}$，程序不会发生运行错误。（ ）
>
> - 单选题
>
> - **3）**当输入的 $\texttt{d[i]}$ 是严格**单调递增**序列时，第 17 行的 $\texttt{swap}$ 平均执行次数是( )。
> - A. $\mathcal O(n \log n)$ B. $\mathcal O(n)$ C. $\mathcal O(\log n)$ D. $\mathcal O(n^2)$
> - **4）**当输入的 $\texttt{d[i]}$ 是严格**单调递减**序列时，第 17 行的 $\texttt{swap}$ 平均执行次数是( )。
> - A. $\mathcal O(n^2)$ B. $\mathcal O(n)$ C. $\mathcal O(n\log n)$ D. $\mathcal O(\log n)$
> - **5）**若输入的 $\texttt{d[i]}=i$，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。
> - A. $\mathcal O(n)$， $\mathcal O(n^2)$ B. $\mathcal O(n)$， $\mathcal O(n \log n)$
> - C. $\mathcal O(n \log n)$， $\mathcal O(n^2)$ D. $\mathcal O(n \log n)$， $\mathcal O(n \log n)$
> - **6）**若输入的 $\texttt{d[i]}$ 都为同一个数，此程序平均的时间复杂度是( )。
> - A. $\mathcal O(n)$ B. $\mathcal O(\log n)$ C. $\mathcal O(n \log n)$ D. $\mathcal O(n^2)$
时间复杂度分析四连击是全卷的重点之一，~~当年考的时候被吓傻了，但是都蒙对了~~。
差不多是一个`nth_element`的实现，在 $\texttt d$ 中找出第 $k$ 大数。
- **1）**由于`rand() % (R - L + 1)`取 $0$ 时 $x$ 可以取到 $L$，因此选 **F**。
- **2）**观察循环，此时一定有 $a=b$，选 **T**。
- **3）**实际上**选项有误**，正确答案为 $\mathcal O(\log^2 n)$。
做几次实验发现这个答案是对的，但是怎么证呢？
我们先看一个[错解](https://www.luogu.com.cn/paste/oslkyc7v)（我自己瞎写的，最后推出 $\mathcal O(\log n)$ 的结果 ~~可能出题人当时也是这么推的~~）
哪里错了呢？我们发现，排序过程中 $\texttt d$ 中的要处理的一段数**不一定**单调递减。
比如数列 $d=\{1,2,3,4,5\}$，取 $x=4$，变为 $d=\{4,2,3,1,5\}$。
现在模拟可知 $a=b=5$，若取左半边继续递归，则变成 $d^\prime=\{2,3,1\}$。
怎么办呢？我们发现，**一次递归至多在数列中增加一个不单调的数**。那么之后每次递归**至多**会在这个数上浪费一次 $\texttt{swap}$。
那么我们先用前面的错解求出期望递归深度 $T^\prime(n)=\mathcal O(\log n)$，然后用一个**费用提前计算**的思想列出：
$$
T(n)=\dfrac{1}{n}\sum_{x=1}^n\left(\dfrac{x-1}{n}\left(T(x-1)+T^\prime(x-1)\right)+\dfrac{n-x}{n}\left(T(n-x)+T^\prime(n-x)\right)\right)+1
$$
之后继续借鉴那个错解里的思路，摊开计算贡献：
$$
T(n)=\dfrac{2}{n^2}\sum_{x=0}^{n-1} x(T(x)+T^\prime(x))+1
$$
由于上面证明中我们发现 $T^\prime(x)=\Theta(\log n)$，那么我们设 $A(n)=T(n)+\Theta(\log n)$，忽略后面的常数 $1$，有：
$$
A(n)=\dfrac{2}{n^2}\sum_{x=0}^{n-1} xA(x)+\Theta(\log n)
$$
另有：
$$
A(n-1)=\dfrac{2}{(n-1)^2}\sum_{x=0}^{n-2} x(A(x)+\mathcal O(\log x))+\Theta(\log n-1)
$$
为约去分母，我们将两式同乘一个平方，然后**差分**：
$$
n^2A(n)-(n-1)^2A(n-1)=\left(2\sum_{x=0}^{n-1} xA(x)+n^2\Theta(\log n)\right)-\left(2\sum_{x=0}^{n-2} xA(x)+(n-1)^2\Theta(\log n-1)\right)
$$
$$
=2(n-1)T(n-1)+n^2\Theta(\log n)-(n-1)^2\Theta(\log n-1)
$$
移项并作近似处理得：
$$
n^2A(n)=(n+1)(n-1)A(n-1)+n^2\log n-(n-1)^2\log (n-1)
$$
两边同除 $n(n+1)$：
$$
\dfrac{nA(n)}{n+1}=\dfrac{(n-1)A(n-1)}{n}+\dfrac{n^2\log n-(n-1)^2\log (n-1)}{n(n+1)}
$$
设 $B(n)=\dfrac{nA(n)}{n+1}$，上式可化为：
$$
B(n)=B(n-1)+\dfrac{n^2\log n-(n-1)^2\log (n-1)}{n(n+1)}
$$
简单归纳可得：
$$
B(n)=\sum_{x=1}^n \dfrac{x^2\log x-(x-1)^2\log (x-1)}{x(x+1)}
$$
令 $f(x)=x^2\log x-(x-1)^2\log (x-1)$，我们需要探索 $f(x)$ 的性质。
构造函数 $g(x)=f(x)-2x\log x-x$，扔进 Geogebra 里画个图像发现 $g(x)$ 恒小于 $0$。
实际上，我们对 $g(x)$ 求导便可证明这一点，此处不作展开。
因此有 $f(x)=\mathcal O(x\log x)$。近似地有：
$$
B(n)\sim \sum_{x=1}^n \frac{x\log x}{x^2}=\sum_{x=1}^n \frac{\log x}{x}\le \log n\sum_{x=1}^n \frac{1}{x}\sim \mathcal O(\log^2 n)
$$
于是 $A(n)=\mathcal O(\log^2 n)$，那么 $T(n)=\mathcal O(\log^2 n)$。
- **4）**在这里3）的假结论是正确的，要处理的一段数肯定是单调递减的。
那么我们发现对长度为 $n$ 的数列进行操作会带来 $\dfrac{n}{2}$ 次左右的 $\texttt{swap}$，那么我们直接用上面的方法差分即可。
$$
T(n)=\dfrac{1}{n}\sum_{x=1}^n\left(\dfrac{x-1}{n}T(x-1)+\dfrac{n-x}{n}T(n-x)\right) +\frac{n}{2}
$$
$$
T(n)=\dfrac{2}{n^2}\sum_{x=0}^{n-1} xT(x) +\frac{n}{2}
$$
$$
T(n-1)=\dfrac{2}{(n-1)^2}\sum_{x=0}^{n-2} xT(x)+\frac{n-1}{2}
$$
$$
n^2T(n)-(n-1)^2T(n-1)=\left(2\sum_{x=0}^{n-1} xT(x)+\frac{n^3}{2}\right)-\left(2\sum_{x=0}^{n-2} xT(x)+\frac{(n-1)^3}{2}\right)
$$
$$
=2(n-1)T(n-1)+\frac{3}{2}n^2-\frac{3}{2}n+\frac{1}{2}
$$
$$
n^2T(n)=(n+1)(n-1)T(n-1)+\frac{3}{2}n^2-\frac{3}{2}n+\frac{1}{2}
$$
$$
\dfrac{nT(n)}{n+1}=\dfrac{(n-1)T(n-1)}{n}+\dfrac{3n^2-3n+1}{2n(n+1)}
$$
设 $B(n)=\dfrac{nT(n)}{n+1}$：
$$
B(n)=\sum_{x=1}^n \dfrac{3x^2-3x+1}{2x(x+1)}=\sum_{x=1}^n\mathcal O(1)=\mathcal O(n)
$$
$$
T(n)=\dfrac{n+1}{n} B(n)=\mathcal O(n)
$$
选 **B**。
- **5）**平均时间复杂度就是下式：
$$
T(n)=\dfrac{1}{n}\sum_{x=1}^n\left(\dfrac{x-1}{n}T(x-1)+\dfrac{n-x}{n}T(n-x)\right) + n
$$
随便推推可得 $T(n)=\mathcal O(n)$。
最坏情况下，每次的分割点都取到边缘位置，此时有：
$$
T(n)=T(n-1)+n
$$
那么：
$$
T(n)=\sum_{x=1}^n x=\mathcal O(n^2)
$$
选 **A**。
- **6）**模拟程序过程，发现如果所有 $\texttt{d[i]}$ 都相同，那么在第一次循环时 $a$ 会停在 $L+1$ 处，$b$ 会一直左移至 $L+1$ 处。
因此就相当于每次花 $\Theta(n)$ 的时间把数列切出来一个数。因此，如果询问排名为 $k$ 的数，复杂度即为：
$$
\sum_{x=k}^nx=\frac{(n-k+1)(n-k+2)}{2}
$$
因此平均时间复杂度为：
$$
T(n)=\frac{1}{n}\sum_{k=1}^n \frac{(n-k+1)(n-k+2)}{2}=\frac{1}{n}\sum_{x=1}^n\frac{x^2+x}{2}=\mathcal O(n^2)
$$
选 **D**。
总结：大毒瘤。
（以下为**基于经验主义**的战术胡扯）一般而言，对于时间复杂度（快排求 K 大值）
$$
T(n)=\dfrac{1}{n}\sum_{x=1}^n\left(\dfrac{x-1}{n}T(x-1)+\dfrac{n-x}{n}T(n-x)\right) + f(n)
$$
其时间复杂度相当于
$$
T(n)=T(\frac{n}{2})+f(n)
$$
而对于时间复杂度（快排）
$$
T(n)=\dfrac{1}{n}\sum_{x=1}^n\left(T(x-1)+T(n-x)\right) + f(n)
$$
其时间复杂度相当于
$$
T(n)=2T(\frac{n}{2})+f(n)
$$
> **18.**
>
> ```c++
> #include <iostream>
> #include <queue>
> using namespace std;
>
> const int maxl = 20000000;
>
> class Map {
> struct item {
> string key; int value;
> } d[maxl];
> int cnt;
> public:
> int find(string x) {
> for (int i = 0; i < cnt; ++i)
> if (d[i].key == x)
> return d[i].value;
> return -1;
> }
> static int end() { return -1; }
> void insert(string k, int v) {
> d[cnt].key = k; d[cnt++].value = v;
> }
> } s[2];
>
> class Queue {
> string q[maxl];
> int head, tail;
> public:
> void pop() { ++head; }
> string front() { return q[head + 1]; }
> bool empty() { return head == tail; }
> void push(string x) { q[++tail] = x; }
> } q[2];
>
> string st0, st1;
> int m;
>
> string LtoR(string s, int L, int R) {
> string t = s;
> char tmp = t[L];
> for (int i = L; i < R; ++i)
> t[i] = t[i + 1];
> t[R] = tmp;
> return t;
> }
>
> string RtoL(string s, int L, int R) {
> string t = s;
> char tmp = t[R];
> for (int i = R; i > L; --i)
> t[i] = t[i - 1];
> t[L] = tmp;
> return t;
> }
>
> bool check(string st , int p, int step) {
> if (s[p].find(st) != s[p].end())
> return false;
> ++step;
> if (s[p ^ 1].find(st) == s[p].end()) {
> s[p].insert(st, step);
> q[p].push(st);
> return false;
> }
> cout << s[p ^ 1].find(st) + step << endl;
> return true;
> }
>
> int main() {
> cin >> st0 >> st1;
> int len = st0.length();
> if (len != st1.length()) {
> cout << -1 << endl;
> return 0;
> }
> if (st0 == st1) {
> cout << 0 << endl;
> return 0;
> }
> cin >> m;
> s[0].insert(st0, 0); s[1].insert(st1, 0);
> q[0].push(st0); q[1].push(st1);
> for (int p = 0;
> !(q[0].empty() && q[1].empty());
> p ^= 1) {
> string st = q[p].front(); q[p].pop();
> int step = s[p].find(st);
> if ((p == 0 &&
> (check(LtoR(st, m, len - 1), p, step) ||
> check(RtoL(st, 0, m), p, step)))
> ||
> (p == 1 &&
> (check(LtoR(st, 0, m), p, step) ||
> check(RtoL(st, m, len - 1), p, step))))
> return 0;
> }
> cout << -1 << endl;
> return 0;
> }
> ```
>
> - 判断题
>
> - **1）**输出**可能**为 $0$。（ ）
> - **2）**若输入的两个字符串长度均为 $101$，则 $m=0$ 时的输出与 $m=100$ 时的输出是一样的。（ ）
> - **3）**若两个字符串的长度均为 $n$，则最坏情况下，此程序的时间复杂度为 $\mathcal O((n!)^2)$。（ ）
>
> - 选择题
>
> - **4）**若输入的第一个字符串由 $100$ 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 $m$ 为 $0$，则输出为（ ）。
>
> - A. $49$ B. $50$ C. $100$ D. $-1$
>
> - **5）**己知当输入为 $\texttt{0123{\color{red}\texttt{\n}}3210{\color{red}\texttt{\n}}1}$ 时输出为 $4$，当输入为 $\texttt{012345{\color{red}\texttt{\n}}543210{\color{red}\texttt{\n}}1}$ 时输出为 $14$，当输入为 $\texttt{01234567{\color{red}\texttt{\n}}76543210{\color{red}\texttt{\n}}1}$ 时输出为 $28$，则当输入为 $\texttt{0123456789ab{\color{red}\texttt{\n}}ba9876543210{\color{red}\texttt{\n}}1}$ 时输出为
> ( ）。其中 ${\color{red}\texttt{\n}}$ 为换行符。
>
> - A. $56$ B. $84$ C. $102$ D. $68$
>
> - **6）**若两个字符串的长度均为 $n$，且 $0<m<n-1$，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法**正确**的是（ ）。
>
> （提示：考虑输入与输出有多少对字符前后顺序不一样。）
>
> - A. 若 $n,m$ 均为奇数，则输出**可能**小于 $0$。
> - B. 若 $n,m$ 均为偶数，则输出**可能**小于 $0$。
> - C. 若 $n$ 为奇数、$m$ 为偶数，则输出**可能**小于 $0$。
> - D. 若 $n$ 为偶数、$m$ 为奇数，则输出**可能**小于 $0$。
当年考的时候三道选择题全蒙错了/tuu
逐步分析代码，发现代码中实现了一个 $\mathcal O(n)$ 的 map 和一个 queue。
$\texttt{LtoR}$ 函数起**把字符串 $L$ 位置的字符移至 $R$ 处，原先 $(L,R]$ 中的字符依次前移**。$\texttt{RtoL}$ 函数同理。
$\texttt{check}$ 函数则是用于检查询问的字符串是否在另一个 map 内出现，若出现则输出二者的值之和并退出程序。
现在观察主函数，我们发现这是一个借助 queue 执行的 BFS 的过程。
BFS 中，每次把 $\texttt{st0}$ 中 **$m$ 位置的字符移到头部或尾部**，或把 $\texttt{st1}$ 中**头部或尾部的字符移到 $m$ 位置**。
那么，答案就是**二者经过最小轮数的操作达到相同的总操作数**。
由于操作作用在 $\texttt{st0}$ 上和作用在 $\texttt{st1}$ 上是对称的，我们发现实际上答案就是**使二者相同的最小的总操作数**。
- **1）**观察第 72~75 行，若 $\texttt{st0}=\texttt{st1}$，那么就会输出 $0$。选 **T**。
- **2）**$m=0$ 时相当于只允许 $\texttt{st0}$ 进行全局 $\texttt{LtoR}$，只允许 $\texttt{st1}$ 进行全局 $\texttt{RtoL}$，而 $m=100$ 时正好相反。
故选 **F**。
- **3）**最坏情况就是产生了所有可能的排列，共 $\mathcal O(n!)$ 个。
这样每次插入时都要花 $\mathcal O(n!)$ 的时间枚举 map 中的字符串，对每个都进行 $\mathcal O(n)$ 的比较。
总复杂度 $\mathcal O((n!)^2\cdot n)$。
- **4）**手动模拟 $len=3$ 的情况就能知道无法使二者达到相同。
事实上，全局 $\texttt{LtoR/RtoL}$ 所得的所有串是与原串循环同构的，而 $len>2$ 时原串与反串显然不满足循环同构。
因此会输出 $-1$ 表示不可能，选 **D**。
- **5）**乱搞题。由于给了我们三个点值，我们考虑插值，可以插出一个二次函数。
代入 $(2,4),(3,14),(4,28)$ 可得 $y=2x^2-4$。
然后代入 $x=6$ 可以得到答案 $68$。选 **D**。
- **6）**我们把 $\texttt{st1}$ 看作正序，进行映射。由于双向搜索的特性，我们可以钦定只有 $\texttt{st1}$ 发生了变化。
则若 $n$ 为奇数、$m$ 为偶数则每次交换逆序对数量**只能减少一个偶数**，而不能改变其奇偶性。
为啥只减少一个偶数捏？我们假设 $\texttt{RtoL}$ 时前面有 $x$ 个比它小的，$y$ 个比它大的。易知 $x+y$ 是偶数，因此二者奇偶性相同。
对 $x$ 个比它小的来说，将它前移共会增加 $x$ 个逆序对；对 $y$ 个比它大的来说，将它前移共会减少 $y$ 个逆序对。
因此 $x-y$ 是偶数，$\texttt{LtoR}$ 时同理。选 **C**。
评价：离谱。
### 三、完善程序
这部分倒是都对了。
**19.** 直接贪心，略。
> **20.** 懒得修 $\LaTeX$ 了，题面自己看去。
>
> ```c++
> #include <iostream>
>
> using namespace std;
>
> typedef long long LL;
>
> const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
> const LL INF = 1000000000000000LL;
> LL Max[MS + 4][MS + 4];
>
> int w(int x)
> {
> int s = x;
> while(x)
> {
> __(1)__;
> s++;
> }
> return s;
> }
>
> void to_max(LL &x, LL y)
> {
> if(x < y)
> x = y;
> }
>
> int main()
> {
> int n;
> LL ans = 0;
> cin >> n;
> for(int x = 0; x <= MS; x++)
> for(int y = 0; y <= MS; y++)
> Max[x][y] = -INF;
> for(int i = 1; i <= n ; i++)
> {
> LL a;
> cin >> a;
> int x = __(2)__ , y = a & MS;
> LL v = __(3)__;
> for(int z = 0; z < = MS; z++)
> to_max(v, __(4)__);
> for(int z = 0; z < = MS; z++)
> __(5)__;
> to_max(ans , v);
> }
> cout << ans << endl;
> return 0;
> }
> ```
>
> 1. A. `x >>= 1` B. `x ^= x&(x ^ (x + 1))` C. `x -= x | -x` D. `x ^= x &(x ^ (x - 1))`
>
> 2. A. `(a & MS) << B` B. `a >> B`
>
> C. `a & (1 << B)` D. `a & (MS << B)`
>
> 3. A. `-INF` B. `Max[y][x]` C. `0` D. `Max[x][y]`
>
> 4. A.`Max[x][z] + w(y ^ z)`
>
> B.`Max[x][z] + w(a ^ z)`
>
> C.`Max[x][z] + w(x ^ (z << B))`
>
> D.`Max[x][z] + w(x ^ z)`
>
> 5. A. `to_max(Max[y][z], v + w(a ^ (z << B)))`
>
> B.`to_max(Max[z][y], v + w((x ^ z) << B))`
>
> C.`to_max(Max[z][y], v + w(a ^ (z << B)))`
>
> D.`to_max(Max[x][z], v + w(y ^ z))`
赛后了解到这好像叫什么平衡规划。
主要思想是转移时保留一半**先前的信息**和一半**之后的信息**，不过只能适用于贡献可拆分的情况。
**1.** 这是一个求 $\mathrm{popcnt}$ 的过程，每次从 $x$ 中去掉它的 $\textrm{lowbit}$。选 **D**。
**2.** 由于 $y$ 是 $a$ 的后 $B$ 位，自然猜测 $x$ 是 $a$ 的前 $B$ 位。选 **B**。
**3.** 主要考虑到 $i=1$ 时所有转移答案都是 $-\infty$，因此需要有一个 $0$ 保底。
**4.** 这是要计算当前的最大答案，算出当时的后 $B$ 位的权值。选 **A**。
**5.** 算出前 $B$ 位的贡献来计算之后的答案。选 **B**。
评价：就这？？？