最后三题似乎是有点代表性的难题，就挑着讲一讲罢，毕竟我基础的选择题都全对了后面的程序前两题也是一点小失误丢分不大，，，，

第十八题

首先我们浅浅的看一看代码：

// 这道题的编写者手写了几个数据结构，我们要注意一下。
// 下面模拟一下顺序查看代码的过程

#include <iostream>
#include <queue>
using namespace std;

const int maxl = 20000000;

// Map 顾名思义应该是个哈希表
class Map {
    struct item { // 哈希表内元素
        string key; int value; // 存了一个字符串和一个数字，目前还不知道是干什么的
    } d[maxl]; // 哈希表数组本体
    int cnt; // 目前不知道，简单看了看 insert 插入函数应该是哈希表内元素的数量。
  public:
    int find(string x) { // 函数名很简单，就是查找的意思。
        for (int i = 0; i < cnt; ++i) { // 很是暴力，直接大力查看这个哈希表内所有的元素qwq 
        	//记一下复杂度 O(cnt) 的
            if (d[i].key == x)
                return d[i].value;
        }
        return -1; // 找不到就是 -1
    } 
    // end 设为 -1 不知有何用意，估计是用来判有没有找到某个元素用的
    // 顺带一提，这个 static 考试的时候不知道什么意思，直接跳过了
    // 查了一下，对于这份代码而言，加不加差不多
    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; } // 就是字面意思的 pop
    // 要说可能一下子没看懂，但是说一开始头尾都是 0 后面尾巴是 1 了头的数值还是 0 
    // 数值存在 1，所以说的是 q[head + 1]
    string front() { return q[head + 1]; }
    // 这个正常，字面意思头尾相同就是空
    bool empty() { return head == tail; }
    // 就是字面意思的 push
    void push(string x) { q[++tail] = x;  }
} q[2]; // 定义了两个队列，目的是后面的玄学广搜

// st0 和 st1 看了后面的就知道应该是初始字符串和要变成的字符串
string st0, st1;
// m 似乎是一个操作的标识，看了后面的代码应该是一个类似于分界点的东西
int m;

// 这个函数很好理解，把 [L,R] 的数值整体循环左移 1
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;
}

// 遇上一个函数相似度极高，就是把 [L,R] 的数值整体循环右移 1
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;
}

// 这个是下面广搜的 check
// st 是目前状态，p 是当前是哪一个队列，step 是步数
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) {
      	// 这个 for 循环很新奇，其实就是来回更新两个广搜
        // 取出当前这个队列的队头，进行操作
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        // 这边的意思大概就是分两种队列讨论
        // p=0 的队列初值是 st0 也就是初始状态，是顺着的。
        // 顺着的说，m作为分界点，[0,m] 只能整体右移，[m,len-1] 只能整体左移
        // p=1 的队列初值是 st1 也就是结束状态，是反着的。
        // 相对的说，m作为分界点，[0,m] 只能整体左移，[m,len-1] 只能整体右移
        // check 如果找到了答案就会输出并返回 true，所以这边如果是 true 就直接 return 了
        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;
}

大概阅读完就知道了这个题目的操作逻辑。

接下来看一看题目

判断题

输出可能为 $0$ 。（）

解析：

初始结束字符串一样就是零，一眼题，判对
若输入的两个字符串长度均为 $101$ 时，则 $m=0$ 时的输出与 $m=100$ 时的输出是一样的。（）

解析：

带入看看，m = 0 时，[0,0] 意义不大，但是 [0,100] 就意味着整体左移
当 m = 100 时，也一样的，就是 [0,100] 循环右移
方向都不一样，怎么可能一样！所以判错
若两个字符串的长度均为 $n$ ，则最坏情况下，此程序的时间复杂度为 $O(n!)$ 。（）
解析：

分析一波，这个广搜的状态数量，我们首先就要想想，我们如何让一个数，与另一个数交换？我们以 1234 变成 1432 ，其中 m = 1 为例。
1
2
3
4
5
6
7
0: 1234
1: 2134
2: 2341
3: 2413
4: 4213
5: 4132
6: 1432
事实上，通过这种以 m 点作为中心，左右循环的方式，可以使得我们把任意两个数交换。也就是说，对于由 $n$ 个不同字母构成的字符串来说，状态最多有 $n!$ 种。

然后我们在想，他那个哈希表动不动就扫描所有的，复杂度是不是也是状态数，这一下复杂度就已经 $O((n!)^2)$ 了，另外提一嘴，函数 LtoR 和 RtoL 也是 $O(n)$ 的。。。总复杂度是 $O((n!)^2n)$ 。。。。

判错

单选题

（2.5 分）若输入的第一个字符串长度由 $100$ 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 $m$ 为 $0$，则输出为（）。
```
  A. 49          B. 50          C. 100          D. -1
```
解析：

这很简单，镜像的字符串怎么可能通过整体的循环左移而对其，显而易见的无解，直接选 D
（4 分）己知当输入为 0123\n3210\n1 时输出为 $4$ ，当输入为 012345\n543210\n1 时输出为 $14$ ，当输入为 01234567\n76543210\n1 时输出为 $28$ ，则当输入为0123456789ab\nba9876543210\n1 输出为（）。其中 \n 为换行符。
```
  A. 56          B. 84          C. 102          D. 68
```
解析：

首先，我们要看看如何把 0123 变成 3210 当 m = 1 的时候
1
2
3
4
5
0: 0123
1: 0231
2: 2031
3: 2310
4: 3210
刚好四步，来继续，我们看看当 m = 1 的时候，如何把 012345 变成 543210
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0: 012345
1: 023451
2: 034512
3: 304512
4: 345120
5: 351204
6: 312045
7: 132045
8: 120453
9: 104532
10: 015432
11: 045321
12: 405321
13: 450321
14: 543210
总之这个很好枚举，把样例都模拟了推出答案基本上就没什么难度了，选 D
（4 分）若两个字符串的长度均为 $n$ ，且 $0<m<n−1$ ，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不一样。

A. 若 $n,m$ 均为奇数，则输出可能小于 $0$ 。
B. 若 $n,m$ 均为偶数，则输出可能小于 $0$ 。
C. 若 $n$ 为奇数、$m$ 为偶数，则输出可能小于 $0$ 。
D. 若 $n$ 为偶数、$m$ 为奇数，则输出可能小于 $0$ 。

解析：

题目既然已经提示我们从逆序对分析，那么我们就看看有什么规律

考虑当 $n$ 为奇数时，假设 $st1$ 的字符严格单调递增，$st0$ 的字符严格单调递减，则 $st1$ 的逆序对为 $0$ ，$st0$ 的逆序对为 $\cfrac {n\times(n-1)}{2}$ 为奇数。由于 $m$ 为偶数，因此不论将$st0[m]$放在字符串开头或者结尾，逆序对的减少量都为偶数，最终不可能为$0$。

第十九题

（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$ 。第 $i$ 块蛋糕的价值是 $w_i$ ，体积是 $v_i$ 。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$ 。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $a(0<a<l)$ ，并将一块价值是 $w$ ，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $a×w$ ，体积是 $a×v$ ，另一块的价值是 $(1−a)×w$ ，体积是 $(1−a)×v$ 。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 $n=3,B=8$ ，三块蛋糕的价值分别是 $4,4,2$ ，体积分别是 $5,3,2$ 。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$ ，价值是 $2.4$ ，另一份体积是 $2$ ，价值是 $1.6$ ，然后把体积是 $3$ 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 $8.4$ ，故程序输出 $\cfrac{42}{5}$ 。

输入的数据范围为：$1≤n≤1000$ ，$1≤B≤10^5$ ，$1≤w_i,v_i≤100$ 。

提示：将所有的蛋糕按照性价比 $\cfrac{w_i}{v_i}$ 可从大到小排序后进行贪心选择。

试补全程序。

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
} 

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\n", w);
    else
        printf("%d/%d\n" w, v);
}
void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d" &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if (①) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if  (②) {
        ③
    } else {
        print(B * w[1] , v[1]);
        return 0;
    }
    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print (④);
            return 0;
        }
    print(⑤);
    return 0;
}

①处应填（）
1
2
3
4
A. w[j] / v[j] < w[j+1] / v[j+1]
B. w[j] / v[j] > w[j +1] / v[j+1]
C. v[j] * w[j+1] < v[j+1] * w[j]
D. w[j] * v[j+1] < w[j+1] * v[j]
解析：

题目已经给出提示，这就是一个简单的冒泡排序而已，按照题目的意思不难写出：
$$
\frac{w_i}{v_i} \gt \frac{w_{i+1}}{v_{i+1}}
$$
但是说，我们毕竟不可以用 int 整形做除法，这样是算的整除，所以说，我们只能使用交叉相乘变除为乘。学过分式的人都可以写出
$$
w_i\times v_{i + 1} \gt w_{i + 1}\times v_i
$$
直接选 C
②处应填（）
1
2
3
4
A. w[1] <= B
B. v[1] <= B
C. w[1] >= B
D. v[1] >= B
解析：

观察后面他直接 return 了。并且输出了 $\cfrac{B\times w_1}{v_1}$ 这是什么意思？显而易见就是性价比最高的物品超过了背包容量，所以我们只需要考虑这一种物品即可。那么超过就是 $v_1\gt B$ 那么上面的 if 语句就可以直接选 B 了。
③处应填（）
1
2
3
4
A. print(v[1],w[1]); return 0;
B. curV = 0; curW = 0;
C. print(w[1], v[1]); return 0;
D. curV = v[1]; curW = w[1];
解析：

首先，你下面的 else 都已经直接 return 了，你这个 if 再 return 是几个意思？直接排除 A，C

那么如果这个性价比最高的物品可以被背包容纳，这最好，所以说直接选了，也就是 D
④处应填（）
1
2
3
4
A. curW * v[i] + curV * w[i], v[i]
B. (curW - w[i]) * v[i] + (B - curV) * w[i], v[i]
C. curW + v[i], w[i]
D. curW * v[i] + (B - curV) * w[i], v[i]
解析：

看上面 if 的意思，就是能放就全放，这里放不下了，我们自然也得利益最大化，切块块放进来。

那么首先，我们以前都是整个放进来的，所以价值一定是整数，表示出来应该是一个带分数的形式，即 curW + 当前切下来的价值

当前切下来的价值，应该是首先看剩余空间能容纳多少，即 $\cfrac{B-curV}{v_i}$ 这个分数就是要留下来这个蛋糕的这么多分数，把整个的价值乘上就是 (B-curV) * w[i] / v[i] ，然后把带分数的那一部分转化过来，分子就是 curW * v[i] + (B - curV) * w[i] 分母自然就是 v[i] 。

所以选 D
⑤处应填（）
1
2
3
4
A. curW,curV
B. curW, 1
C. curV, curW
D. curV, 1
解析：

乍一看好像就是这个 print 是不太可能的，但是脑子一动，猛然想到，如果这个蛋糕从来没有切过且所有蛋糕的体积加起来也可以被背包装下，是不是就不会在 for 的过程中被输出并退出。也就是说，这时候答案是个整数，那就是直接输出 curW ，当然分母是 1 选 D

第二十题

（最优子序列）取 $m=16$ ，给出长度为 $n$ 的整数序列 $a_1,a_2,…,a_n(0≤a_i<2^m)$ 。对于一个二进制数 $x$ ，定义其分值 $w(x)$ 为 $x+popcnt⁡(x)$ ，其中 $popcnt⁡(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列 $b_1,b_2,…,b_k$ ，定义其子序列分值 $S$ 为 $w(b_1⊕b_2)+w(b_2⊕b_3)+w(b_3⊕b_4)+⋯+w(b_{k−1}⊕b_k)$ 。其中 $⊕$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n(1≤n≤40000)$ 接下来一行包含 $n$ 个整数 $a_1,a_2,⋯,a_n$ 。

提示：考虑优化朴素的动态规划算法，将前 $\cfrac m 2$ 位和后 $\cfrac m 2$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 $8$ 位是 $x$ 、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。

试补全程序。

#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) 
    {
        ①;
        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 = ② , y = a & MS;
        LL v = ③;
        for(int z = 0; z < = MS; z++)
            to_max(v, ④);
        for(int z = 0; z < = MS; z++)
            ⑤;
        to_max(ans , v);
    }
    cout << ans << endl;
    return 0;
}

①处应填（）
1
2
3
4
A. x >>= 1
B. x ^= x &(x ^ (x + 1))
C. x -= x | -x
D. x ^= x &(x ^ (x - 1))
解析：

这道题就是典型的 lowbit 与常见的不同，我们常见的应该是 x -= x & -x 或者 x -= x & (x - 1) ，自己带入也可以得出不错的结果，总之很简单的就选了 D 因为这个多了一个 x ^ (x-1) 其实对于 & 运算没有影响，如果这里的异或变出来了一个 1 也会被 & 搞掉，如果是把 1 变成了 0 （似乎不太可能的样子
②处应填（）
1
2
3
4
A. (a & MS) << B
B. a >> B
C. a & (1 << B)
D. a & (MS << B)
解析：

这道题太弱智，题目已经把第八位和高八位的定义告诉了你，你一看这个 y = a & MS 就是第八位，那 x 就只能是高八位了。也就是选 B 。
③处应填（）
1
2
3
4
A. -INF
B. Max[y][x]
C. 0
D. Max[x][y]
解析：

首先这时候 Max 数组都还没有赋值，所以说，BD 都可以直接排除，那么剩下来的 AC 之中就选 C 了，负数还真没必要
④处应填（）
1
2
3
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)
解析：

我们看这里的形式，显而易见就是在更新答案。我们就考虑这里的更新怎么统计。那么我们已经知道题目给出的就是高 $x$ 低 $y$ 的最大价值，我们要给他换了，就是说把低八位换了。那么造成的新的价值显而易见是 y ^ z 。
⑤处应填（）
1
2
3
4
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))
解析：

那么上一题统计了答案，把低八位换了，这里自然是要换掉高八位。那么就首先可以排除掉 AD 他们是对于低八位的更新没有用。然后就是看 BC 选什么，显而易见的，z 作为高八位贡献也要左移。也就是说，选 B ，B选项对于 z 的贡献单独的左移了 8 位满足条件。

好了以上就是这次 2020 提高组初赛的全部内容了~