开始整卷作答
按大题分页，翻页自动存草稿，做完统一交卷。
# CSP 2024 提高级第一轮
第 1–15 题 · 共 15 题
### 判断题
第 16–16 题 · 共 1 题
### 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
### 第 1 题
```cpp
#include <iostream>
using namespace std;
const int N = 1000;
int c[N];
int logic(int x, int y) {
return (x & y) ^ ((x ^ y) | (~x & y));
}
void generate(int a, int b, int *c) {
for (int i = 0; i < b; i++)
c[i] = logic(a, i) % (b + 1);
}
void recursion(int depth, int *arr, int size) {
if (depth <= 0 || size <= 1) return;
int pivot = arr[0];
int i = 0, j = size - 1;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
recursion(depth - 1, arr, j + 1);
recursion(depth - 1, arr + i, size - i);
}
int main() {
int a, b, d;
cin >> a >> b >> d;
generate(a, b, c);
recursion(d, c, b);
for (int i = 0; i < b; ++i) cout << c[i] << " ";
cout << endl;
}
```
第 17–20 题 · 共 4 题
### 判断题
第 21–21 题 · 共 1 题
### 第 2 题
```cpp
#include <iostream>
#include <string>
using namespace std;
const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];
int solve() {
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = (1 << (m - 1)) - 1; j >= 0; --j) {
int k = (j << 1) | (s[i] - '0');
if (j != 0 || s[i] == '1')
dp[k] = (dp[k] + dp[j]) % P;
}
}
int ans = 0;
for (int i = 0; i < (1 << m); ++i) {
ans = (ans + 1ll * i * dp[i]) % P;
}
return ans;
}
int solve2() {
int ans = 0;
for (int i = 0; i < (1 << n); ++i) {
int cnt = 0;
int num = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
num = num * 2 + (s[j] - '0');
cnt++;
}
}
if (cnt <= m) (ans += num) %= P;
}
return ans;
}
int main() {
cin >> n >> m;
cin >> s;
if (n <= 20) {
cout << solve2() << endl;
}
cout << solve() << endl;
return 0;
}
```
假设输入的 $s$ 是包含 $n$ 个字符的 $01$ 串，完成下面的判断题和单选题。
第 22–26 题 · 共 5 题
### 判断题
第 27–27 题 · 共 1 题
### 第 3 题
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;
typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];
struct H {
int h1, h2, l;
H(bool b = false) {
h1 = b + K1;
h2 = b + K2;
l = 1;
}
H operator + (const H & h) const {
H hh;
hh.l = l + h.l;
hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
return hh;
}
bool operator == (const H & h) const {
return l == h.l && h1 == h.h1 && h2 == h.h2;
}
bool operator < (const H & h) const {
if (l != h.l) return l < h.l;
else if (h1 != h.h1) return h1 < h.h1;
else return h2 < h.h2;
}
} h[maxn];
void init() {
memset(p, 1, sizeof(p));
p[0] = p[1] = false;
p1[0] = p2[0] = 1;
for (int i = 1; i <= n; ++i) {
p1[i] = (1ll * B1 * p1[i-1]) % P1;
p2[i] = (1ll * B2 * p2[i-1]) % P2;
if (!p[i]) continue;
for (int j = 2 * i; j <= n; j += i) {
p[j] = false;
}
}
}
int solve() {
for (int i = n; i; --i) {
h[i] = H(p[i]);
if (2 * i + 1 <= n) {
h[i] = h[2 * i] + h[i] + h[2 * i + 1];
} else if (2 * i <= n) {
h[i] = h[2 * i] + h[i];
}
}
cout << h[1].h1 << endl;
sort(h + 1, h + n + 1);
int m = unique(h + 1, h + n + 1) - (h + 1);
return m;
}
int main() {
cin >> n;
init();
cout << solve() << endl;
}
```
第 28–32 题 · 共 5 题
### 第 1 题
第 33–33 题 · 共 1 题
### 三、完善程序（单选题，每小题 3 分，共计 30 分）
### 第 1 题
**（序列合并）** 有两个长度为 $N$ 的单调不降序列 $A$ 和 $B$，序列的每个元素都是小于 $10^9$ 的非负整数。在 $A$ 和 $B$ 中各取一个数相加可以得到 $N^2$ 个和，求其中第 $K$ 小的和。上述参数满足 $N \leq 10^5$ 和 $1 \leq K \leq N^2$。
```cpp
#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;
}
```
第 34–37 题 · 共 4 题
### 第 1 题
第 38–38 题 · 共 1 题
**（次短路）** 已知一个有 $n$ 个点 $m$ 条边的有向图 $G$，并且给定图中的两个点 $s$ 和 $t$，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 $-1$。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。
```cpp
#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);
}
}
```
第 39–42 题 · 共 4 题
展开逐题清单（单独练某一道）
● 绿=已通过 ● 橙=做过没全对 ● 灰=没做过
# CSP 2024 提高级第一轮
1.
[CSP2024 提高级] 第 1 题
2.
[CSP2024 提高级] 第 2 题
3.
[CSP2024 提高级] 第 3 题
4.
[CSP2024 提高级] 第 4 题
5.
[CSP2024 提高级] 第 5 题
6.
[CSP2024 提高级] 第 6 题
7.
[CSP2024 提高级] 第 7 题
8.
[CSP2024 提高级] 第 8 题
9.
[CSP2024 提高级] 第 9 题
10.
[CSP2024 提高级] 第 10 题
11.
[CSP2024 提高级] 第 11 题
12.
[CSP2024 提高级] 第 12 题
13.
[CSP2024 提高级] 第 13 题
14.
[CSP2024 提高级] 第 14 题
15.
[CSP2024 提高级] 第 15 题
### 判断题
16.
[CSP2024 提高级] 第 16 题
### 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
### 第 1 题
```cpp
#include <iostream>
using namespace std;
const int N = 1000;
int c[N];
int logic(int x, int y) {
return (x & y) ^ ((x ^ y) | (~x & y));
}
void generate(int a, int b, int *c) {
for (int i = 0; i < b; i++)
c[i] = logic(a, i) % (b + 1);
}
void recursion(int depth, int *arr, int size) {
if (depth <= 0 || size <= 1) return;
int pivot = arr[0];
int i = 0, j = size - 1;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
recursion(depth - 1, arr, j + 1);
recursion(depth - 1, arr + i, size - i);
}
int main() {
int a, b, d;
cin >> a >> b >> d;
generate(a, b, c);
recursion(d, c, b);
for (int i = 0; i < b; ++i) cout << c[i] << " ";
cout << endl;
}
```
17.
[CSP2024 提高级] 第 17 题
18.
[CSP2024 提高级] 第 18 题
19.
[CSP2024 提高级] 第 19 题
20.
[CSP2024 提高级] 第 20 题
### 判断题
21.
[CSP2024 提高级] 第 21 题
### 第 2 题
```cpp
#include <iostream>
#include <string>
using namespace std;
const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];
int solve() {
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = (1 << (m - 1)) - 1; j >= 0; --j) {
int k = (j << 1) | (s[i] - '0');
if (j != 0 || s[i] == '1')
dp[k] = (dp[k] + dp[j]) % P;
}
}
int ans = 0;
for (int i = 0; i < (1 << m); ++i) {
ans = (ans + 1ll * i * dp[i]) % P;
}
return ans;
}
int solve2() {
int ans = 0;
for (int i = 0; i < (1 << n); ++i) {
int cnt = 0;
int num = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
num = num * 2 + (s[j] - '0');
cnt++;
}
}
if (cnt <= m) (ans += num) %= P;
}
return ans;
}
int main() {
cin >> n >> m;
cin >> s;
if (n <= 20) {
cout << solve2() << endl;
}
cout << solve() << endl;
return 0;
}
```
假设输入的 $s$ 是包含 $n$ 个字符的 $01$ 串，完成下面的判断题和单选题。
22.
[CSP2024 提高级] 第 22 题
23.
[CSP2024 提高级] 第 23 题
24.
[CSP2024 提高级] 第 24 题
25.
[CSP2024 提高级] 第 25 题
26.
[CSP2024 提高级] 第 26 题
### 判断题
27.
[CSP2024 提高级] 第 27 题
### 第 3 题
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;
typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];
struct H {
int h1, h2, l;
H(bool b = false) {
h1 = b + K1;
h2 = b + K2;
l = 1;
}
H operator + (const H & h) const {
H hh;
hh.l = l + h.l;
hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
return hh;
}
bool operator == (const H & h) const {
return l == h.l && h1 == h.h1 && h2 == h.h2;
}
bool operator < (const H & h) const {
if (l != h.l) return l < h.l;
else if (h1 != h.h1) return h1 < h.h1;
else return h2 < h.h2;
}
} h[maxn];
void init() {
memset(p, 1, sizeof(p));
p[0] = p[1] = false;
p1[0] = p2[0] = 1;
for (int i = 1; i <= n; ++i) {
p1[i] = (1ll * B1 * p1[i-1]) % P1;
p2[i] = (1ll * B2 * p2[i-1]) % P2;
if (!p[i]) continue;
for (int j = 2 * i; j <= n; j += i) {
p[j] = false;
}
}
}
int solve() {
for (int i = n; i; --i) {
h[i] = H(p[i]);
if (2 * i + 1 <= n) {
h[i] = h[2 * i] + h[i] + h[2 * i + 1];
} else if (2 * i <= n) {
h[i] = h[2 * i] + h[i];
}
}
cout << h[1].h1 << endl;
sort(h + 1, h + n + 1);
int m = unique(h + 1, h + n + 1) - (h + 1);
return m;
}
int main() {
cin >> n;
init();
cout << solve() << endl;
}
```
28.
[CSP2024 提高级] 第 28 题
29.
[CSP2024 提高级] 第 29 题
30.
[CSP2024 提高级] 第 30 题
31.
[CSP2024 提高级] 第 31 题
32.
[CSP2024 提高级] 第 32 题
### 第 1 题
33.
[CSP2024 提高级] 第 33 题
### 三、完善程序（单选题，每小题 3 分，共计 30 分）
### 第 1 题
**（序列合并）** 有两个长度为 $N$ 的单调不降序列 $A$ 和 $B$，序列的每个元素都是小于 $10^9$ 的非负整数。在 $A$ 和 $B$ 中各取一个数相加可以得到 $N^2$ 个和，求其中第 $K$ 小的和。上述参数满足 $N \leq 10^5$ 和 $1 \leq K \leq N^2$。
```cpp
#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;
}
```
34.
[CSP2024 提高级] 第 34 题
35.
[CSP2024 提高级] 第 35 题
36.
[CSP2024 提高级] 第 36 题
37.
[CSP2024 提高级] 第 37 题
### 第 1 题
38.
[CSP2024 提高级] 第 38 题
**（次短路）** 已知一个有 $n$ 个点 $m$ 条边的有向图 $G$，并且给定图中的两个点 $s$ 和 $t$，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 $-1$。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。
```cpp
#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);
}
}
```
39.
[CSP2024 提高级] 第 39 题
40.
[CSP2024 提高级] 第 40 题
41.
[CSP2024 提高级] 第 41 题
42.
[CSP2024 提高级] 第 42 题