感觉简单了这次

第十六题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;

unsigned short f(unsigned short x) {
    x ^= x << 6;
    x ^= x >> 8;
    return x;
}
int main() {
    unsigned short x;
    cin >> x;
    unsigned short y = f(x);
    cout << y << endl;
    return 0;
}

假设输入的 $x$ 是不超过 $65535$ 的自然数，完成下面的判断题和单选题：

判断题

  1. 当输入非零时，输出一定不为零。（）

    解析：

    异或操作左移右移不会搞掉我们原来有的 1，判对

  2. （2 分）将 f 函数的输入参数的类型改为 unsigned int，程序的输出不变。（）

    解析：

    肯定一不一样，这种左移右移会自然溢出的东西，内存翻了倍可不是开玩笑的，判错

  3. 当输入为 65535 时，输出为 63。（）

    解析：

    模拟。正确

  4. 当输入为 1 时，输出为 64。（）

    解析：

    模拟。错误，答案是 65

选择题

  1. 当输入为 512 时，输出为（）。

  2. 当输入为 64 时，执行完第 55 行后 x 的值为（）。

    解析：

    都是模拟题，直接手摸即可，答案是 B，D

第十七题

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
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long solve1(int n) {
    vector<bool> p(n + 1, true);
    vector<long long> f(n + 1, 0), g(n + 1, 0);
    f[1] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (p[i]) {
            vector<int> d;
            for (int k = i; k <= n; k *= i)
                d.push_back(k);
            reverse(d.begin(), d.end());
            for (int k : d) {
                for (int j = k; j <= n; j += k) {
                    if (p[j]) {
                        p[j] = false;
                        f[j] = i;
                        g[j] = k;
                    }
                }
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (p[i]) {
            f[i] = i;
            g[i] = i;
        }
    }
    long long sum = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
        sum += f[i];
    }
    return sum;
}

long long solve2(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout << solve1(n) << endl;
    cout << solve2(n) << endl;
    return 0;
}

假设输入的 $n$ 是不超过 $1000000$ 的自然数，完成下面的判断题和单选题：

判断题

  1. 将第 $15$ 行删去，输出不变（）

    解析：

    不可能，以及涉及到了关键的步骤。判错

  2. 当输入为 10 时，输出的第一行大于第二行。（）

    解析：

    首先我们来看 solve2 就是一个求因数和的模板，那么 solve1 是什么呢？其实也是，看下面答案的时候那种类似于等比数列的结构以及上面的一些猜测不难猜出。所以上下一直都是一样的（你也可以自己算算

    判错

  3. （2 分） 当输入为 1000 时，输出的第一行与第二行相等。（）

    解析：

    上面刚刚讲过，答案是对

单选题

  1. solve1(n) 的时间复杂度为（）。

    A. $O(n\log^2 n)$
    B. $O(n)$
    C. $O(n\log n)$
    D. $O(n\log\log n)$

    解析：

    solve1 函数其实就是 埃氏筛的变式，复杂度就是 D

  2. solve2(n) 的时间复杂度为（）。

    A. $O(n^2)$
    B. $O(n)$
    C. $O(n\log n)$
    D. $O(n\sqrt n)$

    解析：

    送分题，一眼 O(n) 。选 A

  3. 当输入为 5 时，输出的第二行为（）。

    A. 20
    B. 21
    C. 22
    D. 23

    解析：

    模拟谢谢，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
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool f0(vector<int> &a, int m, int k) {
    int s = 0;
    for (int i = 0, j = 0; i < a.size(); i++) {
        while (a[i] - a[j] > m)
            j++;
        s += i - j;
    }
    return s >= k;
}

int f(vector<int> &a, int k) {
    sort(a.begin(), a.end());

    int g = 0;
    int h = a.back() - a[0];
    while (g < h) {
        int m = g + (h - g) / 2;
        if (f0(a, m, k)) {
            h = m;
        }
        else {
            g = m + 1;
        }
    }

    return g;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << f(a, k) << endl;
    return 0;
}

假设输入总是合法的且 $1\le a_i\le10^8,n\le10000,1\le k\le\cfrac{n(n-1)}{2}$ ，完成下面的判断题和单选题:

判断题

  1. 将第 24 行的 m 改为 m - 1，输出有可能不变，而剩下情况为少 1 。（）

    解析：

    这道题很难评，包的啊哥哥，又是送分题，判对

  2. 将第 22 行的 g + (h - g) / 2 改为 (h + g) >> 1，输出不变。（）

    解析：

    又是送分题，，，，判对

  3. 当输入为 5 7 2 -4 5 1 -3，输出为 5。（）

    解析：

    模拟即可，判对

单选题

  1. 设 $a$ 数组中最大值减最小值加 $1$ 为 $A$ ，则 f 函数的时间复杂度为（）。

    解析：

    排序是 $O(n\log n)$ 二分是 $O(n\log A)$ 两个加起来就是 选项C

  2. 将第 10 行中的 > 替换为 >=，那么原输出与现输出的大小关系为（）。

    解析：

    替换后在 m 一定时，s 可能不变或变得更大，而变得更大可能会让本来的 false 变成 true ，使答案变得更小。

  3. 当输入为 5 8 2 -5 3 8 -12，输出为（）。

    解析：

    模拟谢谢，选 B

第十九题

（第 $k$ 小路径）给定一张 $n$ 个点 $m$ 条边的有向无环图，定点编号从 $0$ 到 $n−1$ ，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 $1≤n,m≤10^5,1≤k≤10^{18}$ 。

在程序中，我们求出从每个点出发的路径数量。超过 $10^{18}$ 的数都用 $10^{18}$ 表示。然后我们根据 $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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;
const long long LIM = 1000000000000000000ll;

int n, m, deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];

int next(std::vector<int> cand, long long &k) {
    std::sort(cand.begin(), cand.end());
    for (int u : cand) {
        if (①) return u;
        k -= f[u];
    }
    return -1;
}

int main() {
    std::cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v; // 一条从u到v的边
        E[u].push_back(v);
        ++deg[v];
    }
    std::vector<int> Q;
    for (int i = 0; i < n; ++i)
        if (!deg[i]) Q.push_back(i);
    for (int i = 0; i < n; ++i) {
        int u = Q[i];
        for (int v : E[u]) {
            if (②)
                Q.push_back(v);
            --deg[v];
        }
    }
    std::reverse(Q.begin(), Q.end());
    for (int u : Q) {
        f[u] = 1;
        for (int v : E[u])
            f[u] = ③;
    }
    int u = next(Q, k);
    std::cout << u << std::endl;
    while (④) {
        ⑤;
        u = next(E[u], k);
        std::cout << u << std::endl;
    }
    return 0;
}

  1. 解析：

    f[u] 表示以 u 为起点的路径数，k 表示要求的路径第 k 小，此处若 k<=f[u] 则说明要求的路径经过顶点 u。

  2. 解析：

    拓扑排序板子。
    若顶点 v 入度为 0 则将其加入 Q 中。这里是先判断后删除，所以 deg[v] == 1 。

  3. 解析：

    对于每一个 u -> v ，以 v 开头的路径数量之和再加 1 就是以 u 开头的路径数量。（从 u 走到 v ，然后继续往下走，或者只有一个 u ）
    按照拓扑序逆序遍历可以保证遍历到 u 时已经遍历过了每一个 v 。

  4. 解析：

    如果k>1就说明u不是终点，所以继续循环。（k=1表示路径是以u开头的路径中字典序最小的，即只有一个u）

  5. 解析：

    此处--k表示考虑过了以u为终点的情况

第二十题

(最大值之和）给定整数序列 $a_0,\dots,a_{n-1}$，求该序列所有非空连续子序列的最大值之和。上述参数满足 $1≤n≤ 10^5$ 和 $1≤a_i≤10^8$ 。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$（其中 $0≤l≤r<n$ ）表示，对应的序列为 $a_l,a_{l+1},\dots,a_r$。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 $[1,2,1,2]$ 时，要计算子序列 $[1]$ 、$[2]$ 、$[1]$ 、$[2]$ 、$[1,2]$ 、$[2,1]$ 、$[1,2]
$ 、$[1,2,1]$ 、$[2,1,2]$ 、$[1,2,1,2]$ 的最大值之和，答案为 $18$ 。注意 $[1,1]$ 和 $[2,2]$ 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以
会被分别计算。

解决该问题有许多算法，以下程序使用分治算法，时间复杂度 $O(n \log n)$。

试补全程序。

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
#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
    if (l + 1 == r) {
        ans += a[l];
        return;
    }
    int mid = (l + r) >> 1;
    std::vector<int> pre(a + mid, a + r);
    for (int i = 1; i < r - mid; ++i) ①;
    std::vector<long long> sum(r - mid + 1);
    for (int i = 0; i < r - mid; ++i)
        sum[i + 1] = sum[i] + pre[i];
    for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {
        while (j < r && ②) ++j;
        max = std::max(max, a[i]);
        ans += ③;
        ans += ④;
    }
    solve(l, mid);
    solve(mid, r);
}

int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    ⑤;
    std::cout << ans << std::endl;
    return 0;
}

这一道完善程序题最大的难点在于要看懂上述代码究竟怎样分治。
上述代码的分治部分对于区间 $[ l , r )$ 主要做了以下几件事：

  1. 求出区间的中点 mid
  2. 统计左端点再 mid 左边，且右端点在 mid 右边的区间最大值之和
  3. 分别递归下降到 $[l,mid)$ 和 $[mid,r)$ 如果能想明白这些，尤其是第二条，这题就好做多了

选择题

  1. 解析：

    此处用于求区间 $[mid,r)$ 的前缀最大值。选 D

  2. 解析：

    双指针，固定左端点，求右端点的范围使右端点小于左端点，所以选 B

  3. 解析：

    表示左端点为 $i$ ，右端点为 $ mid,\dotsc,j-1$ 中任意一点，最大值皆为 $\max$，共 $j-mid$ 个。

    所以选 A

  4. 解析：

    表示左端点为 $i$ ，右端点在 $j, \dotsc, r-1$ 中的区间的最大值之和。选A

  5. 解析：

    送分题，左闭右开，选C