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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i]; // 保证输入的都是正整数

    vector<vector<bool>> dp(k + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;
    for (int idx = 0; idx < n; idx++) {
        int num = nums[idx];
        for (int i = k; i >= 1; i--) {
            for (int j = m; j >= num; j--) {
                if (dp[i - 1][j - num]) {
                    dp[i][j] = true;
                }
            }
        }
    }

    if (dp[k][m]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
typedef long long ll;

ll fPow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    ll n, p;
    cin >> n >> p;
    if (n >= p) {
        cout << 0 << endl;
        return 0;
    }
    ll res = p - 1;
    for (ll i = n + 1; i < p; i++)
        res = (res * fPow(i, p - 2, p)) % p;
    cout << res << endl;
    return 0;
}

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if ((n & 1) == 0) return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    for (int i = l; i <= r; i++) {
        if (isPrime(i)) {
            int power2 = 1;
            while (power2 < i) power2 <<= 1;
            if ((power2 - i) <= 2 || (i - (power2 >> 1)) <= 2)
                cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

求解同余方程组： $x \equiv a_i \pmod{m_i}$， $i = 0, \cdots, n-1$，输出 $x$ 的最小正整数解，若无解则输出 -1。

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll exgcd(①) {
    if (②) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y = y - a / b * x;
    return g;
}

ll mod(ll a, ll b) {
    return (a % b + b) % b;
}

ll crt(vector<ll> &a, vector<ll> &m) {
    int n = a.size();
    ll a1 = a[0], m1 = m[0];
    for (int i = 1; i < n; i++) {
        ll a2 = a[i], m2 = m[i];
        ll x, y;
        ll g = exgcd(m1, m2, x, y);
        if (③) return -1;

        ll p, q;
        exgcd(m1 / g, m2 / g, p, q);
        ④;

        ll x_val = (a1 + m1 * (a2 - a1) / g * p) % lcm;
        a1 = mod(x_val, lcm);
        m1 = lcm;
    }
    return ⑤;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), m(n);
    for (int i = 0; i < n; i++) // 表示一个方程 x ≡ a (mod m)
        cin >> a[i] >> m[i];
    ll res = crt(a, m);
    if (res == -1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

给定一棵有 n 个节点的树，树以节点 1 为根。程序使用倍增算法求解树上任意两个节点的最近公共祖先（LCA）。最近公共祖先是指两个节点在树上的公共祖先中深度最大的那个节点。当有多组问询时，按照问询的顺序，依次输出每个问询的答案。

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

const int N = 200009;
vector<int> to[N];
int L, n, q, p[N][20];
int tI[N], tO[N], timer;

void dfs(int u, int fa) {
    tI[u] = ++timer;
    p[u][0] = fa;
    for (int i = 1; i <= L; ++i) p[u][i] = ①;
    for (int i = 0; i < to[u].size(); ++i)
        if (to[u][i] != fa) dfs(to[u][i], u);
    tO[u] = ++timer;
}

bool up(int u, int v) {
    return ②;
}

int lca(int u, int v) {
    if (up(u, v)) return u;
    if (up(v, u)) return v;
    for (int i = L; i >= 0; --i)
        if (③) u = p[u][i];
    return ④;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    L = 1;
    while (⑤) ++L;
    dfs(1, 0);

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
}