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

#include <cstdio>
using namespace std;

int findvall(int n) {
    int f;
    if (n == 0) return 1;
    else f = findvall(n / 2);
    return n * f;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d
", findvall(n));
    return 0;
}

#include <cstdio>
#include <cstring>
using namespace std;

int main() {
    char str[60];
    int len, i, j, chr[26];
    char mmin = 'z';
    scanf("%s", str); // 保证输入仅含小写字母
    len = (int)strlen(str);
    for (i = len - 1; i >= 1; i--)
        if (str[i - 1] < str[i]) break;
    if (i == 0) {
        printf("No result!
");
        return 0;
    }
    for (j = 0; j < i - 1; j++) putchar(str[j]);
    memset(chr, 0, sizeof(chr));
    for (j = i; j < len; j++) {
        if (str[j] > str[i - 1] && str[j] < mmin)
            mmin = str[j];
        chr[str[j] - 'a']++;
    }
    chr[mmin - 'a']--;
    chr[str[i - 1] - 'a']++;
    putchar(mmin);
    for (i = 0; i < 26; i++)
        for (j = 0; j < chr[i]; j++)
            putchar(i + 'a');
    putchar('
');
    return 0;
}

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

int a, mp[101][101];
int t[100003], y[100003], cnt;
int len = 2, dir = 3, die = 0;
const int dx[5] = {0, 0, -1, 0, 1};
const int dy[5] = {0, -1, 0, 1, 0};
int nx = 0, ny = 1, px = 1, py = 2;

int check(int x, int yy) {
    if (x < 1 || x > a || yy < 1 || yy > a) return 1;
    if (cnt + 1 - mp[x][yy] < len) return 1;
    return 0;
}

void work() {
    if (die) return;
    px += nx;
    py += ny;
    die = check(px, py);
    if (die) return;
    mp[px][py] = ++cnt;
}

void show() {
    for (int i = 1; i <= a; ++i) {
        for (int j = 1; j <= a; ++j) {
            if (mp[i][j] != 0 && mp[i][j] >= cnt - len + 1) putchar('o');
            else putchar('.');
        }
        puts("");
    }
}

int main() {
    memset(mp, 0xf0, sizeof(mp));
    mp[1][1] = ++cnt;
    mp[1][2] = ++cnt;
    int n, m, op, xx;
    char s[3];
    scanf("%d", &a);
    scanf("%d%d", &n, &m);
    while (n--) {
        scanf("%d%d", &op, &xx);
        if (op == 1) {
            t[xx] = 1;
            scanf("%s", s);
            if (s[0] == 'L') y[xx] = 1;
            else if (s[0] == 'U') y[xx] = 2;
            else if (s[0] == 'R') y[xx] = 3;
            else y[xx] = 4;
        } else {
            t[xx] = 2;
        }
    }
    for (int tm = 1; tm <= m; ++tm) {
        if (t[tm] == 1) {
            if (y[tm] % 2 != dir % 2) {
                dir = y[tm];
                nx = dx[y[tm]];
                ny = dy[y[tm]];
            }
        } else if (t[tm] == 2) {
            ++len;
        }
        work();
        if (die) break;
    }
    show();
    return 0;
}

小 D 在外面游玩，回去时想在 App 上点 KFC，然后带回宿舍。他想选择一家 KFC，取完餐后尽快回宿舍，忽略取餐时间。地图可看作 $n \times m$ 的网格，其中有一些不可通过的障碍，小 D、KFC、宿舍均可以看作道路，可以通行。小 D 可途经多个 KFC。小 D 可以选择向上、下、左、右四个方向移动，一次移动算一步。求他取到餐并回到宿舍的最少步数。

输入第一行有两个数 n, m。接下来 n 行，每行包含 m 个字符，表示地图。

'S' 表示小 D 的初始位置，

'E' 表示宿舍位置，

'#' 表示障碍物，

1. 表示道路，

$^{1}$K' 表示 KFC。

下面的程序已采用 BFS 算法完成这个问题，试补全程序。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int MAXN = 1e3 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
char s[MAXN][MAXN];
int n, m;
int dir[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};
int dis[2][MAXN][MAXN];

void bfs(int p, int a, int b) {
    memset(dis[p], INF, sizeof(dis[p]));
    dis[p][a][b] = 0;
    queue<pair<P, int>> q;
    q.push({{a, b}, 0});
    while (!q.empty()) {
        int x = q.front().fi.fi, y = q.front().fi.se, d = q.front().se;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int dx = x + dir[0][i], dy = y + dir[1][i];
            if (dx < 1 || dy < 1 || dx > n || dy > m || s[dx][dy] == '#') continue;
            if (①) {
                ②;
                ③;
            }
        }
    }
}

int main(void) {
    while (scanf("%d%d", &n, &m) != EOF) {
        int ans = INF;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s[i][j] == 'S') bfs(0, i, j);
                else if (s[i][j] == 'E') ④;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s[i][j] == 'K') ans = ⑤;
        if (ans == INF) ans = -1;
        printf("%d
", ans);
    }
    return 0;
}

（尺取法求区间个数）给定 n 个非负整数 a[1]..a[n]，求区间和小于或等于 k 的区间个数，即求使 a[L]+\cdots+a[R] ≤ k 的区间 [L,R] 的个数（ $1 \leq L \leq R \leq n$）。由于对内存和时间复杂度有要求，本题已经用尺取法写好部分代码，请补全程序。

输入的第一行为两个整数 n, k (1 ≤ n ≤ 1000000, 0 ≤ k ≤ 10000000 000 000 000 000)，第二行为 n 个数，表示 a[1] ~ a[n] (0 ≤ a[i] ≤ 1000 000 000)。

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

const int mx = 1e6 + 10;
int n, a[mx];
ll k, sum, ans;

int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int r = 0;
    for (int i = 1; i <= n; ++i) {
        while (r < n) {
            if (①) ②;
            else break;
        }
        ③;
        if (i <= r) ④;
        else ⑤;
    }
    printf("%lld
", ans);
    return 0;
}