提高组 CSP-S 2026 初赛模拟卷 5

#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, a[N], res[2];

void solve() {
    int xor_all = 0;
    for (int i = 0; i < n; i++) xor_all ^= a[i];
    int low_bit = xor_all & -xor_all;
    for (int i = 0; i < n; i++) {
        if (a[i] & low_bit) res[0] ^= a[i];
        else res[1] ^= a[i];
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    solve();
    cout << res[0] << " " << res[1] << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int n, k, d[N];

int solve(int left, int right, int k) {
    if (left == right) return d[left];
    int pivot = d[right], i = left - 1;
    for (int j = left; j < right; j++)
        if (d[j] > pivot) swap(d[++i], d[j]);
    swap(d[i + 1], d[right]);
    int pivotIndex = i + 1;
    if (k == pivotIndex) return d[k];
    if (k < pivotIndex) return solve(left, pivotIndex - 1, k);
    return solve(pivotIndex + 1, right, k);
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> d[i];
    cout << solve(0, n - 1, k - 1) << endl;
    return 0;
}

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

int solve(string t1, string t2) {
    int m = t1.length(), n = t2.length();
    vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (t1[i - 1] == t2[j - 1])
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }
    return f[m][n];
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << solve(s1, s2) << endl;
    return 0;
}

（最短路径变种）在一个 $m \times n$ 的网格地图中，每个网格单元 $(i,j)$ 都有一个整数高度值 $h[i][j]$。现在需要从左上角 $(0,0)$ 移动到右下角 $(m-1,n-1)$，每次只能向上、下、左、右四个方向移动一个网格单元。但是，移动时相邻两个网格单元的高度差不能超过给定的阈值 $d$。也就是说，从高度为 $h_{1}$ 的格子移动到高度为 $h_{2}$ 的格子时，必须满足 $|h_{1}-h_{2}|\leq d$。请设计算法，计算在这种限制条件下从起点到终点的最短路径长度（移动步数）。若无法到达终点，则返回 -1。

#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int m, n, d;
int h[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Node {
    int x, y, dst;
    bool operator>(const Node& other) const {
        return dst > other.dst;
    }
};

int solve() {
    vector<vector<int>> dst(m, vector<int>(n, INT_MAX));
    dst[0][0] = 0;
    priority_queue<Node, vector<Node>, ①> q;
    q.push((Node){0, 0, 0});
    while (!q.empty()) {
        Node now = q.top();
        q.pop();
        if (②) continue;
        for (int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (③) {
                    int cost = now.dst + 1;
                    if (cost < dst[nx][ny]) {
                        dst[nx][ny] = cost;
                        ④;
                    }
                }
            }
        }
    }
    return ⑤;
}

（欧拉函数）欧拉函数 $\varphi(n)$ 是一个在数论中非常重要的函数，它表示小于或等于 n 的正整数中与 n 互素的数的数量。例如， $\varphi(8)=4$，因为 1,3,5,7 均与 8 互素。

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

ll eulerPhi(int n) {
    if (n == 1) return 1;
    vector<int> prime;
    int temp = n;
    for (int i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            prime.push_back(i);
            while (temp % i == 0) temp /= i;
        }
    }
    if (temp > 1) ①;
    int k = prime.size();
    ll result = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        ll product = 1;
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            if (②) {
                cnt++;
                product *= prime[i];
            }
        }
        if (cnt == 0) {
            ③;
        } else if (cnt % 2 == 1) {
            ④;
        } else {
            ⑤;
        }
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    cout << eulerPhi(n) << endl;
    return 0;
}