[CSP-J 2025] 真题报告

注意：本真题报告的正确情况均以洛谷上的提交情况为准（毕竟是官方数据），但编者不保证在小龙OJ的提交全部通过。（所以说，憋抄）

T1 - 拼数/number

知识点：字符串模拟

思路：对每个字符识别，是数字则进行下一步处理，最后输出降序结果。

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

int main(){
	/*正式比赛时要加上：*/
	// freopen("number.in","r",stdin);
	// freopen("number.out", "w",stdout);

	char c;
	priority_queue<int> number;
	while(scanf("%c", &c) && c!='\n' && c!=EOF)	//读入字符串，如果为数字，则进行处理
		if(c>='0' && c<='9')
			number.push(c-'0');

	while(!number.empty())	// 输出
		printf("%d", number.top()), number.pop();
}

T2 - 座位/seat

知识点：非常那啥的模拟
思路：对成绩排序后，模拟每个考生对应的位置，当排到小R时输出即可。
核心思路：先统计小R的排名（统计比他分数高的人数+1），再计算座位：
- 列c = (p-1)/n + 1；
- 行r：若p%n == 0，奇数列r = n，偶数列r = 1；若p%n >= 1，奇数列r = p%n，偶数列r = n-(p%n)+1。
最终输出c和r。

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

int main(){
    int n, m, a[105], p=1;
    cin >> n >> m;
    for(int i=1; i<=n*m; i++)
		cin >> a[i];
    for(int i=2; i<=n*m; i++)
		if(a[i]>a[1]) 
			p++; //O(nm)统计排名
    int c=(p-1)/n+1,r;
    if(c%2) r = p%n ? p%n : n;
    else r = n-(p%n ? p%n : n)+1;
    cout << c << ' ' << r;
    return 0;
}

T3 - 异或和/xor

微信博主@安教练：我就说前缀和会考吧……

很明显，这是一道前缀和的题目。说一下思路：

选择尽可能多的不相交区间，使得每个区间的异或和都等于 $k$ 。
设前缀异或数组： $s_i = a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_i$ ，其中 $s_0 = 0$ 。我们就借此来用前缀和的方式求 $[l,r]$ 的区间和，即 $SoR(l, r) = s_r-s_{l-1}$ 。
要是区间 $[l, r]$ 的异或和等于 $k$ ，则必须满足 $SoR(l, r)=k \Longleftrightarrow SoR(l,r) \oplus k$ 。
那这道题就可以转化为：在 $s$ 数组中寻找尽可能多的下标对 $(l, r)$ ，满足：
- $l < r$
- $s_r = s_l \oplus k$
- 对应 $[l+1, q]$ 互不重叠
再用贪心来做，哈希表记录各前缀异或值最近出现位置，按照条件选取区间。

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

const int N = 500009;
int a[N], s[N];
map<int, int> lst;

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
        
    lst[0] = 0;
    int last = 0, ans = 0;
    for(int i=1; i<=n; i++){
        s[i] = s[i-1]^a[i];
        int target = s[i]^k;
        if(lst.count(target) && lst[target]>=last)
            ans++,
            last = i;
            
        lst[s[i]] = i;
        
    }
    printf("%d", ans);
}

T4 - 多边形/polygon

思路：

由于两种方案不同当且仅当选择的小木棍的下标集合不同，也就是我们不关心选出来的木棍怎么排序，那么这个多边形我们能知道的重要信息只有使用的木棍数量和使用的木棍长度最大值。
显然，这两个信息同时处理并不方便，我们肯定得先解决掉其中一个点。样例解释中解释是按照使用的木棍数量顺序给出的，考虑到一般黑心出题人都喜欢用样例解释误导选手，所以我考场上果断选择从使用的木棍长度最大值入手。
假设已知多边形最长的木棍是哪根，那么有多少种选法？ —很明显，选法数量就是用短于最长木棍的所有木棍拼出来的长度中，大于最长木棍长度的数量。
题目加粗文字中有“集合”二字，想一想可以发现：从集合中挑出一些数，求组成某个和的方案有多少种，这是经典的 01 背包计数问题。于是我们可以升序枚举用到的最长木棍，并求出所对的方案数。
特别地，对于大于 $\max a_i$ 的长度的方案数，我们并不关心他们实际有多长，全部记为长度为 5001 即可。

时间复杂度： $O(n \times \max a_i)$

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

const int mod = 998244353;
int n, a[5005], f[5005]={1}, ans;

int main(){
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    sort(a+1, a+1+n);
    for(int i=1; i<=n; i++){
        for(int j=5001; j>a[i]; j--)
            (ans+=f[j]) %= mod;
        for(int j=5001; j>=5001-a[i]; j--)
            (f[5001]+=f[j]) %= mod;
        for(int j=5000; j>=a[i]; j--)
            (f[j]+=f[j-a[i]]) %= mod;
    }
    cout << ans;
    return 0;
}

目录

[CSP-J 2025] 真题报告

T1 - 拼数/number

T2 - 座位/seat

T3 - 异或和/xor

T4 - 多边形/polygon