目录

前言答案合集单项选择题T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15

阅读程序T1判断-1判断-2判断-3判断-4单选-1单选-2

T2判断-1判断-2判断-3选择-1选择-2选择-3

T3判断-1判断-2判断-3选择-1选择-2选择-3

完善程序T1T1T2T3T4T5

T2写在前面的话T1T2T3T4T5

尾声

前言

又到了CSP前夕，刷历年真题却发现没有题解，于是自己写了一篇

答案合集

题号
1~5	B	A	A	C	B
6~10	A	C	B	A	C
11~15	A	C	C	B	A
16~20	✓	✗	✓	✗	B
21~25	D	✗	✗	✓	D
26~30	B	B	✓	✓	✓
31~35	C	B	B	B	A
36~40	A	D	C	D	B
41~43	A	C	A	😛	😛

单项选择题

T1

在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？

A. newdir

B. mkdir

C. create

D. mkfold

这题没什么好说的

T2

0

,

1

,

2

,

3

,

4

0,1,2,3,4

0,1,2,3,4 中选取

4

4

4 个数字，能组成（）个不同四位数（注：最小的四位数是

1000

1000

1000 最大的四位数是

9999

9999

9999）。

A.

96

96

96

B.

18

18

18

C.

120

120

120

D.

84

84

84

最高位不能填

0

0

0，有四钟不同的情况，次高位不能填和最高位相同的数字，有四种不同的情况，再下一位不能和前两位相同，有三种情况，以此类推。

根据乘法原理，总共有

4

∗

4

∗

3

∗

2

=

96

4*4*3*2 = 96

4∗4∗3∗2=96种情况。要是不放心也可以枚举。

T3

假设

n

n

n 是图的顶点的个数，

m

m

m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于

m

=

Θ

(

n

)

m=\Theta{(n)}

m=Θ(n) 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

A.

O

(

m

log

⁡

n

∗

log

⁡

log

⁡

n

)

O(m\sqrt{\log{n}} * \log{\log{n}})

O(mlogn

​∗loglogn)

B.

O

(

n

2

+

m

)

O(n^2+m)

O(n2+m)

C.

O

(

n

2

log

⁡

m

+

m

log

⁡

n

)

O(\frac{n^2}{\log{m}} + m\log{n})

O(logmn2​+mlogn)

D.

O

(

m

+

n

log

⁡

n

)

O(m + n\log{n})

O(m+nlogn)

对于这一题， “

m

=

Θ

(

n

)

m = \Theta{(n)}

m=Θ(n)” 可以简单粗暴的理解为

m

=

n

m=n

m=n，这样一来就很好比较了。

T4

假设有

n

n

n 根柱子，需要按照以下规则依次放置编号为

1

,

2

,

3

,

⋯

1,2,3,⋯

1,2,3,⋯ 的圆环：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有

4

4

4 根柱子时，最多可以放置（）个圆环

A.

7

7

7

B.

9

9

9

C.

11

11

11

D.

5

5

5

首先，需要知道，“相邻圆环”指上下相邻。

然后手动贪心即可，

11

11

11个圆环的放法如下图所示：

T5

以下对数据结构的表述不恰当的一项是：

A. 队列是一种先进先出（FIFO）的线性结构

B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索

C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构

D. 二叉树是一种每个结点最多有两个子结点的树结构

A C D 显然正确

B 纯属胡言乱语，哈夫曼树是一种贪心，主要应用是哈夫曼编码，感兴趣的读者可以自行搜索。

T6

以下连通无向图中，（）一定可以用不超过两种颜色进行染色

A. 完全三叉树

B. 平面图

C. 边双连通图

D. 欧拉图

“染色”即二分图，完全三叉树的染色方法为：把所有偶数层的节点染成一个颜色，奇数层的节点染成另一个颜色。

T7

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列

X

=

x

1

,

x

2

,

x

3

,

⋯

,

x

m

X=x_1,x_2,x_3,⋯,x_m

X=x1​,x2​,x3​,⋯,xm​ 和

Y

=

y

1

,

y

2

,

y

3

,

⋯

,

y

n

Y=y_1,y_2,y_3,⋯,y_n

Y=y1​,y2​,y3​,⋯,yn​， 最长公共子序列（LCS）问题的目标是找到一个最长的新序列

Z

=

z

1

,

z

2

,

z

3

,

⋯

,

z

k

Z=z_1,z_2,z_3,⋯,z_k

Z=z1​,z2​,z3​,⋯,zk​ ，使得序列

Z

Z

Z 既是序列

X

X

X 的子序列，又是序列

Y

Y

Y 的子序列，且序列

Z

Z

Z 的长度

k

k

k 在满足上述条件的序列里是最大的。 （注：序列

A

A

A 是序列

B

B

B 的子序列，当且仅当在保持序列

B

B

B 元素顺序的情况下，从序列

B

B

B 中删除若干个元素，可以使得剩余的元素构成序列

A

A

A）则序列 <code>ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）

A. 4

B. 5

C. 6

D. 7

最长公共子序列是ABCABA或ABAABA。

T8

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出

x

x

x 点，得到

2

x

2x

2x 元；第二次掷出

y

y

y 点，当

y

=

x

y=x

y=x 时玩家会失去之前得到的

2

x

2x

2x 元而当

y

≠

x

y \neq x

y=x 时玩家能保住第一次获得的

2

x

2x

2x 元。上述

x

,

y

∈

1

,

2

,

3

,

4

,

5

,

6

x,y \in 1,2,3,4,5,6

x,y∈1,2,3,4,5,6。 例如：玩家第 一次掷出

3

3

3 点得到

6

6

6 元后，但第二次再次掷出

3

3

3 点，会失去之前得到的

6

6

6 元，玩家最终收益为

0

0

0 元；如果玩家第一次掷出

3

3

3 点、第二次掷出

4

4

4 点，则最终收益是

6

6

6 元。假设骰子掷出任意一点的概率均为

1

6

\frac{1}{6}

61​​ ,玩家连续掷两次般子后，所有可能情形下收益的平均值是多少？

A.

7

7

7 元

B.

35

6

\frac{35}{6}

635​ 元

C.

16

3

\frac{16}{3}

316​ 元

D.

19

3

\frac{19}{3}

319​ 元

总共只有36种情况，枚举即可：

0元的有：(1,1) (2,2) …… (6,6) 共六种。

2元的有：(1,2) (1,3) …… (1,6) 共五种。

4元、6元、8元、10元、12元的情况与2元相同，各5种。

所有可能情况下的收益之和为

(

2

+

4

+

6

+

8

+

10

+

12

)

∗

5

=

210

(2+4+6+8+10+12)*5=210

(2+4+6+8+10+12)∗5=210元，所以所有可能情况下收益的平均值是

210

36

\frac{210}{36}

36210​即

35

6

\frac{35}{6}

635​元。

T9

假设我们有以下的 C++ 代码：

int a = 5, b = 3, c = 4;

bool res = a & b || c ^ b && a | c;

请问，res 的值是什么？

提示：在 C++ 中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非与位非优先级相同，且高于所有双目运算符。

A. true

B. false

C. 1

D. 0

根据“提示”所说的顺序手动计算即可。注意，逻辑运算时，所有非

0

0

0的数均视为

t

r

u

e

true

true，

0

0

0视为

f

a

l

s

e

false

false。

至于为什么答案是

t

r

u

e

true

true而非

1

1

1，咱也不知道，咱也不敢问😁

T10

假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

A. 快速排序对于此类输入的表现最好，因为数组已经排序。

B. 快速排序对于此类输入的时间复杂度是

Θ

(

n

log

⁡

n

)

\Theta(n\log{n})

Θ(nlogn)。

C. 快速排序对于此类输入的时间复杂度是

Θ

(

n

2

)

\Theta(n^2)

Θ(n2)

D. 快速排序无法对此类数组进行排序，因为数组已经排序。

这种情况下，快速排序的递归会进行

n

n

n次，每次把第一个元素分为一部分，剩下的分为一部分，总复杂度退化到

Θ

(

n

2

)

\Theta(n^2)

Θ(n2)。

T11

以下哪个命令，能将一个名为 <code>main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？

A. g++ -o main main.cpp

B. g++ -o main.cpp main

C. g++ main -o main.cpp

D. g++ main.cpp -o main.cpp

没啥好说的。

T12

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？

A.

4

4

4 个结点的树

B.

6

6

6 个结点的树

C.

7

7

7 个结点的树

D.

8

8

8 个结点的树

注意到，偶数个节点的树是一条链时一定有两个重心。

T13

如图是一张包含

6

6

6 个顶点的有向图，但顶点间不存在拓扑序。

如果要删除其中一条边，使这

6

6

6 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？

A.

1

1

1

B.

2

2

2

C.

3

3

3

D.

4

4

4

不存在拓扑序无非是应为有环。因此，只要破坏掉这个环即可。也就是说，删除下图中的三条边都是可以的：

T14

若

n

=

∑

i

=

0

k

1

6

i

∗

x

i

n = \sum^{k}_{i=0}16^i*x_i

n=∑i=0k​16i∗xi​ ，定义

f

(

n

)

=

∑

i

=

0

k

x

i

f(n)=\sum^{k}_{i=0} x_i

f(n)=∑i=0k​xi​，其中

x

i

∈

0

,

1

,

…

,

15

x_i\in0,1,\dotsc,15

xi​∈0,1,…,15。对于给定自然数

n

0

n_0

n0​​ ，存在序列​

n

0

,

n

1

,

n

2

,

…

,

n

m

n_0,n_1,n_2,\dotsc , n_m

n0​,n1​,n2​,…,nm​，其中对于

1

≤

i

≤

m

1≤i≤m

1≤i≤m 都有

n

i

=

f

(

n

i

−

1

)

n_i=f(n_{i-1})

ni​=f(ni−1​) ，且

n

m

=

n

m

−

1

n_m=n_{m-1}

nm​=nm−1​ ，称

n

0

n_0

n0​ 为

n

m

n_m

nm​ 关于

f

f

f 的不动点。

问在

10

0

16

100_{16}

10016​ 到

1

A

0

16

1A0_{16}

1A016​ 中，关于

f

f

f 的不动点为

9

9

9 的自然数个数为（）。

A.

10

10

10

B.

11

11

11

C.

12

12

12

D.

13

13

13

不知道各位看到这道题是什么感觉，反正我被这道题震撼了两次。一次是在考场上看见这道题，一次是在写这篇题解的时候输入各种LaTeX。

言归正传，这道题

n

n

n和

f

f

f的定义相当丑陋，但是无意间发现“

16

16

16”出现的频率相当高，再加上设问是两个十六进制数，我们不难发现：

n

n

n就是一个十六进制数

f

(

n

)

f(n)

f(n)就是这个数在16进制下各位数字之和（下称数字和）关于

f

f

f的不动点为

9

9

9就是说这个数字在十六进制下的数字和为

9

9

9或数字和的数字和为

9

9

9以此类推

然后枚举即可。这11个数字分别是：

10

8

16

108_{16}

10816​

11

7

16

117_{16}

11716​

12

6

16

126_{16}

12616​

13

5

16

135_{16}

13516​

14

4

16

144_{16}

14416​

15

3

16

153_{16}

15316​

16

2

16

162_{16}

16216​

17

1

16

171_{16}

17116​

18

0

16

180_{16}

18016​

18

F

16

18F_{16}

18F16​

19

E

16

19E_{16}

19E16​

注意：

不要忘记百位上有个

1

1

1因为是十六进制下的数字和，所以两次数字和为

9

9

9即表示一次数字和为

1

8

16

18_{16}

1816​，而非

18

18

18（

2

7

16

27_{16}

2716​等同理）

T15

现在用如下代码来计算

x

n

x^n

xn ，其时间复杂度为（）。

<code>double quick_power(double x, unsigned n) { -- -->

if (n == 0) return 1;

if (n == 1) return x;

return quick_power(x, n / 2)

* quick_power(x, n / 2)

* ((n & 1) ? x : 1);

}

A.

O

(

n

)

O(n)

O(n)

B.

O

(

1

)

O(1)

O(1)

C.

O

(

log

⁡

n

)

O(\log n)

O(logn)

D.

O

(

n

log

⁡

n

)

O(n \log n)

O(nlogn)

这题会主定理的同学可以用主定理算，不会主定理的同学可以猜，具体方法如下：

首先，

O

(

1

)

O(1)

O(1)太离谱了，肯定不对第二， 解答树有

log

⁡

n

\log n

logn层，最深的一层有大约

n

n

n个节点，所以肯定至少是

O

(

n

)

O(n)

O(n)第三，解答树是一颗二叉树，所以最多大约有

2

n

2n

2n个节点，在

O

(

n

)

O(n)

O(n)级

阅读程序

T1

#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;

}

判断-1

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

无法构造出符合条件的

x

x

x

判断-2

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

注意，是输入！有没有人和我一样改返回值类型的

举个例子：x = 32768

原因：x << 6爆了unsigned short而没有爆unsigned int，导致执行完第四行时

x

x

x的值不一样，于是第五行

x

x

x异或的东西也就不一样

判断-3

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

手算即可。

判断-4

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

手算即可。

单选-1

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

A. 33280

B. 33410

C. 33106

D. 33346

手算即可。

单选-2

当输入为 64 时，执行完第

5

5

5 行后 x 的值为（）。

A. 8256

B. 4130

C. 4128

D. 4160

手算即可。

T2

#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;

}

使用“洛谷有题”进行练习的同学们注意了，本题在“洛谷有题”中的题面有误：

代码的第

15

15

15行是reverse(d.begin(), d.end());，而d.push_back(k);与for (int k = i; k <= n; k *= i)在同一行。

判断-1

将第

15

15

15 行删去，输出不变。（✗）

第15行为reverse(d.begin(), d.end());，删去后会导致数组g[]的值发生变化。

如：

不删去第

15

15

15行时g[4]==4删去后g[4]==2

判断-2

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

手算即可。

判断-3

当输入为 1000 时，输出的第一行与第二行相等。（✓）

手算即可。

这题手算显然不现实，我们不妨尝试一下小一些的数据。

输入为1，输出两行都是1输入为2，输出两行都是4输入为3，输出两行都是8

这时我们可以大胆猜测，输出的两行总是相等的

选择-1

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

A.

O

(

n

log

⁡

2

n

)

O(n \log ^2n)

O(nlog2n)

B.

O

(

n

)

O(n)

O(n)

C.

O

(

n

log

⁡

n

)

O(n \log n)

O(nlogn)

D.

O

(

n

log

⁡

log

⁡

n

)

O(n \log \log n)

O(nloglogn)

solve1的主体部分是艾氏筛，时间复杂度为

O

(

n

log

⁡

log

⁡

n

)

O(n \log \log n)

O(nloglogn)，而筛完之后的循环复杂度为

O

(

n

)

O(n)

O(n)，故总复杂度为

O

(

n

log

⁡

log

⁡

n

)

O(n \log \log n)

O(nloglogn)。

相关证明感兴趣的读者可以自行学习。

选择-2

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

A.

O

(

n

2

)

O(n^2)

O(n2)

B.

O

(

n

)

O(n)

O(n)

C.

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn)

D.

O

(

n

n

​

)

O(n\sqrt n​ )

O(nn

​​)

一重

i

∈

1

…

n

i \in 1 \dotsc n

i∈1…n的循环，没什么好说的。

选择-3

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

A. 20

B. 21

C. 22

D. 23

手算即可。

T3

#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;

}

使用“洛谷有题”进行练习的同学们注意了，本题在“洛谷有题”中的题面有误：

代码的第11行为s += i - j;，而j++与while在同一行

判断-1

将第

24

24

24 行的 m 改为 m - 1，输出有可能不变，而剩下情况为少

1

1

1。（✓）

注意 第

24

24

24行是h = m;而非if (f0(a, m, k)) {

若最后一次二分执行的是第

27

27

27行g = m + 1;则答案不变，否则少

1

1

1。

判断-2

将第

22

22

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

g

+

h

−

g

2

=

2

g

+

h

−

g

2

=

h

+

g

2

g+\frac{h-g}{2} = \frac{2g+h-g}{2} = \frac{h+g}{2}

g+2h−g​=22g+h−g​=2h+g​

可以看出，修改前后的算式等价

判断-3

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

手算即可。

选择-1

设

a

a

a 数组中最大值减最小值加

1

1

1 为

A

A

A，则

f

f

f 函数的时间复杂度为（）。

A.

O

(

n

log

⁡

A

)

O(n\log A)

O(nlogA)

B.

O

(

n

2

log

⁡

A

)

O(n^2\log A)

O(n2logA)

C.

O

(

n

log

⁡

(

n

A

)

)

O(n\log (nA))

O(nlog(nA))

D.

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn)

注意到函数

f

f

f有两部分，一个排序，一个二分。其中，排序的复杂度为

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn)，二分的复杂度为

O

(

n

log

⁡

A

)

O(n \log A)

O(nlogA)。

所以总复杂度为

O

(

n

(

log

⁡

n

+

log

⁡

A

)

)

O(n(\log n + \log A))

O(n(logn+logA))，即

O

(

n

log

⁡

(

n

A

)

)

O(n \log (nA))

O(nlog(nA))

选择-2

将第

10

10

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

A. 一定小于

B. 一定小于等于且不一定小于

C. 一定大于等于且不一定大于

D. 以上三种情况都不对

替换后在m一定时，s可能不变或变得更大，而变得更大可能会让本来的

f

a

l

s

e

false

false变成

t

r

u

e

true

true，使答案变得更小。

这里我就偷个懒，不造数据了，不放心的读者可以自行验证。

选择-3

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

A. 13

B. 14

C. 8

D. 15

手算即可。

完善程序

T1

（第

k

k

k 小路径）给定一张

n

n

n 个点

m

m

m 条边的有向无环图，顶点编号从

0

0

0 到

n

−

1

n−1

n−1，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第

k

k

k 小的路径。保证存在至少

k

k

k 条路径。上述参数满足

1

≤

n

,

m

≤

1

0

5

,

1

≤

k

≤

1

0

18

1≤n,m≤10^5,1≤k≤10^{18}

1≤n,m≤105,1≤k≤1018。

在程序中，我们求出从每个点出发的路径数量。超过

1

0

18

10^{18}

1018 的数都用

1

0

18

10^{18}

1018 表示。然后我们根据

k

k

k 的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。

试补全程序。

#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;

}

T1

A. k >= f[u]

B.k <= f[u]

C. k > f[u]

D. k < f[u]

f[u]表示以u为起点的路径数，k表示要求的路径第

k

k

k小，此处若k<=f[u]则说明要求的路径经过顶点u。

T2

A. deg[v] == 1

B. deg[v] == 0

C. deg[v] > 1

D. deg[v] > 0

拓扑排序板子。

若顶点v入度为

0

0

0则将其加入Q中。这里是先判断后删除，所以deg[v] == 1。

T3

A. std::min(f[u] + f[v], LIM)

B. std::min(f[u] + f[v] + 1, LIM)

C. std::min(f[u] * f[v], LIM)

D. std::min(f[u] * (f[v] + 1), LIM)

对于每一个u -> v，以v开头的路径数量之和再加

1

1

1就是以u开头的路径数量。（从u走到v，然后继续往下走，或者只有一个u）

按照拓扑序逆序遍历可以保证遍历到u时已经遍历过了每一个v。

T4

A. u != -1

B. !E[u].empty()

C. k > 0

D. k > 1

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

T5

A. k+=f[u]

B. k-=f[u]

C. --k

D. ++k

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

T2

（最大值之和）给定整数序列

a

0

,

…

,

a

n

−

1

a_0, \dotsc, a_{n-1}

a0​,…,an−1​ ，求该序列所有非空连续子序列的最大值之和。上述参数满足

1

≤

n

≤

1

0

5

1≤n≤10^5

1≤n≤105 和

1

≤

a

i

​

≤

1

0

8

1≤a_i​ ≤10^8

1≤ai​​≤108 。

一个序列的非空连续子序列可以用两个下标

l

l

l 和

r

r

r（其中

0

≤

l

≤

r

<

n

0≤l≤r<n

0≤l≤r<n）表示，对应的序列为

a

l

,

a

l

+

1

,

…

,

a

r

a_l,a_{l+1},\dotsc,a_r

al​,al+1​,…,ar​ 。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为

[

1

,

2

,

1

,

2

]

[1,2,1,2]

[1,2,1,2] 时，要计算子序列

[

1

]

[1]

[1]、

[

2

]

[2]

[2]、

[

1

]

[1]

[1]、

[

2

]

[2]

[2]、

[

1

,

2

]

[1,2]

[1,2]、

[

2

,

1

]

[2,1]

[2,1]、

[

1

,

2

]

[1,2]

[1,2]、

[

1

,

2

,

1

]

[1,2,1]

[1,2,1]、

[

2

,

1

,

2

]

[2,1,2]

[2,1,2]、

[

1

,

2

,

1

,

2

]

[1,2,1,2]

[1,2,1,2] 的最大值之和，答案为

18

18

18。注意

[

1

,

1

]

[1,1]

[1,1] 和

[

2

,

2

]

[2,2]

[2,2] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

解决该问题有许多算法，以下程序使用分治算法，时间复杂度

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn)。

试补全程序。

#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 - l, 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

)

[l,r)

[l,r)主要做了以下几件事：

求出区间的中点

m

i

d

mid

mid统计左端点再

m

i

d

mid

mid左边，且右端点在

m

i

d

mid

mid右边的区间最大值之和分别递归下降到

[

l

,

m

i

d

)

[l,mid)

[l,mid)和

[

m

i

d

,

r

)

[mid,r)

[mid,r)

如果能想明白这些，尤其是第二条，这题就好做多了.

T1

A. pre[i] = std::max(pre[i - 1], a[i - 1])

B. pre[i + 1] = std::max(pre[i],pre[i + 1])

C. pre[i] = std::max(pre[i -1], a[i])

D. pre[i] = std::max(pre[i], pre[i - 1])

此处用于求区间

[

m

i

d

,

r

)

[mid,r)

[mid,r)的前缀最大值。

T2

A. a[j] < max

B. a[j] < a[i]

C. pre[j - mid] < max

D. pre[j - mid] > max

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

T3

A. (long long)(j - mid) * max

B. (long long)(j - mid) * (i - 1) * max

C. sum[j - mid]

D. sum[j - mid] * (i - 1)

表示左端点为

i

i

i，右端点为

m

i

d

,

…

,

j

−

1

mid,\dotsc,j-1

mid,…,j−1中任意一点，最大值皆为max，共j-mid个。

T4

A. (long long)(r - j) * max

B. (long long)(r - j) * (mid - i) * max

C. sum[r - mid] - sum[j - mid]

D. (sum[r - mid] - sum[j - mid]) * (mid - i)

表示左端点为i，右端点在

j

,

…

,

r

−

1

j, \dotsc, r-1

j,…,r−1中 的区间的最大值之和。

T5

A. solve(0，n)

B. solve(0，n - 1)

C. solve(1，n)

D. solve(1，n - 1)

本题代码采用左闭右开，故区间是

[

0

,

n

)

[0,n)

[0,n)。

尾声

一年多没更新了，终于找到机会写了一篇题解。

如有写的不好的地方欢迎提出意见。