2025CSP-J复赛讲解

AC是最好的

2025-11-16 11:15:21

发布于：福建

21阅读

0回复

0点赞

T1：P14357 [CSP-J 2025] 拼数 / number（民间数据）

题意

给定一个包含小写字母和数字的字符串 $s$ ，要求从小写字母及数字的字符串 $s$ 中选出任意多个数字，并按任意顺序将它们拼接成一个正整数。每个数字只能使用一次。求出所有能拼成的正整数中的最大值。
$1 \le|s|\le10^6$

解析：以发现，最终数字的最高位越大，这个数就越大，因而只需挑出字符串中的所有数字，再按大小降序排序即可。

答案：

#include <bits/stdc++.h>

using namespace std;

string s , ans;

int main( ) {
    //freopen("number.in", "r", stdin);
    //freopen("number.out", "w", stdout);
    
    cin >> s;
    
    for (int i = 0; i < s.length(); i++) {// 选出 s 中的所有数字，加入答案字符串
        if (s[i] >= '0' && s[i] <= '9')
            ans += s[i];
    }
    sort(ans.begin() , ans.end());    // 升序排序
    reverse(ans.begin() , ans.end());// 反转整个字符串（降序）
    
    cout << ans << endl;

    //fclose(stdin);
    //fclose(stdout);

    return 0;
}

T2：P14358 [CSP-J 2025] 座位 / seat（民间数据）

题意：

考场共有 $n$ 行 $m$ 列座位，共有共 $n × m$ 名考生。考生按照成绩由高到低，以“蛇形”顺序分配座位。蛇形分配的规则是：先从第1列第1行向下到第 $n$ 行，然后转向第2列第 $n$ 行向上到第1行，再转向第3列第1行向下到第 $n$ 行，以此类推。给定考场的行数 $n$ 、列数 $m$ 和所有考生的成绩 $a_{1}$ ， $a_{2}$ ，…… ， $a_{n × m}$ （其中a_{1}是小R的成绩)，要求确定小R的座位所在的列数 $c$ 和行数 $r$
$1≤n,m≤10$

解析：

根据其他同学的成绩，可以很轻松的求出小 R 的排名（统计有多少人分数不小于他即可）。假设小 R 排名为 x，则他将位于第 $(x - 1) / n + 1$ 列，第 $(x - 1) 取余 n + 1$ ，当行数为奇数时，恰位于 $(x - 1) 取余 n + 1$ 行，否则将位于第 $m - (x - 1) 取余 n$ 行。分类讨论得出答案。

答案

#include <bits/stdc++.h>

using namespace std;

long long n , m , x;

int main( ) {
    cin >> n >> m >> x;
    long long pos = 1;    // 小 R 排名
    
    for (int i = 2 ; i <= n * m ; i++) {// 计算小 R 排名
        long long y;
        scanf("%lld", &y);
        if (y > x)
            pos++;
    }
    long long l = (pos - 1) / n + 1; // 求列号
    long long h = (pos - 1) % n + 1; // 求行号
    if (l % 2 == 0) {
        h = n - h + 1;
   }

    cout << l << " " << h;

    return 0;
}

T3：P14359 [CSP-J 2025] 异或和 / xor（官方数据）

题意

给定一个长度为 $n$ 的非负整数序列 $a_{1}，a_{2}，……，a_{n}$ 和一个非负整数 $k$ 。定义一个区间 $[l,r]$ 的权值为该区间内所有元素的二进制按位异或和。目标是选择序列中尽可能多的不相交的区间，使得每个区间的权值都等于 $k$ 。

解析

####思路1
令前缀异或和 $S_{x} = a_{1} ⊕ a_{2} ⊕ … ⊕ a_{x}$ ，则区间 $[l,r]$ 异或和可以表示为 $S_{r} ⊕ S_{l -1}$ 。则在右端点固定为 $R$ 时，找到任意满足 $S_{l - 1} = R ⊕ K$ 的 $l$ 等同于为一合法区间，为使区间长度尽可能小，我们选择最大的合法 $l$ 。可以维护 $pos_{x}$ 表示前缀中满足 $s_{y} = x$ 的最大的 $y$ 。在记动态规划状态 $f_x$ 表示前 $x$ 个数中的最大和发区间数，则有动态规划转移方程

$f$ 中的最大值即为答案。

思路2

前半部分推导同解法一，随后，我们考虑使用贪心法，我们要取出足够多的区间，假设我们最终取出了若干个不交区间作为答案集合，那么考虑这个答案里的最左边的集合，它的右端点一定是越靠左越好，将这个最左边的区间取出来之后，相当于我们无法再取任何左侧的点了，那么在剩下的部分中，我们依然是取一个越靠左越好的区间。因此，我们的做法就可以是，从左到右按顺序扫描，每次一旦发现一个合法的区间，就直接取出来，并让答案+1，之后再取区间只能取当前这个点右侧的区间，一直取到最后没有合法区间为止，就能得到答案。判断合法区间的方式就是判断 $pos_{x}$ 是否在上一次取的区间右端点的右侧即可。

答案

思路1

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

ll n, K, num[N], dp[N], pos[N];

int main()
{
	memset(pos, -1, sizeof(pos));
	cin >> n >> K;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
		num[i] ^= num[i - 1]; // 维护异或前缀和
	}

	pos[0] = 0;
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = dp[i - 1];
		if (pos[num[i] ^ K] != -1)
			dp[i] = max(dp[i], dp[pos[num[i] ^ K]] + 1); // 状态转移
		ans = max(ans, dp[i]);							 // 求最大值
		pos[num[i]] = i;								 // 记录各个异或前缀和的位置
	}
	cout << ans;
}

思路2

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

ll n, K, num[N], dp[N], pos[N];

int main()
{
	memset(pos, -1, sizeof(pos));
	cin >> n >> K;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &num[i]);
		num[i] ^= num[i - 1]; // 维护异或前缀和
	}

	pos[0] = 0;
	ll ans = 0;
	int last_r = 0;
	for (int i = 1; i <= n; i++)
	{
		if (pos[num[i] ^ K] >= last_r)
		{
			last_r = i;
			ans++;
		}
		pos[num[i]] = i; // 记录各个异或前缀和的位置
	}
	cout << ans;
}

T4：P14360 [CSP-J 2025] 多边形 / polygon（官方数据）

题意

有 $n$ 根小木棍，长度分别为 $a_{1} , a_{2} , ⋯ , a_{n}$ 。从这 $n$ 根木棍中选出 $m$ 根 ( $m≥3$ )，它们能拼成一个多边形当且仅当所有选出木棍的长度之和大于最长木棍长度的两倍。要求计算出有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形，答案对 $998244353$ 取模

解析

不妨将所有给定木棍根据其长度 $a_{i}$ 排序，假设第 $i$ 根木棍被选择且其长度最大，则需要在前 $i-1$ 根木棍中选取部分，使选择的木棍长度和大于 $a_{i}$ ，这个无法直接求，不过我们可以考虑求其补集。即在前 $i-1$ 根木棍中选取部分，使其长度和小于等于 $a_{i}$ 。这一转换后的问题显然可以用动态规划处理，记 $dp_{i,j}$ 表示前 $i$ 根木棍中选取若干，使其长度和为 $j$ 的方案数，有 $dp_{i,j} = dp_{i - 1 , j} + dp_{i - 1 , j - a_{i}}$ 注意 $a_{i} > j$ 时，后一项视为0.最后用所用的所有选取方案数减去 $2^n$ 减去不合法的部分即可

答案

#include <bits/stdc++.h>
#define ll long long
#define MN 5000
#define N 5010
#define M 998244353
using namespace std;

ll n, m, num[N], dp[N];

inline void Add(ll &u, ll v) { u = (u + v) % M; } // u+=v，再取模
inline ll po(ll u, ll v)                          // 乘法快速幂，计算 u^v
{
    ll res = 1;
    for (; v;)
    {
        if (v & 1)
            res = res * u % M;
        u = u * u % M;
        v >>= 1;
    }
    return res;
}

int main()
{
    dp[0] = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &num[i]);
    sort(num + 1, num + n + 1);

    ll ans = po(2, n) - 1;       // 总方案数
    for (int i = 1; i <= n; i++) // 枚举最长木棍 ai
    {
        for (int j = 0; j <= num[i]; j++)
            Add(ans, M - dp[j]); // 去掉此时的不合法方案
        for (int j = MN; j >= num[i]; j--)
            Add(dp[j], dp[j - num[i]]); // 状态转移
    }
    cout << ans;
}