KDOI Tournament 2026 Preliminary Round

已结束笔试

已结束

练习

KDOI Tournament 2026 Preliminary Round

本试卷共 43 小题，满分 100 分，考试时间 120 分钟。

姓名：—试卷号：#4版本：v4.131

一、单项选择题

本题共 15 小题，每小题 2 分，满分 30 分。在每题所给的四个选项中，有且仅有一个符合题目要求。

在 C++ 语言程序中，定义 int 类型数组 a[20][30]。已知 int 占 $4$ 字节，且数组按行连续储存，则 a[2][19] 与 a[7][4] 的首地址之差为

得分：2

$20$ 字节

$60$ 字节

$540$ 字节

$600$ 字节

下列整数中，在模 $12$ 意义下存在乘法逆元的是

得分：2

$3$

$4$

$5$

$6$

在 Linux 系统中，若文件 main 已经存在，下列指令中可以为当前用户增加该文件的可执行权限的是

得分：2

chmod +x main

grep main

mkdir main

pwd main

一个动态数组初始容量为 $1$ ，每当数组已满时，就申请一个容量为原来 $2$ 倍的新数组，并将原元素全部复制过去。连续执行 $n$ 次尾部插入操作，则所有元素复制操作的总次数为

得分：0

$\Theta(n)$

$\Theta(n\log n)$

$\Theta(n\sqrt{n})$

$\Theta(n^2)$

设 $1\le n\le 20$ ，运行以下代码：

long long cnt = 0;for (int s = 0; s < (1 << n); s++)    for (int t = s; t > 0; t = (t - 1) & s)        cnt++;

程序结束后，cnt 的值为

得分：0

$3^n$

$3^n-2^n$

$n\cdot 2^n$

$4^n-3^n$

在一棵非空有根树中，每个非叶结点恰好有 $2$ 或 $3$ 个儿子。设其中有 $x$ 个节点恰有 $2$ 个儿子， $y$ 个节点恰有 $3$ 个儿子，则该树中叶节点的个数为

得分：2

$x+y+1$

$2x+3y+1$

$x+2y+1$

$2x+2y+1$

对于某大小为 $N=32$ 的树状数组，其修改（单点加）操作的实现如下：

void modify(int x, int v) {    while (x < N) {        bit[x] += v;        x += x & (-x);    }}

执行一次 modify(6)，被修改的 bit 数组下标依次为

得分：0

$6, 7, 8, 16$

$6, 8, 16$

$6, 8, 16, 31$

$6, 8, 12, 16, 24$

从集合 $\{1,2,\ldots,20\}$ 中选择若干个数，使得选出的数中不存在两个数的和为 $22$ ，则选出的数的个数最大为

得分：0

$10$

$11$

$12$

$13$

某序列中不存在相同元素。交换序列中两个相邻位置上的元素后，该序列的逆序对数量

得分：2

一定不变

一定增加 $1$ 或减少 $1$

可能增加 $2$ 或减少 $2$

可能发生任意大小的变化

10.

给定一个边权均为正数的连通无向图 $G$ 以及一个顶点 $s$ ，现在选择一个正数 $C$ ，将所有与 $s$ 相邻的边的权值同时增加 $C$ ，则

得分：2

$G$ 中任意两点间的最短路径均不发生变化

$G$ 的任意一棵最小生成树的边权总和恰好增加 $C$

$G$ 的所有最小生成树组成的集合不发生变化

对于任意 $v\ne s$ ，从 $s$ 到 $v$ 的最短距离恰好增加 $C$

11.

元素 $1,2,3,4,5,6$ 按此顺序依次进入一个栈。栈的容量最多为 $3$ ，入栈和出栈操作可以任意交替进行。下列序列中，不可能是合法出栈序列的是

得分：2

$3,2,1,6,5,4$

$4,3,2,1,6,5$

$2,1,4,3,6,5$

$3,2,4,6,5,1$

12.

给定一个边权均非负的有向图，以及若干个特殊顶点组成的集合 $S$ 。现在新建一个顶点 $s_0$ ，并对每个 $u\in S$ ，加入一条从 $s_0$ 到 $u$ 的权值为 $0$ 的边，然后从 $s_0$ 开始运行一次 Dijkstra 算法，则对于原图中的一个顶点 $v$ ，所得到的最短距离为

得分：2

所有特殊顶点到 $v$ 的距离之和

所有特殊顶点到 $v$ 的距离的最小值

所有特殊顶点到 $v$ 的距离的最大值

距离 $v$ 最近的两个特殊顶点到 $v$ 的距离之和

13.

在平面直角坐标系中，从点 $(0,0)$ 出发，每次只能向右或向上移动一个单位。若移动过程中不能经过点 $(3,3)$ ，则到达点 $(6,6)$ 的不同最短路径共有多少条？

得分：2

$400$

$504$

$524$

$924$

14.

给定三个正整数 $k,a,b$ ，满足 $k<a< b$ 。则下列关于 $\gcd⁡(a-k,b-k)$ 的说法中，正确的是

得分：0

一定是 $\gcd⁡(a,b)$ 的因数

一定是 $a+b$ 的因数

一定是 $a-b$ 的因数

至少含有 $2$ 个不同的素因子

15.

在下面给出的有向图中，简单有向环的个数为

得分：2

$3$

$4$

$5$

$6$

二、阅读程序题

本题共 18 小题，除特殊说明外，判断题每小题 1.5 分，选择题每小题 3 分，满分 40 分。在每道选择题所给的四个选项中，有且仅有一个符合题目要求。保证程序输入不超过数组或字符串定义的范围。

（1）阅读下面的程序，完成所给小题。

#include <cstdio>bool used[15];int n, p[15];int ans = 0;void dfs(int k) {    if (k == n + 1) {        ++ans;        return;    }    for (int i = 1; i <= n; ++i) {        if (used[i]) continue;        if (k > 1 && (p[k - 1] + i) % 3 == 0)            continue;        p[k] = i;        used[i] = true;        dfs(k + 1);        used[i] = false;    }}int main() {    scanf("%d", &n);    dfs(1);    printf("%d\n", ans);    return 0;}

判断题

16.

（1 分）当输入的 $n=3$ 时，程序输出 2。

得分：1

正确

错误

17.

在 dfs 函数运行过程中，参数 $k$ 的取值始终满足 $1\le k \le n + 1$ 。

得分：1.5

正确

错误

18.

删除程序的第 19 行，不会影响程序输出。

得分：1.5

正确

错误

单选题

19.

当输入的 $n=4$ 时，程序输出为

得分：0

4

6

8

12

20.

如果在调用 dfs(1) 前，数组 p 中保存着任意初值，则

得分：3

程序输出一定增大

程序输出一定减小

输出可能改变，但无法确定

不影响程序输出

21.

如果删除第 13 行的语句，则当输入的 $n=3$ 时，程序输出为

得分：3

9

10

12

27

（2）阅读下面的程序，完成所给小题。

#include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;using ull = unsigned long long;const ull BASE = 131;string s;vector<ull> h, pw;ull get_hash(int l, int r) {    return h[r] - h[l - 1] * pw[r - l + 1];}bool check(int len) {    vector<ull> value;    for (int l = 1; l + len - 1 <= (int)s.size(); ++l) {        int r = l + len - 1;        value.push_back(get_hash(l, r));    }    sort(value.begin(), value.end());    for (int i = 1; i < (int)value.size(); ++i)        if (value[i] == value[i - 1]) return true;    return false;}int main() {    cin >> s;    int n = s.size();    h.assign(n + 1, 0);    pw.assign(n + 1, 1);    for (int i = 1; i <= n; ++i) {        h[i] = h[i - 1] * BASE             + (unsigned char)s[i - 1] + 1;        pw[i] = pw[i - 1] * BASE;    }    int left = 0, right = n;    while (left < right) {        int mid = (left + right) >> 1;        if (check(mid)) left = mid + 1;        else right = mid;    }    cout << left - 1 << '\n';    return 0;}

判断题

22.

当输入为 banana 时，程序输出 3。

得分：0

正确

错误

23.

（2 分）不考虑哈希冲突，当 len ≥ 2 且 check(len) 返回 true 时，check(len - 1) 也一定返回 true。

得分：2

正确

错误

24.

将第 41 行的代码改为 int mid = (left + right - 1) / 2;，则程序可能会发生死循环。

得分：1.5

正确

错误

单选题

25.

不考虑哈希冲突，该程序求出的是

得分：0

字符串的最长回文子串的长度

字符串中出现至少两次的最长子串长度，两次出现可以重叠

出现至少两次且两次出现不能重叠的最长子串长度

字符串和其反串的最长公共子串的长度

26.

如果将 BASE 改为 1，程序最可能出现的问题是

得分：3

二分查找一定陷入死循环

数组 pw 一定发生越界

不同子串更容易得到相同的哈希值

程序一定输出 0

27.

设输入的字符串长度为 $n$ ，该程序的时间复杂度最接近

得分：3

$\Theta(n\log n)$

$\Theta(n^2)$

$\Theta(n^2\log n)$

$\Theta(n\log^2 n)$

（3）阅读下面的程序，完成所给小题。

#include <algorithm>#include <cstdio>#include <vector>using namespace std;struct Edge {    int to;    int w; // 边权};int n;vector<vector<Edge>> graph;vector<int> sz;vector<long long> f;void dfs1(int u, int parent, long long dist) {    sz[u] = 1;    f[1] += dist;    for (Edge e : graph[u]) {        int v = e.to;        if (v == parent) continue;        dfs1(v, u, dist + e.w);        sz[u] += sz[v];    }}void dfs2(int u, int parent) {    for (Edge e : graph[u]) {        int v = e.to;        if (v == parent)            continue;        f[v] = f[u] + 1LL * (n - 2 * sz[v]) * e.w;        dfs2(v, u);    }}int main() {    scanf("%d", &n);    graph.resize(n + 1);    sz.resize(n + 1);    f.assign(n + 1, 0);    for (int i = 1; i < n; ++i) { // 读入树结构        int u, v, w;        scanf("%d%d%d", &u, &v, &w);        graph[u].push_back({v, w});        graph[v].push_back({u, w});    }    dfs1(1, 0, 0);    dfs2(1, 0);    long long best = f[1];    int cnt = 0;    for (int i = 1; i <= n; ++i) best = min(best, f[i]);    for (int i = 1; i <= n; ++i)        if (f[i] == best) ++cnt;    printf("%lld %d\n", best, cnt);    return 0;}

输入保证所有边权均为正整数。

判断题

28.

程序执行完 dfs1 和 dfs2 后，f[u] 表示结点 $u$ 到树中所有结点的距离之和。

得分：0

正确

错误

29.

将程序的第 22 行改为 dfs1(v, u, e.w);，不会影响程序输出。

得分：1.5

正确

错误

30.

若将所有边权同时乘以同一个正整数 $c$ ，则程序输出的 best 变为原来的 $c$ 倍，而 cnt 保持不变。

得分：1.5

正确

错误

31.

设树中结点数为 $n$ ，该程序的时间和空间复杂度均为 $\Theta(n)$ 。

得分：1.5

正确

错误

单选题

32.

将程序的第 49、50 行函数的第一个参数均改为某一大于 $1$ 的正整数 $r$ ，则

得分：0

程序输出的第一个数一定会发生变化，但第二个数不会

程序输出的第一个数和第二个数均可能发生变化

程序输出的第二个数一定会发生变化，但第一个数不会

程序输出的第一个数和第二个数均不会发生变化

33.

（4 分）程序结束后，关于满足 f[u] == best 的结点，下列说法一定正确的是

得分：0

有且仅有一个这样的节点

至多有两个这样的节点

这样的结点一定是度数最大的结点

这样的结点数量可能达到 $3$

三、完善程序题

本题共 10 小题，每小题 3 分，满分 30 分。在每题所给的四个选项中，有且仅有一个符合题目要求。

（1）（跳过区间）给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$ 。初始时有一个整数 $x=0$ ，你需要选择一个区间 $[l,r]$ ，接下来，对于每个 $i=1,2,\ldots,n$ 依次执行：

如果 $l\le i\le r$ ，则跳过此次操作；
否则：
- 如果 $a_i>x$ ，则将 $x$ 赋值为 $x+1$ ；
- 如果 $a_i<x$ ，则将 $x$ 赋值为 $x-1$ ；
- 如果 $a_i=x$ ，则 $x$ 的值保持不变。

你的目标是最大化执行完所有操作后 $x$ 的值。注意，你必须选择一个区间跳过。

以下程序实现了该算法。试补全程序。

#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;const int _N = 3e5 + 5, inf = 1e9;int n, a[_N];int before[_N], skipping[_N], after[_N];int trans(int x, int y) {    if(x < y) return x + 1;    if(x > y) return x - 1;    return x;}int main() {    cin >> n;    for(int i = 1; i <= n; i++) cin >> a[i];    before[0] = 0;    skipping[0] = after[0] = ①;    for(int i = 1; i <= n; i++) {        before[i] = ②;        skipping[i] = ③;        after[i] = trans(④, a[i]);    }    cout << ⑤ << '\n';    return 0;}

34.

①处应填

得分：0

0

n

inf

-n

35.

②处应填

得分：3

before[i - 1]

trans(before[i], a[i])

max(before[i - 1], trans(before[i], a[i]))

trans(before[i - 1], a[i])

36.

③处应填

得分：0

before[i - 1]

max(skipping[i - 1], after[i - 1])

max(before[i], skipping[i - 1])

max(before[i - 1], skipping[i - 1])

37.

④处应填

得分：0

after[i - 1]

max(before[i - 1], after[i - 1])

max(skipping[i], after[i - 1])

max(skipping[i - 1], after[i - 1])

38.

⑤处应填

得分：0

before[n]

after[n]

max(before[n], after[n])

max(skipping[n], after[n])

（2）（美妙路径）给定一棵 $n$ 个节点的树，每个节点分别编号为 $1$ 到 $n$ 。如果一条路径满足：该路径上所有节点的编号在排序后恰好构成一段连续的数字，则称这条路径是“美妙的”。你的目标是统计出所有“美妙的”路径的条数。

以下程序读取树的结构并输出最终答案。试补全程序。

提示：程序将原问题转化为如下问题：计算区间 $[l, r]$ 的个数，使得节点 $l, l+1, \ldots, r$ 在树上构成一条路径。

#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;const int _N = 2e5 + 5, inf = 1e9;struct node {    int mn, num, tag;} t[_N << 2];void pushup(int u) {    t[u].mn = min(t[u << 1].mn, t[u << 1 | 1].mn);    t[u].num = 0;    if (t[u << 1].mn == t[u].mn) t[u].num += t[u << 1].num;    if (t[u << 1 | 1].mn == t[u].mn) t[u].num += t[u << 1 | 1].num;}void addtag(int u, int x) {    t[u].mn += x, t[u].tag += x;}void pushdown(int u) {    if (!t[u].tag) return;    addtag(u << 1, t[u].tag), addtag(u << 1 | 1, t[u].tag);    t[u].tag = 0;}void build(int u, int l, int r) {    t[u] = ①;    if (l == r) return;    int mid = (l + r) >> 1;    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);}void modify(int u, int l, int r, int ql, int qr, int x) {    if (ql <= l && r <= qr) {        addtag(u, x);        return;    }    pushdown(u);     int mid = (l + r) >> 1;    if (ql <= mid) modify(u << 1, l, mid, ql, qr, x);    if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, x);    pushup(u);}void change(int u, int l, int r, int k) {    if (l == r) {        t[u].mn = t[u].tag = 0;        return;    }    pushdown(u);     int mid = (l + r) >> 1;    if (k <= mid) change(u << 1, l, mid, k);    else change(u << 1 | 1, mid + 1, r, k);    pushup(u);}int n, lst[_N][3], bad[_N];bool vis[_N];vector<int> e[_N];int main() {    cin >> n;    for (int i = 1, u, v; i < n; i++) {        cin >> u >> v;        e[u].emplace_back(v), e[v].emplace_back(u);    }    build(1, 1, n);    ll ans = 0;    for (int u = 1; u <= n; u++) {        change(1, 1, n, u), modify(1, 1, n, 1, u, 1);        for (int v : e[u]) {            if (②) modify(1, 1, n, 1, v, -1);        }        vis[u] = true, bad[u] = lst[u][2];        if (bad[u]) modify(1, 1, n, 1, bad[u], 1);        for (int v : e[u]) {            lst[v][2] = lst[v][1];            lst[v][1] = lst[v][0];            lst[v][0] = ③;            if (!vis[v]) continue;            int nw = ④;            if (nw > bad[v]) modify(1, 1, n, bad[v] + 1, nw, 1);            bad[v] = nw;        }        ⑤;    }    cout << ans << '\n';    return 0;}

39.

① 处应填

得分：3

{inf, r - l + 1, 0}

{inf, 1, 0}

{inf, r - l + 1, r - l + 1}

{inf, 1, r - l + 1}

40.

②处应填

得分：0

bad[v]

!bad[v]

u < v

v < u

41.

③处应填

得分：0

u

v

1

0

42.

④处应填

得分：3

lst[v][1] ? min(v, lst[v][1]) : 0

lst[v][2] ? max(v, lst[v][2]) : 0

lst[v][1] ? max(v, lst[v][1]) : 0

lst[v][2] ? min(v, lst[v][2]) : 0

43.

⑤处应填

得分：3

if (t[u].mn == 1) ans += t[1].num

if (t[1].mn == 1) ans++

if (t[u].mn == 1) ans++

if (t[1].mn == 1) ans += t[1].num