Day8 CSP-J1 全真模拟①（重制版）·阅读程序

共 3 个完整程序组、17 个小问，满分 40 分。判断题正确填 A，错误填 B。

第一组：BFS 最短距离与最短路径条数

---

程序一

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dist(n + 1, -1), ways(n + 1, 0);
    queue<int> q;
    dist[1] = 0;
    ways[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                ways[v] = ways[u];
                q.push(v);
            } else if (dist[v] == dist[u] + 1) {
                ways[v] += ways[u];
            }
        }
    }
    cout << dist[6] << " " << ways[6] << " "
         << dist[7] << " " << ways[7];
    return 0;
}

第 16 题

输入为：

7 9
1 2
1 3
2 4
3 4
3 5
4 6
5 6
6 7
5 7

顶点 4 的 dist 为 2（ {{ input(16) }} ）。

---

第 17 题

对上述输入，顶点 4 的 ways 为 2（ {{ input(17) }} ）。

---

第 18 题

仅改变各邻接表中邻居的排列顺序，可能改变程序得到的最短距离（ {{ input(18) }} ）。

---

第 19 题

对上述输入，程序输出（ {{ select(19) }} ）。

• 2 2 3 1
• 3 2 2 1
• 3 3 3 1
• 3 3 4 3

---

第 20 题

把顶点标记推迟到出队时才进行，最可能造成（ {{ select(20) }} ）。

• 所有距离变为 $-1$
• 同一顶点被重复加入队列
• 图自动变为有向图
• 队列始终为空

---

第 21 题

使用邻接表时，程序的时间复杂度是（ {{ select(21) }} ）。

• $O(1)$
• $O(n)$
• $O(n^2)$
• $O(n+m)$

---

第二组：一维 0/1 背包

---

程序二

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int w, v;
        cin >> w >> v;
        for (int j = W; j >= w; --j)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[W] << " " << dp[5];
    return 0;
}

第 22 题

dp[j] 表示总重量必须恰好等于 $j$ 时的最大价值（ {{ input(22) }} ）。

---

第 23 题

容量从大到小枚举，可以防止当前物品在同一轮被重复使用（ {{ input(23) }} ）。

---

第 24 题

输入为：

5 8
2 3
3 4
4 7
5 8
6 9

程序输出（ {{ select(24) }} ）。

• 12 8
• 12 7
• 11 8
• 14 9

---

第 25 题

若容量循环改为从小到大，程序可能把问题错误地变成（ {{ select(25) }} ）。

• 每件物品都必须选择
• 物品完全不能选择
• 只能选择最后一件物品
• 同一件物品可以选择多次

---

第 26 题

程序关于 $n,W$ 的时间复杂度是（ {{ select(26) }} ）。

• $O(n+W)$
• $O(2^n)$
• $O(nW)$
• $O(W\log n)$

---

第三组：统计恰有两个不同质因数的整数

---

程序三

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> cnt(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        if (cnt[i] == 0) {
            for (int j = i; j <= n; j += i)
                ++cnt[j];
        }
    }

    int ans = 0;
    for (int i = 2; i <= n; ++i)
        if (cnt[i] == 2) ++ans;
    cout << ans;
    return 0;
}

第 27 题

程序不会把整数 1 计入答案（ {{ input(27) }} ）。

---

第 28 题

程序结束后，每个质数 $p$ 都满足 cnt[p]==0（ {{ input(28) }} ）。

---

第 29 题

程序结束后，cnt[12] 的值为 3（ {{ input(29) }} ）。

---

第 30 题

输入 20 时，程序输出（ {{ select(30) }} ）。

• $6$
• $7$
• $8$
• $9$

---

第 31 题

若把内层循环初值改为 i*i，最可能造成（ {{ select(31) }} ）。

• 遗漏一部分质因数标记，答案可能错误
• 结果不变且一定更快
• 所有合数的计数都加倍
• 程序发生数组越界

---

第 32 题

程序的时间复杂度最合适的估计是（ {{ select(32) }} ）。

• $O(1)$
• $O(2^n)$
• $O(n^2)$
• $O(n\log\log n)$

---