5、下面是使用邻接矩阵实现的 Dijkstra 算法的核心片段，用于求单源最短路径。在找到当前距离起点最近的顶点 u 后，需要更新其邻接点 j 的距离。横线处应填入的代码是（）。
for (int j = 1; j <= n; j++) {
if (!visited[j] && graph[u][j] < INF) {
if (________) {// 在此处填入选项
dis[j] = dis[u] + graph[u][j];
}
}
}
A. dis[j] < dis[u] + graph[u][j]B. dis[j] > dis[u] + graph[u][j]
C. graph[u][j] > dis[u] + dis[j]
D. dis[j] > graph[u][j]
正确答案：B
6、下面程序使用动态规划求两个字符串的最长公共子序列（LCS）长度，横线处应填入的是（）。
#include<algorithm>#include<string>#include<vector>usingnamespace std;
intlcs_len(const string &a, const string &b){
int n = (int)a.size(), m = (int)b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else ________;// 在此处填入选项return dp[n][m];
}
A. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
B. dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
C. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
D. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;
正确答案：C
7、已知两个点和 在平面直角坐标系中的坐标。下列 C++ 表达式中，能正确计算这两点之间直线距离的是（）。
A. sqrt((x1 - x2)^2 + (y1 - y2)^2)
B. sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))
C. pow(x1 - x2, 2) + pow(y1 - y2, 2)
D. abs(x1 - x2) + abs(y1 - y2)
正确答案：B
8、已知 int a = 10; ，执行 int &b = a; b = 20; 后，变量 a 的值是（）。
A. 10B. 20 C. 30 D. 编译错误
正确答案：B
9、下列代码的时间复杂度（以 n 为自变量，忽略常数与低阶项）是（）。
longlong s = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
s += j;
}
}
A. B. C. D.
正确答案：无
10、下列程序实现了线性筛法（欧拉筛），用于在 O(n) 时间内求出 n 之间的所有质数。为了保证每个合数只被其最小质因子筛掉，横线处应填入的语句是（）。
for (int i = 2; i <= n; i++) {
if (!not_prime[i]) primes[++cnt] = i;
for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
not_prime[i * primes[j]] = true;
if (________) break;// 在此处填入选项
}
}
A. i + primes[j] == n
B. primes[j] > i
C. i % primes[j] == 0
D. i % primes[j] != 0
正确答案：C
11、在 C++ 语言中，关于类的继承和访问权限，下列说法正确的是（）。
A. 派生类可以访问基类的 private 成员。
B. 基类的 protected 成员在私有继承（private inheritance）后，在派生类中变为 public。
C. 派生类对象在创建时，会先调用基类的构造函数，再调用派生类自己的构造函数。
D. 派生类对象在销毁时，会先调用基类的析构函数，再调用派生类自己的析构函数。
【问题描述】
猫和老鼠所在的庄园可以视为一张由 n 个点和 m 条带权无向边构成的连通图。结点依次以 1 编号，结点 i（1 ≤ i ≤ n）有价值为 c_i 的奶酪。在 m 条带权无向边中，第 k（1 ≤ k ≤ m）条无向边连接结点 u_k 与结点 v_k，边权 w_k 表示猫和老鼠通过这条边所需的时间。
猫窝位于结点 a，老鼠洞位于结点 b。对于老鼠而言，结点 i 是安全的当且仅当：
老鼠能规划一条从结点 i 出发逃往老鼠洞的路径，使得对于路径上任意结点 x（包括结点 i 与老鼠洞）都有：dist_cat[x] > dist_mouse[x]。
猫从猫窝出发到结点 x 的最短时间严格大于老鼠从结点 i 沿这条路径前往结点 x 所需的时间。
老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。
【输入格式】
第一行，两个正整数 n, m，分别表示图的结点数与边数。
第二行，两个正整数 a, b，分别表示猫窝的结点编号，以及老鼠洞的结点编号。
第三行，n 个正整数 c_1, c_2, ..., c_n，表示各个结点的奶酪价值。
接下来 m 行中的第 k 行（1 ≤ k ≤ m）包含三个正整数 u_k, v_k, w_k，表示图中连接结点 u_k 与结点 v_k 的边，边权为 w_k。
【数据范围】
对于 30% 的测试点，保证 n ≤ 100。
对于所有测试点，保证 1 ≤ n ≤ 10^5, 1 ≤ m ≤ 2*10^5, 1 ≤ a, b ≤ n, 1 ≤ w_k ≤ 10^9。
【参考程序】
#include<cstdio>#include<algorithm>#include<vector>#include<queue>usingnamespace std;
constint N = 1e5 + 5;
constlonglong oo = 1e18;
int n, m;
int a, b;
int c[N];
vector<pair<int, int>> e[N];
longlong dis[N];
priority_queue<pair<longlong, int>, vector<pair<longlong, int>>, greater<pair<longlong, int>>> q;
longlong ans;
intmain(){
scanf("%d%d", &n, &m);
scanf("%d%d", &a, &b);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back({v, w});
e[v].emplace_back({u, w});
}
for (int i = 1; i <= n; i++) dis[i] = oo;
dis[b] = 0;
q.push({-dis[b], b});
while (!q.empty()) {
auto p = q.top();
q.pop();
if (dis[p.second] != -p.first) continue;
int u = p.second;
for (auto r : e[u]) {
int v = r.first, w = r.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({-dis[v], v});
}
}
}
for (int i = 1; i <= n; i++)
if (dis[i] < dis[a]) ans += c[i];
printf("%lld\n", ans);
return0;
}
3.2 编程题 2 宝石项链
【问题描述】
小 A 有一串包含 n 枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以 1 编号，第 i 枚宝石与第 i+1 枚宝石相邻（第 n 枚与第 1 枚相邻）。项链由 m 种宝石组成，其中第 i 枚宝石种类为 t_i。
小 A 想将宝石项链分给他的好朋友们。具体而言，小 A 会将项链划分为若干连续段，并且需要保证每段都包含全部 m 种宝石。请帮小 A 计算在满足条件的前提下，宝石项链最多可以划分为多少段。
【输入格式】
第一行，两个正整数 n, m，分别表示宝石项链中的宝石的数量与种类数。
第二行，n 个正整数 t_1, t_2, ..., t_n，表示每枚宝石的种类。
【输出格式】
输出一行，一个整数，表示宝石项链最多可以划分的段数。
【样例输入 1】
6 2
1 2 1 2 1 2
【样例输出 1】
2
【样例输入 2】
7 3
3 1 3 1 2 1 2
【样例输出 2】
2
【数据范围】
对于 30% 的测试点，保证 n ≤ 100。
对于所有测试点，保证 1 ≤ n ≤ 2*10^5, 1 ≤ m ≤ n, 1 ≤ t_i ≤ m，保证 m 均在 t 中出现。
【参考程序】
#include<cstdio>#include<algorithm>usingnamespace std;
constint L = 20;
constint N = 2e5 + 5;
constint oo = 1e9;
int n, m;
int t[N], jump[L][N];
int cnt[N], tot;
int ans;
intgo(int u){
int cnt = 0, ans = 0;
for (int i = L - 1; i >= 0; i--)
if (cnt + jump[i][u] <= n) {
cnt += jump[i][u];
ans += 1 << i;
u = (u + jump[i][u] - 1) % n + 1;
}
return ans;
}
intmain(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
t[i + n] = t[i];
}
for (int i = 1, r = 0; i <= n; i++) {
while (tot < m) {
r++;
if (!cnt[t[r]]++) tot++;
}
jump[0][i] = r - i + 1;
if (--cnt[t[i]]) tot--;
}
for (int i = 1; i < L; i++)
for (int j = 1; j <= n; j++) {
int tar = (j + jump[i - 1][j] - 1) % n + 1;
jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
}
for (int i = 1; i <= n; i++) ans = max(ans, go(i));
printf("%d\n", ans);
return0;
}
