CSP-S1 2020 A卷 官方答案&简要解析

· · 个人记录

注：尚未完成

来源：官方答案&U裙的讨论。有争议的题本文一律按官方答案。

Part 1 单项选择

CBBBD BAACC CDBDC（比较显然）

Part 2 阅读程序

Code 1

FFTTCC

求不相等的 d_i,d_j 中 d_i+d_j-(d_i\operatorname{and}d_j) 的最大值。

判断题显然。单选第一道构造即可。

第二道，当且仅当 d_i,d_j 全为偶数时，这玩意才是偶数。

Code 2

FTXBAD
注：Code2 判断第二题有争议，第三题（是个单选）正确答案应该是\Theta(\log^2n)，但选项中无。官方说3选任何答案都行。

nth_element 的一种实现。

注意，此题期望情况下的计算应该每次分界线取中点。

判断题第一道显然，判断第二道和单选第三道的争议问题建议去看UOJ裙讨论。判断第二道当L和R相等时可能会出问题。

4和6都可以手推，需要注意一下两个 while 循环中带不带等号的问题。

5的期望复杂度用主定理第三种情形或者等比数列求和即可，复杂度递推式 T(n)=T(n/2)+n。最坏复杂度也可以手推。

实际上n方的情形都是把[L,R]割出来一个数，然后剩下的部分继续递归的……比如[L,R]割成[L,L]和[L+1,R]，这样就是n方的。

Code 3

TFFDDC

双向bfs。

此题的意义是给定两个字符串，给一个分界线 m，0 到 m 的子串可以进行 rtol 的轮换操作，m 到 len-1 的子串可以进行 ltor 的轮换操作，问第一个字符串需要几次变换才能成为第二个字符串。由于 ltor 和 rtol 两个函数十分容易看懂，这里就不讲了。

  1. 输出可能为0，显然是对的
  2. 关键观察：ltor 和 rtol 是互逆操作，且周期相等。知道这一点就显然了。
  3. 应该是 O(n(n!)^2)。
  4. m=0时，只有一个合法的轮换操作，显然不可能能翻转数组，显然-1。
  5. 可以通过猜想/构造看出来是 O(n^2) 的，于是待定系数法/拉格朗日插值/爆算/直接推导即可。
  6. 观察逆序对的奇偶性，也比较显然 然而我考场上写错了

Part 3 完善程序

Code 1

DBDDB

裸贪心，没啥好讲的

Code 2

DBCAB

  1. lowbit 的一些奇奇怪怪的写法
  2. 取出高位，显然B
  3. 最劣情况的答案是0，也就是啥都不选
  4. 根据题意推即可
  5. 根据题意推即可