2025年CSP-J同步赛

IOI

#include <iostream>
using namespace std;
int f(int n, int m) {
    if (n == 1) return m;
    if (m == 1) return n;
    int res = 0;
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            res += f(i, j);
    return res;
}
int n, m;
int main() {
    cin >> n >> m;
    cout << f(n, m) << endl;
    return 0;
}

#include <iostream>
using namespace std;
int c[100], n, s, cnt, ans;
void calln(int x) {
    while (x) {
        n++;
        x >>= 1;
    }
}
int bitcount(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}
int main() {
    cin >> s;
    calln(s);
    for (int i = s; i; i = s & (i-1)) {
        cnt++;
        c[bitcount(i)] += i;
    }
    for (int i = 1; i <= n; i++)
        ans = max(ans, c[i]);
    cout << cnt << endl;
    cout << ans << endl;
    return 0;
}

假设输入的 s 为正整数且不超过 $10^9$，完成下面的判断题和单选题：

#include <iostream>
using namespace std;
int f[1001], g[1001], p[1001], m, n;
void init() {
    f[1] = g[1] = 1;
    for (int i = 2; i <= 1000; i++) {
        if (!f[i]) {
            p[++m] = i;
            for (int j = i*i; j <= 1000; j += i)
                f[j] = 1;
        }
        g[i] = g[i-1] + f[i];
    }
}
int main() {
    init();
    cin >> n;
    cout << f[n] << endl;
    cout << g[n] << endl;
    if (n <= 100)
        cout << p[n] << endl;
    return 0;
}

给定一个由 $1 \sim n$ 构成的排列 $a$，求 $a$ 的上一个排列。比如，当 $n$ 等于 3 时，由 $1 \sim 3$ 构成的全排列按照从小到大排如下所示：

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

其中，排列 3,2,1 的上一个排列为 3,1,2；排列 3,1,2 的上一个排列为 2,3,1；排列 2,3,1 的上一个排列为 2,1,3；排列 2,1,3 的上一个排列为 1,3,2；排列 1,3,2 的上一个排列为 1,2,3；排列 1,2,3 没有上一个排列。

你的任务是根据输入的排列计算并输出其上一个排列；

特别地，若输入的排列没有上一个排列，输出 -1 。试补全下面的模拟上一个排列的程序。

#include <iostream>	
#include <algorithm>	
using namespace std;	
int n, a[1000];	
bool cmp(int a, int b) {	
    return (1);	
}	
bool pre_permutation(int a[], int n) {
    int i = n-1;	
    while (i > 0 && a[i-1] < a[i])	
        i--;	
    if ((2))	
        return false;	
    for (int j = i; j < n; j++) {	
        if (j == n-1 || (3)) {
            swap((4), a[j]);	
            break;	
        }	
    }	
    sort((5), a+n, cmp);	
    return true;	
}	
int main() {	
    cin >> n;	
    for (int i = 0; i < n; i++)	
        cin >> a[i];	
    if (pre_permutation(a, n)) {	
        for (int i = 0; i < n; i++)	
            cout << a[i] << " ";	
    }	
    else {	
        cout << -1 << endl;	
    }	
    return 0;	
}	

某科技公司有 $n$ 名工程师需要配备高性能工作站。公司为这次采购预留了 $A$ 元的预算。与此同时，第 $i$ 位工程师有自己的个人设备采购基金 $M_i$ 元。

市场上有 $B(B ≥ n)$ 款不同型号的工作站可供选择，第 $j$ 款工作站的价格为 $C_j$ 元。每位工程师可以使用自己的个人基金或公司的预算资金来购买工作站，但财务规定要求：
1、每位工程师只能为自己购买工作站
2、不同工程师之间的资金不能相互借用
公司需要知道最多能为多少名工程师配备工作站
请设计一个算法，计算在满足预算约束的情况下，最多可以有多少名工程师获得工作站。

#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn) {
    int count = 0, i, j;
    i = ___(1)___;
    j = 1;
    while (i <= n) {
        if (___(2)___)
            count += C[j] - M[i];
        i++;
        j++;
    }
    return ___(3)___;
}
void sort(int a[], int l, int r) {
    int i = l, j = r, x = a[(l + r) / 2], y;
    while (i <= j) {
        while (a[i] < x) i++;
        while (a[j] > x) j--;
        if (i <= j) {
            y = a[i];
            a[i] = a[j];
            a[j] = y;
            i++;
            j--;
        }
    }
    if (i < r) sort(a, i, r);
    if (l < j) sort(a, l, j);
}
int main() {
    int i;
    cin >> n >> B >> A;
    for (i = 1; i <= n; i++)
        cin >> M[i];
    for (i = 1; i <= B; i++)
        cin >> C[i];
    sort(M, 1, n);
    sort(C, 1, B);
    l = 0;
    r = n;
    while (l <= r) {
        mid = (l + r) / 2;
        if (___(4)___) {
            ans = mid;
            l = mid + 1;
        } else
            r = ___(5)___;
    }
    cout << ans << endl;
    return 0;
}