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

{1}

#include <iostream>
using namespace std;
int n, k, ans;

int main() {
    cin >> n >> k; // 保证 n, k 是非负整数，且在 int 范围内
    int ans = 0;
    while (n) {
        if (n % k > 0) ans++;
        n /= k;
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
using namespace std;

int equationCount(int n, int m) {
    if (n == 1 || m == 1) return 1;
    if (n < m) return equationCount(n, n);
    if (n == m) return 1 + equationCount(n, n - 1);
    return equationCount(n, m - 1) + equationCount(n - m, m);
}

int main() { // 本题不需要考虑数值溢出的可能性
    int n;
    cin >> n;
    cout << equationCount(n, n) << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int maxn = 100000;
int a[maxn], b[maxn], n;

int Search(int num, int low, int high) {
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (num >= b[mid]) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

int main() {
    int len, pos;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    b[1] = a[1];
    len = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] >= b[len]) b[++len] = a[i];
        else {
            pos = Search(a[i], 1, len);
            b[pos] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

（精准覆盖问题）给定一个 $N \times M$ 的 0-1 矩阵，求选出其中的一些行，使对 1..M 的每一列，在所选行内有且只有一行该列为 1。例如如下的矩阵中第 1、4、5 行就是一种可行解。

11100001 10001110 10010110 00010010 00001100

输入数据：有多组数据，每组数据第一行的两个整数为 N, M；接下来 N 行，每行开头为一个整数 x，表示该行 1 的个数，其后的 x 个整数表示每个 1 所在的列编号。

输出要求：如果有解，随意输出一组可行解的行的集合，否则输出 NO。

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define N 2005
#define M 2000005

int n, m, h[N], s[N], q[N];
int u[M], d[M], L[M], R[M], C[M], X[M];

void del(int c) {
    ①;
    ②;
    for (int i = d[c]; i != c; i = d[i])
        for (int j = R[i]; j != i; j = R[j])
            u[d[j]] = d[u[j]] = j, s[C[j]]--;
}

void add(int c) {
    L[R[c]] = R[L[c]] = c;
    for (int i = u[c]; i != c; i = u[i])
        for (int j = L[i]; j != i; j = L[j])
            u[d[j]] = d[u[j]] = j, s[C[j]]++;
}

bool dance(int k) {
    if (R[0] == 0) return true;
    int mn = inf, c;
    for (int i = R[0]; i; i = R[i])
        if (s[i] < mn) mn = s[i], c = i;
    ③;
    for (int i = d[c]; i != c; i = d[i]) {
        q[k + 1] = i;
        for (int j = R[i]; j != i; j = R[j]) ④;
        if (dance(k + 1)) return true;
        for (int j = L[i]; j != i; j = L[j]) ⑤;
    }
    add(c);
    return false;
}

（树的直径）给定一棵有 n 个节点的树，每条边的长度为 $w_{i}$。树的直径指树中最长的简单路径，请求这棵树的直径长度。

求解方法：开始任选一个节点 u 作为起点进行 BFS，找到距离 u 最远的节点 s；再以节点 s 为起点，再次进行 BFS，找到距离 s 最远的节点 t。s 和 t 之间的路径长度就是树的直径长度。

#include <iostream>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
struct Node { int to, w, next; } edge[maxn * 2];
int head[maxn], tot, n, dis[maxn];
bool vis[maxn];
int que[maxn], first, last;

void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

void addedge(int u, int v, int w) {
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}

int BFS(int u) {
    first = last = 0;
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[u] = 0;
    vis[u] = 1;
    que[last++] = u;
    while (①) {
        u = que[first++];
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (②) {
                vis[v] = 1;
                que[last++] = v;
                ③;
            }
        }
    }
    int tmp = 1;
    for (int i = 2; i <= n; i++)
        if (④) tmp = i;
    return tmp;
}

int main() {
    int u, v, w, s, t;
    cin >> n;
    init();
    for (int i = 1; i < n; i++) {
        cin >> u >> v >> w;
        addedge(u, v, w);
        addedge(v, u, w);
    }
    s = BFS(1);
    ⑤;
    cout << dis[t] << endl;
    return 0;
}