2023 洛谷 SCP-J 第一轮模拟题（入门级 C++）

（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

 1 | #include <iostream>
 2 | #include <cstring>
 3 | using namespace std;
 4 | string s, t;
 5 | string a, b;
 6 | int main(){
 7 |     getline(cin, s);
 8 |     getline(cin, a);
 9 |     getline(cin, b);
10 |     for(int i = 0; i < s.size(); i++){
11 |         bool flag = true;
12 |         if(i + a.size() <= s.size()){
13 |             for(int j = 0; j < a.size(); j++){
14 |                 char p = s[i + j], q = a[j];
15 |                 if('a' <= p && p <= 'z') p = p - 'a' + 'A';
16 |                 if('a' <= q && q <= 'z') q = q - 'a' + 'A';
17 |                 if(p != q)
18 |                     flag = false;
19 |             }
20 |         } else
21 |             flag = false;
22 |
23 |         if(flag == true){
24 |             t += b;
25 |             i += a.size() - 1;
26 |         } else
27 |             t += s[i];
28 |     }
29 |     cout << t << endl;
30 |     return 0;
31 | }

保证输入的三行字符串的长度均不超过 $10^3$，且每个字符串均由 ASCII 可视字符或空格组成且非空。完成下面的判断题和单选题。

 1 | #include<iostream>
 2 | using namespace std;
 3 | int a[100005], b[100005], n, m;
 4 | void very_quick_sort(int l, int r, int p, int q){
 5 |     if(l >= r || p > q){   // ①
 6 |         return;
 7 |     }
 8 |     int mid = (l + r) / 2;
 9 |     int p0 = p - 1;
10 |     int q0 = q + 1;
11 |     for(int i = p; i <= q; i++){
12 |         if(a[i] > mid) b[++p0] = a[i];
13 |         else           b[--q0] = a[i];
14 |     }
15 |     for(int i = p; i <= q; i++)
16 |         a[i] = b[i];
17 |     very_quick_sort(mid + 1, r, p, p0);
18 |     very_quick_sort(l, mid, q0, q);
19 | }
20 | int main(){
21 |     cin >> n >> m;
22 |     for(int i = 1; i <= n; i++)
23 |         cin >> a[i];
24 |     very_quick_sort(1, m, 1, n);
25 |     // ②
26 |     for(int i = 1; i <= n; i++)
27 |         cout << a[i] << " ";
28 |     cout << endl;
29 |     return 0;
30 | }

保证输入的 $n$ 不超过 $10^5$，$m$ 不超过 $10^9$，且 $1\le a_1,a_2,\ldots,a_n\le m$。完成下面的判断题和单选题。

 1 | #include <iostream>
 2 | #include <vector>
 3 | #include <algorithm>
 4 | using namespace std;
 5 | const int mod = 1000000000 + 7;
 6 | int w0[100005];
 7 | int w1[100005];
 8 | int w2[100005];
 9 | int n, m, k, f[100005], d[100005], id[100005];
10 | vector <int> e[100005];
11 | void dfs(int u, int fa){
12 |     d[u] = d[fa] + 1;
13 |     f[u] = fa;
14 |
15 |     for(auto &v : e[u]) if(v != fa){
16 |         dfs(v, u);
17 |     }
18 | }
19 | bool cmp(int a, int b){
20 |     return d[a] < d[b];
21 | }
22 | int main(){
23 |     cin >> n >> m >> k;
24 |     for(int i = 2; i <= n; i++){
25 |         int u, v;
26 |         cin >> u >> v;
27 |         e[u].push_back(v);
28 |         e[v].push_back(u);
29 |     }
30 |     dfs(1, 0);                    // ①
31 |     for(int i = 1; i <= m; i++){
32 |         int x, w;
33 |         cin >> x >> w;
34 |         w1[x] = (w1[x] + w) % mod;
35 |         w2[x] = (w2[x] + w) % mod;
36 |     }
37 |     for(int i = 1; i <= n; i++)
38 |         id[i] = i;
39 |     sort(id + 1, id + 1 + n, cmp);
40 |     for(int i = 1; i <= k; i++){
41 |         for(int j = n; j >= 1; j--){
42 |             int x = id[j];
43 |             for(auto &y : e[x]) if(y != f[x]){
44 |                 w1[y] = (w1[y] + w1[x]) % mod;
45 |             }
46 |             w1[x] = 0;
47 |         }
48 |         for(int x = 1; x <= n; x++)
49 |             w1[x] = (w1[x] - w0[x] + mod) % mod,
50 |             w0[x] = 0;
51 |         for(int j = 1; j <= n; j++){ // ②
52 |             int x = id[j];
53 |             if(f[x]){
54 |                 w1[f[x]] = (w1[f[x]] + w2[x]) % mod;
55 |                 w2[f[x]] = (w2[f[x]] + w2[x]) % mod;
56 |                 w0[x] = (w0[x] + w2[x]) % mod;
57 |                 w2[x] = 0;
58 |             }
59 |         }
60 |     }
61 |     for(int i = 1; i <= n; i++)
62 |         cout << w1[i] << " ";
63 |     return 0;
64 | }

保证输入的 $n,m$ 不超过 $10^5$，$k$ 不超过 20，且 $1\le x_i\le n$，$0\le w_i<10^9+7$。完成下面的判断题和单选题。

（序列问题）给定序列 $a_n$，求有多少对 $(i,j)$ 满足 $a_i<a_j$。测试数据满足 $n\le10^6$，$a_i\le10^9$。

提示：对于任意的 $a_i\ne a_j$，可以发现 $(i,j)$ 或 $(j,i)$ 能对答案产生 1 的贡献，因此只需要用总的对数减去 $a_i=a_j$ 的 $(i,j)$ 数量，就能得到答案。试补全程序。

#include<bits/stdc++.h>
using namespace std;
const int Maxn = ①;
int n, a[Maxn];
long long s[Maxn], ans;
bool check(int l, int r) {
    if (s[r] - s[l - 1] == ②) return true;
    return false;
}



int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    ans = ③;
    for (int i = 1; i <= n;) {
        int l = i, r = n, pos = n;
        while (④) {
            int mid = (l + r) >> 1;
            if(check(l, mid))
                l = mid + 1, pos = mid;
            else
                r = mid - 1;
        }
        ans -= ⑤;
        i = pos + 1;
    }
    cout << ans;
}

（异或和）给定序列 $a_n$，求其所有子区间异或和的和。某个区间的异或和是将这个区间内的所有数字分别进行异或计算。其中 $n\le10^5$，$0\le a_i\le10^9$。

提示：对每一位独立计算，对右端点扫描线，并用异或前缀和辅助统计。试补全程序。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, a[N], cnt[2];
long long ans;
int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], ①;
    for (int bit = ②; ③; bit--) {
        cnt[0] = cnt[1] = 0;
        for (int i = 0; i <= n; i++) {
            cnt[④]++;
            ans += 1LL * ⑤;
        }
    }
    cout << ans;
}