2025 CCF CSP-S 第一轮（提高级 C++）

 1 | #include <algorithm>
 2 | #include <cstdio>
 3 | #include <cstring>
 4 | bool flag[27];
 5 | int n;
 6 | int p[27];
 7 | int ans = 0;
 8 | void dfs(int k) {
 9 |     if (k == n + 1){
10 |         ++ ans;
11 |         return;
12 |     }
13 |     for (int i = 1; i <= n; ++i) {
14 |         if (flag[i]) continue;
15 |         if (k > 1 && i == p[k - 1] + 1) continue;
16 |         p[k] = i;
17 |         flag[i] = true;
18 |         dfs(k + 1);
19 |         flag[i] = false;
20 |     }
21 |     return;
22 | }
23 | int main() {
24 |     scanf("%d", &n);
25 |     dfs(1);
26 |     printf("%d\n", ans);
27 |     return 0;
28 | }

 1 | #include <algorithm>
 2 | #include <cstdio>
 3 | #include <cstring>
 4 | #define ll long long
 5 | int cnt_broken = 0;
 6 | int cnt_check = 0;
 7 | int n, k;
 8 | inline bool check(int h) {
 9 |     printf("now check:%d\n", h);
10 |     ++cnt_check;
11 |     if (cnt_broken == 2) {
12 |         printf("You have no egg!\n");
13 |         return false;
14 |     }
15 |     if (h >= k) {
16 |         ++cnt_broken;
17 |         return true;
18 |     } else {
19 |         return false;
20 |     }
21 | }
22 | inline bool assert_ans(int h) {
23 |     if (h == k) {
24 |         printf("You are Right using %d checks\n", cnt_check);
25 |         return true;
26 |     } else {
27 |         printf("Wrong answer!\n");
28 |         return false;
29 |     }
30 | }
31 | inline void guess1(int n) {
32 |     for (int i = 1; i <= n; ++i) {
33 |         if (check(i)) {
34 |             assert_ans(i);
35 |             return;
36 |         }
37 |     }
38 | }
39 | inline void guess2(int n) {
40 |     int w = 0;
41 |     for (w = 1; w * (w + 1) / 2 < n; ++w)
42 |         ;
43 |     for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
44 |         if (check(nh)) {
45 |             for (int j = nh - ti + 1; j < nh; ++j) {
46 |                 if (check(j)) {
47 |                     assert_ans(j);
48 |                     return;
49 |                 }
50 |             }
51 |             assert_ans(nh);
52 |             return;
53 |         }
54 |     }
55 | }
56 | int main() {
57 |     scanf("%d%d", &n, &k);
58 |     int t;
59 |     scanf("%d", &t);
60 |     if (t == 1) {
61 |         guess1(n);
62 |     } else {
63 |         guess2(n);
64 |     }
65 |     return 0;
66 | }

> (注意：下述的"猜测数"为调用 check 函数的次数 (即 cnt_check 的值)；"猜测正确"的含义为 assert_ans 函数 return true (执行第 25 行所在分支)的情况；所有输入保证 1 ≤ k ≤ n。)

 1 | #include <algorithm>
 2 | #include <cstdio>
 3 | #include <cstring>
 4 | #include <vector>
 5 | #define ll long long
 6 | int n, m;
 7 | std::vector<int> k, p;
 8 | std::vector<int> ans1, ans2;
 9 | int cnt1, cnt2;
10 | inline int mpow(int x, int k) {
11 |     int ans = 1;
12 |     for (; k; k >>= 1, x = x * x) {
13 |         if (k & 1)
14 |             ans = ans * x;
15 |     }
16 |     return ans;
17 | }
18 | inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
19 |     if (l > r) {
20 |         ++cnt;
21 |         ans.push_back(v);
22 |         return;
23 |     }
24 |     for (int i = 1; i <= m; ++i) {
25 |         dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
26 |     }
27 |     return;
28 | }
29 | std::vector<int> cntans1;
30 | int main() {
31 |     scanf("%d%d", &n, &m);
32 |     k.resize(n + 1);
33 |     p.resize(n + 1);
34 |     for (int i = 1; i <= n; ++i) {
35 |         scanf("%d%d", &k[i], &p[i]);
36 |     }
37 |     dfs(ans1, cnt1, 1, n >> 1, 0);
38 |     dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
39 |     std::sort(ans1.begin(), ans1.end());
40 |     int newcnt1 = 1;
41 |     cntans1.push_back(1);
42 |     for (int i = 1; i < cnt1; ++i) {
43 |         if (ans1[i] == ans1[newcnt1 - 1]) {
44 |             ++cntans1[newcnt1 - 1];
45 |         } else {
46 |             ans1[newcnt1++] = ans1[i];
47 |             cntans1.push_back(1);
48 |         }
49 |     }
50 |     cnt1 = newcnt1;
51 |     std::sort(ans2.begin(), ans2.end());
52 |     int las = 0;
53 |     ll ans = 0;
54 |     for (int i = cnt2 - 1; i >= 0; --i) {
55 |         for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
56 |             ;
57 |         if (las < cnt1 && ans1[las] + ans2[i] == 0) {
58 |             ans += cntans1[las];
59 |         }
60 |     }
61 |     printf("%lld\n", ans);
62 |     return 0;
63 | }

1. （特殊最短路）给定一个含 N 个点 M 条边的带权无向图，边权非负。起点为 S，终点为 T。对于一条 S 到 T 的路径，可以在整条路径中，至多选择一条边作为"免费边"；当第一次经过这条被选中的边时，费用视为 0；如果之后再次经过该边，则仍按其原始权重计费。点和边均可重复经过。求从 S 到 T 的最小总费用。 以下代码求解了上述问题，试补全程序。

#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({d[v][used], v, used});
            }

            if (used == 0) {
                if (④ < d[v][1]) {
                    d[v][1] = ④;
                    pq.push({d[v][1], v, 1});
                }
            }
        }
    }

    cout << ⑤ << endl;
    return 0;
}

2. 工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有 n 条生产线（编号 0~n−1），已知其中有一个生产线存在缺陷。每一轮测试为：从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要发送货（结果应为 1），否则正常收货（记为 0）。受售后压力限制，在所有发货批次中，最多只能有 k 次退货（即结果为 1 的次数 ≤k）。工厂的目标是，设计最少的间接测试数 w（发货总批次），保证根据客户收到或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分：

i) 确定 w 的最小值，并设计最优测试方案； ii) 根据测试结果推断存在缺陷的生产线。该程序确定 w 最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此 w 较测试的可能性系数不应少于生产线数量。

`test_subset()` 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位第 1 批次、最高位第 w 批次）；其实现在此处未给出。

试补全程序。

**程序代码**

#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 (②);
    }

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