CSP J/S 2025 游记寄寄寄寄寄寄寄寄寄寄寄

· · 生活·游记

今天去考 CSP 了……

寄寄寄寄寄寄寄寄寄寄寄了！

J

T1

题目大意

给定一个只包含小写字母和字符串 s。将 s 中的字母删去，并输出剩下能组成的最大数字。|s|\le10^6。

思路

简单贪心+排序。期望得分：100。用时：6\sim7 \min。

T2

题目大意

给定 n,m 和 \{a_i\}，按照 a_i 从小到大排序蛇形排座位，求一个人坐在哪里。1\le n,m\le 10。

思路

简单模拟。期望得分：100。用时：6\sim7\min。

T3

题目大意

给定 n,k,\{a_i\}，求最多能分多少个不交的子段使每个子段异或和均为 k。1\le n\le 10^5,0\le a_i,k\le 2^{20}。

思路

前缀和优化 dp。易得出 O(n^2) 转移方程：

dp_i=\max(dp_{i-1},\ _{j=1}^{i-1}dp_j+1\ (a_{j+1}\ \text{xor} \ldots \text{xor}\ a_i = k))

显然可以优化到 O(n)，记录前缀异或下的 dp 最大值。

期望得分：100。用时：13\sim14\min。

前三题做完只用了半小时。

T4

题目大意

求 \{a\} 的子集 \{S\} 的个数，满足 |S|\ge 3,\sum\limits_{i=1}^{|S|} S_i \ge \max\limits_{i=1}^{|S|} S_i。

直接暴力+\{a_i\}=1 跑路，期望得分：64。用时：30\sim+\infty \min。

总分

期望 100+100+100+64=364\ \text{pts}。

同校似乎都 $400\ \text{pts}$…… ### 难度参考（主观） 红红黄绿。 ## S ### T1 反悔贪心。期望得分：$100$。用时：$1\sim1.5\ h$。 ~~写了一个对拍，考试结束的时候才跑不到 $\sout{10^6}$ 组随机数据，~~ 不知道能不能过。 ### T2 直接暴力+特殊性质。期望得分：$[48,56]$。用时：$0.5\sim1\ h$。 ### T3 直接 `Hash`+暴力。期望得分：$[10,25]$。用时：$1\ h$。本来感觉可以想到更多部分分的，但还是不会。 ### T4 直接暴力。期望得分：$8$。用时：$0.5\ h$。 然后就真的不会了。疯狂想半天都想不出来。 ### 总分 期望 $100+[48,56]+[10,25]+8=[166,189]\ \text{pts}$。 $\text{update:}\ $ 貌似 $\mathrm{\text{€€£}}$ 的数据非常 $\color{blue}{\mathrm{水}}$，最终貌似高于最高预期。 同校似乎都 $300+\text{pts}$…… ### 难度参考（主观） [黄，绿] [绿，蓝] [绿，蓝] [ ? ]。 ## 总结 这次 CSP，炸 $\Huge{飞}\huge{飞}\LARGE{飞}\Large{飞}\large{飞}\normalsize{飞}\small{飞}\scriptsize{飞}\tiny{飞}$ 了。