01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 bool flag[27];
05 int n;
06 int p[27];
07 int ans = 0;
08 void dfs(int k) {
09 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
24 int main() {
25 scanf("%d", &n);
26 dfs(1);
27 printf("%d\n", ans);
28 return 0;
}
01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #include <vector>
05 #define ll long long
06 int n, m;
07 std::vector k, p;
08
09 inline int mpow(int x, int k) {
10 int ans = 1;
11 for (; k; k = k >> 1, x = x * x) {
12 if (k & 1)
13 ans = ans * x;
14 }
15 return ans;
16 }
17 std::vector ans1, ans2;
18 int cnt1, cnt2;
19
20 inline void dfs(std::vector& ans, int& cnt, int l, int r, int v) {
21 if (l > r) {
22 ++cnt;
23 ans.push_back(v);
24 return;
25 }
26 for (int i = 1; i <= m; ++i) {
27 dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
28 }
29 return;
30 }
31
32 std::vector cntans1;
33 int main() {
34 scanf("%d%d", &n, &m);
35 k.resize(n + 1);
36 p.resize(n + 1);
37 for (int i = 1; i <= n; ++i) {
38 scanf("%d%d", &k[i], &p[i]);
39 }
40 dfs(ans1, cnt1, 1, n >> 1, 0);
41 dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
42
43 std::sort(ans1.begin(), ans1.end());
44 int newcnt1 = 1;
45 cntans1.push_back(1);
46 for (int i = 1; i < cnt1; ++i) {
47 if (ans1[i] == ans1[newcnt1 - 1]) {
48 ++cntans1[newcnt1 - 1];
49 } else {
50 ans1[newcnt1++] = ans1[i];
51 cntans1.push_back(1);
52 }
53 }
54 cnt1 = newcnt1;
55 std::sort(ans2.begin(), ans2.end());
56
57 int las = 0;
58 ll ans = 0;
59 for (int i = cnt2 - 1; i >= 0; --i) {
60 for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las);
61 if (las < cnt1 && ans1[las] + ans2[i] == 0)
62 ans += cntans1[las];
63 }
64 printf("%lld\n", ans);
65 return 0;
}
给定一个含 N 个点、M 条边的带权无向图，边权非负。起点为 S，终点为 T。对于一条 S 到 T 的路径，可以在整条路径中，至多选择一条边作为“免费边”：当第一次经过这条被选中的边时，费用视为0；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 S 到 T 的最小总费用。以下代码求解了上述问题，试补全程序。
01 #include <algorithm>
02 #include <iostream>
03 #include <queue>
04 #include <vector>
05 using namespace std;
06
07 const long long INF = 1e18;
08
09 struct Edge {
10 int to;
11 int weight;
12 };
13
14 struct State {
15 long long dist;
16 int u;
17 int used_freebie; // 0 for not used, 1 for used
18 bool operator>(const State &other) const {
19 return dist > other.dist;
20 }
21 };
22
23 int main() {
24 int n, m, s, t;
25 cin >> n >> m >> s >> t;
26
27 vector> adj(n + 1);
28 for (int i = 0; i < m; ++i) {
29 int u, v, w;
30 cin >> u >> v >> w;
31 adj[u].push_back({v, w});
32 adj[v].push_back({u, w});
33 }
34
35 vector> d(n + 1, vector(2, INF));
36 priority_queue, greater> pq;
37 d[s][0] = 0;
38 pq.push({0, s, ①});
39
40 while (!pq.empty()) {
41 State current = pq.top();
42 pq.pop();
43
44 long long dist = current.dist;
45 int u = current.u;
46 int used = current.used_freebie;
47
48 if (dist > ②) {
49 continue;
50 }
51
52 for (const auto &edge : adj[u]) {
53 int v = edge.to;
54 int w = edge.weight;
55
56 // 不使用免费边的情况
57 if (d[u][used] + w < ③) {
58 ③ = d[u][used] + w;
59 pq.push({③, v, used});
60 }
61
62 // 使用免费边的情况（仅当未使用过免费边时）
63 if (used == 0) {
64 if (④ < d[v][1]) {
65 d[v][1] = ④;
66 pq.push({d[v][1], v, 1});
67 }
68 }
69 }
70 }
71
72 cout << ⑤ << endl;
73 return 0;
}
工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n条生产线（编号0~n-1），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为1），否则正常收货（结果记为0）。受售后压力限制，在所有发货批次中，最多只能有k次退货（即结果为1的次数 ≤k）。工厂的目标是，设计最少的间接测试轮数 w（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。以下程序实现了工厂的目标，包含两部分：i) 确定 w 的最小值，并设计最优测试方案；ii) 根据测试结果推断存在缺陷的生产线。该程序确定 w 最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此 w 轮测试的可能结果数不应少于生产线数量。test_subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。试补全程序。
01 #include <algorithm>
02 #include <cstddef>
03 #include <iostream>
04 #include <vector>
05 using namespace std;
06
07 long long comb(int w, int i) {
08 if (i < 0 || i > w) {
09 return 0;
10 }
11 long long res = 1;
12 for (int t = 1; t <= i; ++t) {
13 res = res * (w - t + 1) / t;
14 }
15 return res;
16 }
17
18 // 计算长度为 w、1 的个数≤k的码字总数
19 long long count_patterns(int w, int k) {
20 long long total = 0;
21 for (int t = 0; t <= min(w, k); ++t) {
22 total += comb(w, t);
23 }
24 return total;
25 }
26
27 // 抽象测试接口
28 int test_subset(const vector> &plan);
29
30 int solve(int n, int k) {
31 // === 第1步：求最小w ===
32 int w = 1;
33 while (①) {
34 ++w;
35 }
36 cout << w << endl;
37
38 // === 第2步：生成测试方案 ===
39 vector> code(n, vector(w, 0));
40 int idx = 0;
41 for (int ones = 0; ones <= k && idx < n; ++ones) {
42 vector bits(w, 0);
43 fill(bits.begin(), bits.begin() + ones, 1);
44 do {
45 for (int b = 0; b < w; ++b) {
46 code[idx][b] = bits[b];
47 }
48 ++idx;
49 if (idx >= n) {
50 break;
51 }
52 } while (std::②);
53 }
54
55 // === 第3步：构造批次方案 ===
56 vector> plan(w);
57 for (int i = 0; i < w; ++i) {
58 for (int j = 0; j < n; ++j) {
59 if (③) {
60 plan[i].push_back(j);
61 }
62 }
63 }
64
65 // === 第4步：调用测试接口 ===
66 int signature = test_subset(plan);
67
68 // === 第5步：结果解码 ===
69 vector sig_bits(w, 0);
70 for (int i = 0; i < w; ++i) {
71 if (④) {
72 sig_bits[i] = 1;
73 }
74 }
75
76 for (int j = 0; j < n; ++j) {
77 if (⑤) {
78 return j;
79 }
80 }
81 }
82
83 int main() {
84 int n, k;
85 cin >> n >> k;
86 int ans = solve(n, k);
87 cout << ans << endl;
88 return 0;
}