难度适中。

第十六题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream> 
#include <string> 
#include <vector> 

using namespace std; 

int f(const string &s, const string &t) 
{ 
    int n = s.length(), m = t.length(); 

    vector<int> shift(128, m + 1); 

    int i, j;

    for (j = 0; j < m; j++)
        shift[t[j]] = m - j;

    for (i =0; i<= n - m; i += shift[s[i + m]]){
        j =0;
        while(j < m && s[i +j] == t[j]) j++;
        if (j == m) return i;
    }

    return -1;
}

int main()
{
    string a ,b;
    cin >> a >> b;
    cout << f(a, b) << endl;
    return 0;
}

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：

判断题

  1. （1 分）当输入为“ abcde fg ”时，输出为-1。

    解析：

    阅读完程序后，我们发现它这个神似 KMP 的代码一定是一个匹配问题，这两个串一点关系都没有肯定无解 -1，所以判对

  2. 当输入为“ abbababbbab abab ”时，输出为 4。

    解析：

    他的 shift 记录的是这里失配以后往后跳到最短的后缀的，就是有种单纯找这个匹配位置的感觉，然后看这个匹配第一次匹配成功确实是在第四个，但是 i 是从 0 开始的输出因该是 3 判错。

  3. 当输入为“ GoodLuckCsp2022 22 ”时，第 20 行的“ j++ ”语句执行次数为 2。

    解析：

    匹配了两次之后就直接成功了，确实是二判对

单选题

  1. 该算法最坏情况下的时间复杂度为（ ）。

    A. $O(n + m)$
    B. $O(n\log m)$
    C. $O(m\log n)$
    D. $O(nm)$

    解析：

    怎么说呢，但凭这个神似 KMP 就足够证明复杂度了，选 D

  2. f(a, b) 与下列（ ）语句的功能最类似。

    A. a.find(b)
    B. a.rfind(b)
    C. a.substr(b)
    D. a.compare(b)

    解析：

    不难发现就是 find 的功能，find 可以找到某一个串是否存在于另一个串并返回第一次出现的位置，rfind 是反着找，至于 substr 参数就没有字符串的说法，compare 函数更是闻所未闻，选 A

  3. 当输入为“ baaabaaabaaabaaaa aaaa ”，第 20 行的“j++”语句执行次数为 （ ）。

    解析：

    模拟即可。答案是 B

第十七题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>

using namespace std;

const int MAXN = 105;

int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];

void init() 
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> val[i];
    int maximum = val[0];
    for (int i = 1; i < n; i++)
        if (val[i] > maximum) maximum = val[i];
    m = 1;
    while (maximum >= k) {
        maximum /= k;
        m++;
    }
}

void solve() 
{
    int base = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) cnt[j] = 0;
        for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
        for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
        for (int j = n - 1; j >= 0; j--) {
            temp[cnt[val[j] / base % k] - 1] = val[j];
            cnt[val[j] / base % k]--;
        }
        for (int j = 0; j < n; j++) val[j] = temp[j];
        base *= k;
    }
}

int main() 
{
    init();
    solve();
    for (int i = 0; i < n; i++) cout << val[i] << ' ';
    cout << endl;
    return 0;
}

判断题

  1. 这是一个不稳定的排序算法。（ ）

    解析：

    这个送分的，基数排序包稳定的，判错

  2. 该算法的空间复杂度仅与 $n$ 有关。（ ）

    解析：

    乱说，cnt 的大小于 k 有关（这题好像不是指申请的内存，而是指用掉的内存，判错

  3. 该算法的时间复杂度为 $O(m(n+k))$ 。（ ）

    解析：

    没问题这个可以直接看出来，对

单选题

  1. 当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 36 行，val[] 数组的内容依次为（ ）。

    解析：

    模拟，对于 k = 3 ，我们其实只第一次需要比较三进制下的第一位，2 2 1 1 1 ，又因为他是稳定的，所以说应该是 91 37 46 98 26 选 D

  2. 若 val[i]的最大值为 100，k 取（ ）时算法运算次数最少。

    解析：

    总的来讲还是与 n 有关，不确定选 D

  3. 当输入的 k 比 val[i]的最大值还大时，该算法退化为（ ）算法。

    解析：

    计数排序，因为这里相当于是统计了每一个的出现次数，但是桶排还要高级一点

第十八题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXL = 1000;

int n, k, ans[MAXL];

int main(void) 
{
    cin >> n >> k;
    if (!n) cout << 0 << endl;
    else 
    {
        int m = 0;
        while (n) 
        {
            ans[m++] = (n % (-k) + k) % k;
            n = (ans[m - 1] - n) / k;
        }
        for (int i = m - 1; i >= 0; i--)
            cout << char(ans[i] >= 10 ?
                        ans[i] + 'A' - 10 :
                        ans[i] + '0');
        cout << endl;
    }
    return 0;
}

假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：

判断题

  1. 该算法的时间复杂度为$O(\log_kn)$ 。

    解析：

    这个好玩了就，n 可以是负数，因为题目之说在了 int 范围内，所以说复杂度 n 那里应该加一个绝对值，判错

  2. 删除第 23 行的强制类型转换，程序的行为不变。

    解析：

    ？不强转输出就是 int 类型了。。。判错

  3. 除非输入的 n 为 0，否则程序输出的字符数为 $⌊\log⁡_k|n|⌋+1$ 。

    解析：

    m 确实是这个级别，并且 +1 是因为余数问题。判对

选择题

  1. 当输入为“100 7”时，输出为（ ）。

  2. 当输入为“-255 8”时，输出为（ ）。

  3. 当输入为“1000000 19”时，输出为（ ）。

    解析：

    这三题全都是弱智题，不讲了

第十九题

（归并第 k 小） 已知两个长度均为 n 的有序数组 a1 和 a2（均为递增序，但不保证严 格单调递增），并且给定正整数 k（1≤k≤2n），求数组 a1 和 a2 归并排序后的数组里 第 k 小的数值。

试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int solve(int *a1, int *a2, int n, int k) {
    int left1 = 0, right1 = n - 1;
    int left2 = 0, right2 = n - 1;
    while (left1 <= right1 && left2 <= right2) {
        int m1 = (left1 + right1) >> 1;
        int m2 = (left2 + right2) >> 1;
        int cnt = ①;
        if (②) {
            if (cnt < k) left1 = m1 + 1;
            else right2 = m2 - 1;
        } else {
            if (cnt < k) left2 = m2 + 1;
            else right1 = m1 - 1;
        }
    }
    if (③) {
        if (left1 == 0) {
            return a2[k - 1];
        } else {
            int x = a1[left1 - 1], ④;
            return std::max(x, y);
        } 
    } else {
            if (left2 == 0) {
                return a1[k - 1];
            } else {
                int x = a2[left2 - 1], ⑤;
                return std:: max(x, y);
            }
    }
}

选择题

①～⑤处应填（ ）

  1. A. (m1 + m2) * 2
    B. (m1 - 1) + (m2 - 1)
    C. m1 + m2
    D. (m1 + 1) + (m2 + 1)

    解析：

    这里只给了一个 solve 函数，就是补全函数的意思，东西也告诉你了是归并求第 k 小。

    第一处有一种二分位置的感觉我们要求的是比我这个位置小的数量，那么就是 C

  2. A. a1[m1] == a2[m2]
    B. a1[m1] <= a2[m2]
    C. a1[m1] >= a2[m2]
    D. a1[m1] != a2[m2]

    解析：

    注意到，两者较大的会放在合并序列的最后。

    假设 a2 是合并序列的最后一个，那么意味着如果 m2 后移动，后面的所有数字都是 a2。

    分析到这里差不多了，注意到他是 cnt<k 的时候把 m1 往右移。对应的就是 B

  3. A. left1 == right1
    B. left1 < right1
    C. left1 > right1
    D. left1 != right1

    解析：

    肯定是有一个区间不行了才会让结束，那么是哪一个呢，当然是 l1 > r1 因为这个贡献大

  4. A. y = a1[k - left2 - 1]
    B. y = a1[k - left2]
    C. y = a2[k - left1 - 1]
    D. y = a2[k - left1]

    解析：

    是已知一个 $a_0…a_{l−1}$ 的贡献下，求另一个 $a$ 的贡献。

    因为总数是 $k$ ，所以可以很直接得到另一个 $a$ 的长度。

    注意一下下标从 $0$ 开始。然后就是 C，下一题同理选 A

  5. A. y = a1[k - left2 - 1]
    B. y = a1[k - left2]
    C. y = a2[k - left1 - 1]
    D. y = a2[k - left1]

第二十题

（容器分水） 有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：

  1. FILL(i)：用水龙头将容器 $i(i∈1,2)$ 灌满水；
  2. DROP(i)：将容器 i 的水倒进下水道；
  3. POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。

求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。

试补全程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int f[N][N];
int ans;
int a, b, c;
int init;

int dfs(int x, int y) {
    if (f[x][y] != init)
        return f[x][y];
    if (x == c || y == c)
        return f[x][y] = 0;
    f[x][y] = init - 1;
    f[x][y] = min(f[x][y], dfs(a, y) + 1);
    f[x][y] = min(f[x][y], dfs(x, b) + 1);
    f[x][y] = min(f[x][y], dfs(0, y) + 1);
    f[x][y] = min(f[x][y], dfs(x, 0) + 1);
    int t = min(a - x, y);
    f[x][y] = min(f[x][y], ①);
    t = min(x, b - y);
    f[x][y] = min(f[x][y], ②);
    return f[x][y];
}

void go(int x, int y) {
    if (③)
        return;
    if (f[x][y] == dfs(a, y) + 1) {
        cout << "FILL(1)" << endl;
        go(a, y);
    } else if (f[x][y] == dfs(x, b) + 1) {
        cout << "FILL(2)" << endl;
        go(x, b);
    } else if (f[x][y] == dfs(0, y) + 1) {
        cout << "DROP(1)" << endl;
        go (0, y);
    } else if (f[x][y] == dfs(x, 0) + 1) {
        cout << "DROP(2)" << endl;
        go(x, 0);
    } else {
        int t = min(a - x, y);
        if(f[x][y] == ④) {
            cout << "POUR(2,1)" << endl;
            go(x + t, y - t);
        } else {
            t = min(x, b - y);
            if (f[x][y] == ⑤) {
                cout << "POUR(1,2)" << endl;
                go(x - t, y + t);
            } else
                assert(0);
        }
    }
}

int main() {
    cin >> a >> b >> c;
    ans = 1 << 30;
    memset(f, 127, sizeof f);
    init = **f;
    if ((ans = dfs (0, 0)) == init - 1)
        cout << "impossible";
    else {
        cout << ans << endl;
        go (0, 0);
    }
}

①～⑤处应填（ ）

  1. A. dfs(x + t, y - t) + 1
    B. dfs(x + t, y - t) - 1
    C. dfs(x - t, y + t) + 1
    D. dfs(x - t, y + t) - 1

    解析：

    一二两题都是容器互相倒，，，，所以说是 A，第二题选C

  2. A. dfs(x + t, y - t) + 1
    B. dfs(x + t, y - t) - 1
    C. dfs(x - t, y + t) + 1
    D. dfs(x - t, y + t) - 1

  3. A. x == c || y == c
    B. x == c && y == c
    C. x >= c || y >= c
    D. x >= c && y >= c

    解析：

    结束条件，一眼题，A

  4. A. dfs(x + t, y - t) + 1
    B. dfs(x + t, y - t) - 1
    C. dfs(x - t, y + t) + 1
    D. dfs(x - t, y + t) - 1

    解析：

    意思和第一第二两题一样，，，，A，下一题是 C

  5. A. dfs(x + t, y - t) + 1
    B. dfs(x + t, y - t) - 1
    C. dfs(x - t, y + t) + 1
    D. dfs(x - t, y + t) - 1