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

 1 | #include <iostream>
 2 | using namespace std;
 3 |
 4 | const int N = 1000;
 5 | int c[N];
 6 |
 7 | int logic(int x, int y) {
 8 |     return (x & y) ^ ((x ^ y) | (~x & y));
 9 | }
10 |
11 | void generate(int a, int b, int *c) {
12 |     for (int i = 0; i < b; i++) {
13 |         c[i] = logic(a, i) % (b + 1);
14 |     }
15 | }
16 |
17 | void recursion(int depth, int *arr, int size) {
18 |     if (depth <= 0 || size <= 1) return;
19 |     int pivot = arr[0];
20 |     int i = 0, j = size - 1;
21 |     while (i <= j) {
22 |         while (arr[i] < pivot) i++;
23 |         while (arr[j] > pivot) j--;
24 |         if (i <= j) {
25 |             int temp = arr[i];
26 |             arr[i] = arr[j];
27 |             arr[j] = temp;
28 |             i++; j--;
29 |         }
30 |     }
31 |     recursion(depth - 1, arr, j + 1);
32 |     recursion(depth - 1, arr + i, size - i);
33 | }
34 |
35 | int main() {
36 |     int a, b, d;
37 |     cin >> a >> b >> d;
38 |     generate(a, b, c);
39 |     recursion(d, c, b);
40 |     for (int i = 0; i < b; ++i) cout << c[i] << " ";
41 |     cout << endl;
42 | }

 1 | #include <iostream>
 2 | #include <string>
 3 | using namespace std;
 4 |
 5 | const int P = 998244353, N = 1e4 + 10, M = 20;
 6 | int n, m;
 7 | string s;
 8 | int dp[1 << M];
 9 |
10 | int solve() {
11 |     dp[0] = 1;
12 |     for (int i = 0; i < n; ++i) {
13 |         for (int j = (1 << (m - 1)) - 1; j >= 0; --j) {
14 |             int k = (j << 1) | (s[i] - '0');
15 |             if (j != 0 || s[i] == '1')
16 |                 dp[k] = (dp[k] + dp[j]) % P;
17 |         }
18 |     }
19 |     int ans = 0;
20 |     for (int i = 0; i < (1 << m); ++i) {
21 |         ans = (ans + 1ll * i * dp[i]) % P;
22 |     }
23 |     return ans;
24 | }
25 |
26 | int solve2() {
27 |     int ans = 0;
28 |     for (int i = 0; i < (1<<n); ++i) {
29 |         int cnt = 0;
30 |         int num = 0;
31 |         for (int j = 0; j < n; ++j) {
32 |             if (i & (1<<j)) {
33 |                 num = num * 2 + (s[j]-'0');
34 |                 cnt++;
35 |             }
36 |         }
37 |         if (cnt <= m) (ans += num) %= P;
38 |     }
39 |     return ans;
40 | }
41 |
42 | int main() {
43 |     cin >> n >> m;
44 |     cin >> s;
45 |     if (n <= 20) {
46 |         cout << solve2() << endl;
47 |     }
48 |     cout << solve() << endl;
49 |     return 0;
50 | }

假设输入的 s 是包含 n 个字符的 01 串，完成下面的判断题和单选题：

 1 | #include <iostream>
 2 |
 3 | #include <cstring>
 4 |
 5 | #include <algorithm>
 6 |
 7 | using namespace std;
 8 |
 9 | const int maxn = 1000000 + 5;
10 |
11 | const int P1 = 998244353, P2 = 1000000007;
12 |
13 | const int B1 = 2, B2 = 31;
14 |
15 | const int K1 = 0, K2 = 13;
16 |
17 | typedef long long ll;
18 |
19 | int n;
20 | bool p[maxn];
21 | int p1[maxn], p2[maxn];
22 |
23 | struct H {
24 |     int h1, h2, l;
25 |     H(bool b = false) {
26 |         h1 = b + K1;
27 |         h2 = b + K2;
28 |         l = 1;
29 |     }
30 |     H operator + (const H & h) const {
31 |         H hh;
32 |         hh.l = l + h.l;
33 |         hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
34 |         hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
35 |         return hh;
36 |     }
37 |     bool operator == (const H & h) const {
38 |         return l == h.l && h1 == h.h1 && h2 == h.h2;
39 |     }
40 |     bool operator < (const H & h) const {
41 |         if (l != h.l) return l < h.l;
42 |         else if (h1 != h.h1) return h1 < h.h1;
43 |         else return h2 < h.h2;
44 |     }
45 | }
46 | h[maxn];
47 |
48 | void init() {
49 |     memset(p, 1, sizeof(p));
50 |     p[0] = p[1] = false;
51 |     p1[0] = p2[0] = 1;
52 |     for (int i = 1; i <= n; ++i) {
53 |         p1[i] = (1ll * B1 * p1[i-1]) % P1;
54 |         p2[i] = (1ll * B2 * p2[i-1]) % P2;
55 |         if (!p[i]) continue;
56 |         for (int j = 2 * i; j <= n; j += i) {
57 |             p[j] = false;
58 |         }
59 |     }
60 | }
61 |
62 | int solve() {
63 |     for (int i = n; i; --i) {
64 |         h[i] = H(p[i]);
65 |         if (2 * i + 1 <= n) {
66 |             h[i] = h[2 * i] + h[i] + h[2 * i + 1];
67 |         } else if (2 * i <= n) {
68 |             h[i] = h[2 * i] + h[i];
69 |         }
70 |     }
71 |     cout << h[1].h1 << endl;
72 |     sort(h + 1, h + n + 1);
73 |     int m = unique(h + 1, h + n + 1) - (h + 1);
74 |     return m;
75 | }
76 |
77 | int main() {
78 |     cin >> n;
79 |     init();
80 |     cout << solve() << endl;
81 | }

(1)（序列合并）有两个长度为 N 的单调不降序列 A 和 B，序列的每个元素都是小于 10^9 的非负整数。在 A 和 B 中各取一个数相加可以得到 N^2 个和，求其中第 K 小的和。上述参数满足 N <= 10^5 和 1 <= K <= N^2。

#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int* upper_bound(int *a, int *an, int ai) {
    int l = 0, r = ①;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (②) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return ③;
}

long long get_rank(int sum) {
    long long rank = 0;
    for (int i = 0; i < n; ++i) {
        rank += upper_bound(b, b + n, sum - a[i]) - b;
    }
    return rank;
}

int solve() {
    int l = 0, r = ④;
    while (l < r) {
        int mid = ((long long)l + r) >> 1;
        if (⑤) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    cout << solve() << endl;
}

(2)（次短路）已知一个有 n 个点 m 条边的有向图 G，并且给定图中的两个点 s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279;

int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn << 1], *dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];

void add(int a, int b, int c) {
    ++tot;
    nxt[tot] = head[a];
    to[tot] = b;
    w[tot] = c;
    head[a] = tot;
}

bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
    if (d >= dis[b]) return false;
    if (b < n)
        ①;
    q.push(②);
    dis[b] = d;
    pre[b] = a;
    return true;
}

void solve() {
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, s));
    memset(dis, ③, sizeof(dis));
    memset(pre, -1, sizeof(pre));
    dis2 = dis + n;
    pre2 = pre + n;

    dis[s] = 0;
    while (!q.empty()) {
        int aa = q.top().second; q.pop();
        if (vis[aa]) continue;
        vis[aa] = true;
        int a = aa % n;
        for (int e = head[a]; e; e = nxt[e]) {
            int b = to[e], c = w[e];
            if (aa < n) {
                if (!upd(a, b, dis[a]+c, q))
                    ④;
            } else {
                upd(n+a, n+b, dis2[a]+c, q);
            }
        }
    }
}

void out(int a) {
    if (a != s) {
        if (a < n) out(pre[a]);
        else out(⑤);
    }
    printf("%d%c", a%n+1, " \n"[a == n+t]);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    s--, t--;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a-1, b-1, c);
    }
    solve();
    if (dis2[t] == inf) puts("-1");
    else {
        printf("%d\n", dis2[t]);
        out(n+t);
    }
}