djwj233 的博客

djwj233 的博客

2020年 CSP-S1 解析

posted on 2021-08-26 20:56:31 | under 比赛题解 |

这张卷子场上考了 $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.

#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.

#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)$。

    做几次实验发现这个答案是对的,但是怎么证呢?

    我们先看一个错解(我自己瞎写的,最后推出 $\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.

#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$ 了,题面自己看去。

#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

评价:就这???