选 单项选择题（共 15 题，共 0 分）
有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？
在 KMP 算法中，对于模式串 $P=$abacaba，其 next 数组（next[i] 定义为模式串 P[O...i]
最长公共前后缀的长度，且数组下标从 0 开始）的值是什么？（）
对一个大小为 $16$（下标 0-15）的数组上构建满线段树。查询区间 $[3，11]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？（）
将字符串 cat，car，cart，case，dog，do 插入一个空的 Trie 树（前缀树）中。构建完成的 Trie 树（包括根结点）共有多少个结点？
对于一个包含 $n$ 个顶点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？（)
在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $\text{H}(key)=key \mod 13$。依次插入关键字 $18$，$26$，$35$，$9$，$68$，$74$。插入 $74 $后，它最终被放置在哪个索引位置？
一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到$8$），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为 $|7 - 3|=4$。该图的最小生成树的总权重是多少？
如果一棵二叉搜索树的后序遍历序列是 $2$，$5$，$4$，$8$，$12$，$10$，$6$，那么该树的前序遍历序列是什么？（)
一个 0-1 背包问题，背包容量为 $20$。现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15,12,9,7,13$。装入背包的物品能获得的最大总价值是多少？（）
在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（LCA）是结点 $4$。那么下列哪个结点的 LCA 组合是不可能出现的？
递归关系式 $\text{T}(n）=2\text{T}(n/2) + \mathcal{O}(n^2）$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？
在一个初始为空的最小堆（min-heap）中，依次插入元素 $20,12,15,8,10,5$。然后连续执行两次“删除最小值”(delete-min）操作。请问此时堆顶元素是什么？()
$1$ 到 $1000$ 之间，不能被 $2$、$3$、$5$ 中任意一个数整除的整数有多少个？（ ）
斐波那契数列的定义为 $F(0)=0$，$F(1)=1$，$F(n)=F(n-1)+F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的。而使用动态规划(或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？
有 $5$ 个独立的、不可抢占的任务 A1，A2，A3，A4，A5 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3,4,2,5,1$ 和 $5,10,3,15,11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？
阅 阅读程序（共 18 题，共 0 分）
#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
if (k == n + 1) {
++ans;
return;
}
for (int i = 1; i <= n; ++i) {
if (flag[i]) continue;
if (k > 1 && i == p[k - 1] + 1) continue;
p[k] = i;
flag[i] = true;
dfs(k + 1);
flag[i] = false;
}
return;
}
int main() {
scanf("%d", &n);
dfs(1);
printf("%d\n", ans);
return 0;
}
当输入的 $n=$ 3 的时候，程序输出的答案为 3。()
在 dfs 函数运行过程中，k 的取值会满足 $1\leq k\leq n+1$。()
删除第19行的 flag[i] = false;，对答案不会产生影响。()
当输入的 $n=$4的时候，程序输出的答案为()。
如果因为某些问题,导致程序运行第 25 行的 dfs 函数之前，数组 p 的初值并不全为 $0$，则对程序的影响是()。
假如删去第 14 行的 if (flag[i]) continue;，输入 3，得到的输出答案是()。
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
printf("now check:%d\n", h);
++cnt_check;
if (cnt_broken == 2) {
printf("You have no egg!\n");
return false;
}
if (h >= k) {
++cnt_broken;
return true;
} else {
return false;
}
}
inline bool assert_ans(int h) {
if (h == k) {
printf("You are Right using %d checks\n", cnt_check);
return true;
} else {
printf("Wrong answer!\n");
return false;
}
}
inline void guess1(int n) {
for (int i = 1; i <= n; ++i) {
if (check(i)) {
assert_ans(i);
return;
}
}
}
inline void guess2(int n) {
int w = 0;
for (w = 1; w * (w + 1) / 2 < n; ++w);
for (int ti = w, nh = w; ti > 0; --ti, nh += ti) {
nh = std::min(nh, n);
if (check(nh)) {
for (int j = nh - ti + 1; j < nh; ++j) {
if (check(j)) {
assert_ans(j);
return;
}
}
assert_ans(nh);
return;
}
}
}
int main() {
scanf("%d%d", &n, &k);
int t;
scanf("%d", &t);
if (t == 1) {
guess1(n);
} else {
guess2(n);
}
return 0;
}
当输入为 6 5 1 时，猜测次数为 $5$；当输入 6 5 2 时，猜测次数为 $3$。()
不管输入的 $n$ 和 $k$ 具体为多少，$t=2$ 时的猜测数总是小于等于 $t=1$ 时的猜测数。()
不管 $t=1$ 或 $t=2$，程序都一定会猜到正确结果。( )
函数 guess1 在运行过程中，cnt_broken 的值最多为()。
函数 guess2 在运行过程中，最多使用的猜测次数的量级为()。
当输入的 $n=$100 的时候，代码中 $t=1$ 和 $t=2$ 分别需要的猜测次数最多分别为()。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
int ans = 1;
for (; k; k = k >> 1, x = x * x) {
if (k & 1)
ans = ans * x;
}
return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
if (l > r) {
++cnt;
ans.push_back(v);
return;
}
for (int i = 1; i <= m; ++i) {
dfs(ans, cnt, l + 1, r, v + k[l] * mpow(m, p[l]));
}
return;
}
std::vector<int> cntans1;
int main() {
scanf("%d%d", &n, &m);
k.resize(n + 1);
p.resize(n + 1);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &k[i], &p[i]);
}
dfs(ans1, cnt1, 1, n >> 1, 0);
dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
std::sort(ans1.begin(), ans1.end());
int newcnt1 = 1;
cntans1.push_back(1);
for (int i = 1; i < cnt1; ++i) {
if (ans1[i] == ans1[newcnt1 - 1]) {
++cntans1[newcnt1 - 1];
} else {
ans1[newcnt1++] = ans1[i];
cntans1.push_back(1);
}
}
cnt1 = newcnt1;
std::sort(ans2.begin(), ans2.end());
int las = 0;
ll res = 0;
for (int i = cnt2 - 1; i >= 0; --i) {
for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
;
if (las < cnt1 && ans1[las] + ans2[i] == 0)
ans += cntans1[las];
}
printf("%lld\n", res);
return 0;
}
删除第 51 行的 std::sort(ans2. begin(), ans2.end()); 后,代码输出的结果不会受到影响。()
假设计算过程中不发生溢出，函数 mpow(x,k) 的功能是求出 $x^k$ 的取值。()
代码中第 39 行到第 50 行的目的是为了将 ans1 数组进行“去重”操作。()
当输入为 3 15 12 -1 2 1 2 时，输出结果为()。
记程序结束前 $p$ 数组元素的最大值为 $P$，则该代码的时间复杂度是()。
本题所求出的是( )。
完 完善程序（共 10 题，共 0 分）
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const long long INF = 1e18;
struct Edge {
int to;
int weight;
};
struct State {
long long dist;
int u;
int used_freebie; // 0 for not used, 1 for used
bool operator>(const State &other) const {
return dist > other.dist;
}
};
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
vector<vector<Edge>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
priority_queue<State, vector<State>, greater<State>> pq;
d[s][0] = 0;
pq.push({0, s, ①});
while (!pq.empty()) {
State current = pq.top();
pq.pop();
long long dist = current.dist;
int u = current.u;
int used = current.used_freebie;
if (dist > ②) {
continue;
}
for (const auto &edge : adj[u]) {
int v = edge.to;
int w = edge.weight;
if (d[u][used] + w < ③) {
③ = d[u][used]+ w;
pq.push({③, v, used});
}
if (used == 0) {
if (④ < d[v][1]) {
d[v][1] = ④;
pq.push({d[v][1], v, 1});
}
}
}
}
cout << ⑤ << endl;
return 0;
}
①处应填()
②处应填()
③ 处应填()
④处应填()
⑤处应填()
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
long long comb(int w, int i) {
if (i < 0 || i > w) {
return 0;
}
long long res = 1;
for (int t = 1; t <= i; ++t) {
res = res * (w - t + 1) / t;
}
return res;
}
// 计算长度为w、1的个数≤k的码字总数
long long count_patterns(int w, int k) {
long long total = 0;
for (int t = 0; t <= min(w, k); ++t) {
total += comb(w, t);
}
return total;
}
// 抽象测试接口
int test_subset(const vector<vector<int>> &plan);
int solve(int n, int k) {
// === 第1步：求最小w ===
int w = 1;
while (①) {
++w;
}
cout << w << endl;
// === 第2步：生成测试方案 ===
vector<vector<int>> code(n, vector<int>(w, 0));
int idx = 0;
for (int ones = 0; ones <= k && idx < n; ++ones) {
vector<int> bits(w, 0);
fill(bits.begin(), bits.begin() + ones, 1);
do {
for (int b = 0; b < w; ++b) {
code[idx][b] = bits[b];
}
++idx;
if (idx >= n) {
break;
}
} while (std::②);
}
vector<vector<int>> plan(w);
for (int i = 0; i < w; ++i) {
for (int j = 0; j < n; ++j) {
if (③) {
plan[i].push_back(j);
}
}
}
// === 第3步：调用测试接口 ===
int signature = test_subset(plan);
// === 第4步：结果解码 ===
vector<int> sig_bits(w, 0);
for (int i = 0; i < w; ++i) {
if (④) {
sig_bits[i] = 1;
}
}
for (int j = 0; j < n; ++j) {
if (⑤) return j;
}
}
int main() {
int n, k;
cin >> n >> k;
int ans = solve(n, k);
cout << ans << endl;
return 0;
}
①处应填()
②处应填()
③处应填()
④处应填()
⑤处应填()