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

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

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 | int x, y;
 4 | unsigned int n;
 5 | int main() {
 6 |     cin >> n >> x >> y;
 7 |     unsigned int mask = 0xff;
 8 |     int x8 = x << 3;
 9 |     int y8 = y << 3;
10 |     unsigned int nx = (n >> x8) & mask, ny = (n >> y8) & mask;
11 |     n &= (~(mask << x8));
12 |     n &= (~(mask << y8));
13 |     n |= (nx << y8);
14 |     n |= (ny << x8);
15 |     cout << "0x";
16 |     cout << std::hex << n << endl;
17 |     return 0;
18 | }

假设输入的 `n` 是 32 位无符号整数范围内的整数，`x,y` 是不超过 3 的自然数，完成下面的判断题和单选题。

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | int n, k;
 5 |
 6 | int func(vector <int> &nums) {
 7 |     int ret = 0;
 8 |     for(int i = n; i > k; i--) {
 9 |         if(nums[i] > nums[i - k]) {
10 |             swap(nums[i], nums[i - k]);
11 |             ret++;
12 |         }
13 |     }
14 |     return ret;
15 | }
16 |
17 | int main() {
18 |     cin >> n >> k;
19 |     vector <int> a(n + 1, 0);
20 |     for(int i = 1; i <= n; i++)
21 |         cin >> a[i];
22 |     int counter = 0, previous = -1;
23 |     while(counter != previous){
24 |         previous = counter;
25 |         counter += func(a);
26 |     }
27 |     for(int i = 1; i <= n; i++)
28 |         cout << a[i] << ",";
29 |     cout << endl << counter << endl;
30 |     return 0;
31 | }

假设输入的 `n,k` 是不超过 100000 的正整数，输入的 $a_i$ 是不超过 $10^9$ 的整数，`k` 小于等于 `n`，完成下面的判断题和单选题。

 1 | #include <iostream>
 2 | #include <vector>
 3 | #include <queue>
 4 | using namespace std;
 5 | const int MAXN = 200001;
 6 | int main() {
 7 |     int n, m, l, r, w;
 8 |     cin >> n >> m;
 9 |     vector <int> dist(MAXN, -1);
10 |     vector <bool> vis(MAXN, false);
11 |     vector <vector <pair<int, int> > > go(MAXN);
12 |     for(int i = 1; i <= m; i++) {
13 |         cin >> l >> r >> w;
14 |         go[l].push_back(make_pair(r + 1, w));
15 |         go[r + 1].push_back(make_pair(l, -w));
16 |     }
17 |     queue <int> q;
18 |     dist[1] = 0, vis[1] = true;
19 |     q.push(1);
20 |     while(!q.empty()) {
21 |         int x = q.front(); q.pop();
22 |         for(auto i : go[x]) {
23 |             if(!vis[i.first]) {
24 |                 vis[i.first] = true;
25 |                 dist[i.first] = dist[x] + i.second;
26 |                 q.push(i.first);
27 |             }
28 |         }
29 |     }
30 |     if(dist[n + 1] == -1) cout << "sorry" << endl;
31 |     else cout << dist[n + 1] << endl;
32 |     return 0;
33 | }

假设输入的 `n,m` 是不超过 200000 的正整数，程序第 13 行每次输入的 `l,r` 保证 `l<=r`，完成下面的判断题和单选题。

（优美的进制）给出整数 `n`；`k` 进制是优美的，当且仅当 `n` 在 `k` 进制下至少有两位，且每一位的数值都不同。求对于给定的 `n`，有哪些进制是优美的，不存在则输出 -1。试补全程序。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int vis[MAXN], a[MAXN];
vector<int> ans;
int check(int k) {
    int x = n, top = 0;
    for (int i = 0; i <= k; i++) vis[i] = 0;
    while (①) {
        a[++top] = ②;
        x = ③;
    }
    if (top < 2)
        return 0;
    for (int i = 1; i <= top; i++) {
        if (④)
            return 0;
        vis[a[i]] = 1;
    }
    return 1;
}
int main() {
    cin >> n;
    for (int i = ⑤; i <= n; i++) {
        if (check(i))
            ans.push_back(i);
    }
    if (ans.empty()) {
        cout << -1;
    }
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    return 0;
}

（好运的日期）一个日期可以用 `x` 年 `y` 月 `z` 日来表示。我们称一个日期是好运的，当且仅当 $xy(w-z+1)$ 为质数，其中 `w` 为 `x` 年 `y` 月的总天数。输入 `x,y,z`，判断其对应的日期是否好运。保证 `x` 是不超过 2024 的正整数，`y` 是不超过 12 的正整数，`x,y,z` 可以构成一个合法的日期。试补全线性筛法算法，空间限制 512 MiB。

#include <bits/stdc++.h>
using namespace std;

const int MAXW = ①;
const int days[13] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int prime[MAXW], cnt;
bool not_prime[MAXW];

void linear_prime(int n) {
    --n;
    not_prime[0] = not_prime[1] = true;
    for(int i = 2; i <= n; i++) {
        if(not_prime[i] == false)
            prime[++cnt]=i;
        for(int j = 1; ②; j++) {
            not_prime[i * prime[j]] = 1;
            if(i % prime[j] == 0)
                ③;
        }
    }
}
bool check(int n) {
    return ④;
}

int main() {
    linear_prime(MAXW);
    int x, y, z, w;
    cin >> x >> y >> z;
    if(y == ⑤)
        w = check(x) ? 29 : 28;
    else
        w = days[y];
    if(not_prime[x * y * (w - z + 1)])
        cout << "unlucky" << endl;
    else
        cout << "lucky" << endl;
    return 0;
}