CSP-J 2025 T1拼数 / number

题目描述

题目链接：T1拼数 / number

题目大意

给定一个字符串 $s$，其中包含小写英文字母和数字（至少包含一个 $1 \sim 9$ 的数字）。需要从字符串中提取所有数字字符（每个数字只能使用一次），然后将这些数字字符重新排列成一个正整数。目标是找出能拼成的最大正整数。

题解思路

要组成最大的正整数，需要将较大的数字放在高位（即数字按降序排列）。由于正整数不能以 $0$ 开头，但题目保证至少有一个 $1 \sim 9$ 的数字，因此降序排列后第一个数字一定不是 $0$，不会出现前导零的问题。

具体步骤：

1. 遍历字符串 $s$，提取所有数字字符（'0'~'9'）。
2. 将提取的数字字符按升序排序（这样便于后续逆序输出）。
3. 将排序后的数字字符从后往前输出（即降序输出），得到最大正整数。

代码实现

#include <bits/stdc++.h>
using namespace std;
char digits[1000006]; // 存储数字字符的数组
int main() {
    string s;
    cin >> s;
    int count = 0;
    for (char c : s) {
        if (c >= '0' && c <= '9') {
            digits[count++] = c;
        }
    }
    sort(digits, digits + count); // 升序排序
    for (int i = count - 1; i >= 0; i--) {
        cout << digits[i]; // 降序输出
    }
    return 0;
}

csp-j 2025 t2座位（seat）

题目描述

题目链接：t2座位seat

题目大意

有 $n \times m$ 名考生参加 CSP-J 2025 第二轮考试，他们的第一轮成绩互不相同。这些考生按照第一轮成绩从高到低蛇形分配座位，座位排列成 $n$ 行 $m$ 列。

蛇形分配规则：

• 第1列：从上到下（第1行到第n行）
• 第2列：从下到上（第n行到第1行）
• 第3列：从上到下（第1行到第n行）
• 第4列：从下到上（第n行到第1行）
• 以此类推...

已知考场座位行数 $n$、列数 $m$ 和所有考生的成绩（第一个成绩是小R的成绩），求小R的座位位置（列和行）。

题解思路

核心思想

1. 确定小R的排名：统计有多少个成绩大于等于小R的成绩（包括小R自己），得到小R在成绩排名中的位置。
2. 模拟蛇形分配过程：按照蛇形路径遍历所有座位，当到达小R的排名位置时，输出当前座位坐标。(此步骤也可以使用数学方法直接计算出位置)

算法步骤

1. 读入 $n$, $m$ 和所有成绩
2. 遍历所有成绩，统计大于等于小R成绩的个数，得到小R的排名 id
3. 初始化当前位置为第1列第1行，方向为向下
4. 从第1个座位开始模拟分配：
   • 如果当前座位序号等于小R的排名，输出座位坐标并结束
   • 按照蛇形规则移动到下一个座位：
     • 当前方向向下时：行号+1
     • 当前方向向上时：行号-1
     • 当行号超出边界时，切换到下一列并反转方向

代码实现

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

int a[105]; // 存储所有考生的成绩

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读入所有成绩
    for (int i = 1; i <= n * m; i++) {
        cin >> a[i];
    }
    
    // 计算小R的排名（有多少个成绩 >= 小R的成绩）
    int rank = 0;
    for (int i = 1; i <= n * m; i++) {
        if (a[i] >= a[1]) { // a[1]是小R的成绩
            rank++;
        }
    }
    
    // 模拟蛇形分配座位
    int current_seat = 0; // 当前分配的座位序号
    int col = 1, row = 1; // 当前分配的座位坐标（列，行）
    int direction = 1;    // 方向：1表示向下，-1表示向上
    
    while (current_seat < n * m) {
        current_seat++;
        
        // 如果当前座位是小R的座位
        if (current_seat == rank) {
            cout << col << " " << row << endl;
            return 0;
        }
        
        // 移动到下一个座位
        row += direction;
        
        // 检查是否需要换列和改变方向
        if (row > n) { // 到达底部
            col++;
            row = n;
            direction = -1; // 改为向上
        } else if (row < 1) { // 到达顶部
            col++;
            row = 1;
            direction = 1; // 改为向下
        }
    }
    
    return 0;
}

代码实现（数学）

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main() {
	int n,m;
	cin >> n >> m;
	int id =0;
	for(int i=1;i<=n*m;i++){
		cin >> a[i];
		if(a[i] >= a[1] ){
			id++;
		}
	}
	int lie,han;
	lie = (id-1)/n+1;//计算所在列
	han = (id-1)%n+1;//在列上的座位偏移量
	
	if(lie%2==1){
		cout << lie <<" "<< han <<endl;
	} else{
		cout << lie<< " "<< n-han+1<<endl;
	}
	return 0;
}

csp-j 2025 t3异或和 / xor

题目描述

题目链接：t3异或和

题目大意

给定一个长度为 $n$ 的非负整数序列和一个非负整数 $k$。需要找出尽可能多的不相交区间，使得每个区间的异或和都等于 $k$。输出最多能选出的区间数量。

题解思路

核心思想

使用贪心算法和前缀异或的思想：

1. 前缀异或：定义 prefix[i] = a[1] ⊕ a[2] ⊕ ... ⊕ a[i]，其中 prefix[0] = 0
2. 区间异或性质：区间 [l, r] 的异或和 = prefix[r] ⊕ prefix[l-1]
3. 关键观察：如果 prefix[r] ⊕ prefix[l-1] = k，那么 prefix[l-1] = prefix[r] ⊕ k

算法步骤

1. 维护一个集合 s 来记录已经出现的前缀异或值，初始时包含 0
2. 维护当前前缀异或值 temp，初始为 0
3. 遍历序列中的每个元素：
   • 更新当前前缀异或值：temp = temp ⊕ a[i]
   • 检查 temp ⊕ k 是否在集合 s 中：
     • 如果存在，说明找到了一个新的满足条件的区间，答案加1
     • 然后重置状态：清空集合，重新加入 0，重置 temp = 0
   • 将当前 temp 加入集合 s

代码实现

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

int a[500005]; // 序列数组

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    set<int> s;      // 记录出现过的前缀异或值
    int temp = 0;    // 当前前缀异或值
    int ans = 0;     // 答案计数
    
    s.insert(0);     // 初始化，空前缀的异或值为0
    
    for (int i = 1; i <= n; i++) {
        temp ^= a[i]; // 更新前缀异或值
        
        // 检查是否存在前缀使得区间异或和为k
        if (s.count(temp ^ k)) {
            ans++;          // 找到新的区间
            s.clear();      // 重置状态
            s.insert(0);    // 重新初始化
            temp = 0;       // 重置前缀异或值
        } else {
            s.insert(temp); // 记录当前前缀异或值
        }
    }
    
    cout << ans << endl;
    return 0;
}

csp-j 2025 t4多边形 / polygon

题目描述

题目链接：t4多边形 / polygon

题目大意

有 $n$ 根长度分别为 $a_1, a_2, \dots, a_n$ 的小木棍。需要计算有多少种选择木棍的方案（至少选3根），使得选出的木棍能拼成一个多边形。

多边形条件：设选出的木棍长度为 $l_1, l_2, \dots, l_m$，则必须满足：

• $m \geq 3$
• 总长度大于最大长度的两倍：$\sum_{i=1}^m l_i > 2 \times \max_{i=1}^m l_i$

输出方案数对 $998,244,353$ 取模的结果。

题解思路

核心思想

使用容斥原理和动态规划：

1. 总方案数：所有至少选3根木棍的方案数
2. 不合法方案：总长度 ≤ 最大长度的两倍的方案
3. 答案 = 总方案数 - 不合法方案数

关键观察

• 将木棍按长度从小到大排序
• 对于每个木棍 $a_i$ 作为最大值的情况，计算以 $a_i$ 为最大值的不合法方案数
• 不合法条件：总长度 ≤ $2 \times a_i$

算法步骤

1. 排序：将木棍按长度从小到大排序
2. 动态规划：
   • dp[i][j] 表示前 $i$ 根木棍中选出若干根，总长度为 $j$ 的方案数
   • 状态转移：dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]
3. 容斥计算：
   • s 记录前 $i-1$ 根木棍的所有子集数（包括空集）
   • 对于每个 $a_i$，减去前 $i-1$ 根木棍中总长度 $j \leq a_i$ 的方案数
   • 这些方案加上 $a_i$ 后，总长度 ≤ $2 \times a_i$，不满足多边形条件

代码实现

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

const int mod = 998244353;
int n, a[5005], dp[5005][5005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 按长度排序
    sort(a + 1, a + n + 1);
    
    // 初始化动态规划
    dp[0][0] = 1;
    int s = 1;  // 前i-1根木棍的子集数（包括空集）
    int ans = 0; // 最终答案
    
    for (int i = 1; i <= n; i++) {
        // 累加前i-1根木棍的所有子集数
        ans = (ans + s) % mod;
        
        // 动态规划转移
        for (int j = 0; j <= 5000; j++) {
            dp[i][j] = dp[i - 1][j]; // 不选第i根
            // 容斥：减去不合法方案
            if (j <= a[i]) {
                // 以a[i]为最大值，前i-1根总长度j <= a[i]的方案
                // 加上a[i]后总长度 <= 2*a[i]，不满足多边形条件
                ans = (ans - dp[i - 1][j] + mod) % mod;
            }
            if (j >= a[i]) {
                // 选第i根
                dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % mod;
            }
        }
        
        // 更新子集数
        s = s * 2 % mod;
    }
    
    cout << ans << endl;
    return 0;
}