前言 & 背景

CSP2024 游记（一年前文笔不好）

第

4

次打 CSP 了……

~~前 $3$ 次一个奖没拿。[捂脸哭]~~

初二了，这次再不拿奖要 AFO 了。

初赛

坐标 GX。

	J	S
分	68	60
线	37.5	37

考试时全身心投入，竟然没有睡觉。

~~看看这分数线，GX 蒻成啥了。。。~~

复赛

考前备战

考前一周晚自习几乎都埋在了机房，背了点二分动规搜索之类的模板，刷了点题。

考试当天

$07:20$ ，来校升旗广场。
$07:40$ ，大巴发车，前往考点。
$08:10$ ，到达考点，马上进考场。
$08:20$ ，调试一下 CodeBlocks，一切正常。
$08:30$ ，试题下发，开始考试。

J 组

T1 / number

一眼瞪出。

题面大概就是说给定一个只包含大小写字母和数字的字符串

s

，让你用里面的数字拼成一个最大的数。

思路就是用一个桶统计每个数字出现的次数，最后逆序输出即可。

number.cpp

CPP

#include<bits/stdc++.h>
using namespace std;
int t[10];
int main(){
    string s;cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]>='0'&&s[i]<='9')t[s[i]-'0']++;
    }
    for(int i=9;i>=0;i--)
        for(int j=1;j<=t[i];j++)
            cout<<i;
    return 0;
}

T2 / seat

题意：给出一个

n\times m

的考场，给出考场每个人初赛的分数，按分数由高到低如图箭头排列，求其中某个人的位置在第几列第几行。

可以暴力染色，但是这样就对不起标签里的“数学”了，所以我们推式子。

思路：先算出那人的排名

i

。

设

k=\lceil\frac{i}{n}\rceil

。

注意到奇数列由上往下填，偶数列相反。记

mod

为

i

除以

n

的余数，于是我们有

y=\begin{cases}mod&k=2s+1\land mod\not=0\\n&k=2s+1\land mod=0\\n-mod+1&k=2s\land mod\not=0\\1&k=2s\land mod=0\end{cases},s\in\Z

其中

y

表示行数，而列数

x=k

。最后输出

x

和

y

即可。

\color{red}\text{But!}

~~我赛时好像没考虑第四种，痛失 AC。~~

T1 和 T2 赛时大概 10min 想出正解，两题写完并测试一共用了 1h。（好像有点慢了）

T3 / xor

做完 T1T2，长舒一口气：应该有奖了。于是几口扒拉完早餐看 T3。

题意：给定数列

\{a_n\}

和

k\in\N

，定义

w_{l,r}=a_l\oplus a_{l+1}\oplus...\oplus a_{r-1}\oplus a_r

，需找出两个集合

L=\{l_1,l_2,...,l_m\}

和

R=\{r_1,r_2,...,r_m\}

，使得

\forall i\in[1,m]\cap\Z,w_{l_i,r_i}=k

并且

\forall i,j\in[1,m]\cap\Z\land i\not=j,[l_i,r_i]\cap[l_j,r_j]=\varnothing

，最大化

m

的值并求出。

正解 DP，可参考这篇题解，但是显然考场上的我没那么聪明。

赛时知道自己太蒻，于是专心写特殊性质 AB，即：

k\in\{0,1\},\forall i\in[1,n]\cap\Z,a_i\in\{0,1\}

这样原数列便退化为 01 串。

同时，下面的结论未经过严谨证明，纯考试思路，仅供参考。

首先了解一下异或的两个重要性质：

x\oplus0=x,x\oplus x=0

。

这里显然按

k

的奇偶性分类：

当 $k=1$ 时，答案即为数列中 $1$ 的个数。
当 $k=0$ 时，答案即为数列中 $0$ 的个数加上数列中连续两个位置均为 $1$ 的组数（注意 $1111$ 算两组，而不是三组， $11111$ 算两组而不是四组，这里显然是因为 $1\oplus1=0$ ）。

这题大概用 45min。

T4 / polygon

看看表：剩 1.75h，慢慢写也无妨。

题意：给定数列

\{a_n\}

，从中选择

m

个数构成另一个子数列

\{b_m\}

，定义一个子数列

\{b_m\}

是合法的，当且仅当

\sum\limits_{i=1}^mb_i>2\max\limits_{i=1}^mb_i

。求合法的选择方案数对

998,244,353

取模。

不出所料，果然还是方案数问题。

一般这种 T4 我都是直接暴力的，所以直接 dfs 每种状态，对于每个

a_i

选或不选，最后统计方案数，时间复杂度

O(2^n)

。（~~貌似好像有 24 分~~。

30min 解决。

尾声

最后花 1h 检查，造数据，死磕特殊性质。再花 15min 发个呆，最后 0.5h 小补了个觉就撤离了。

总结

这次 J 组的题应该算是比较简单的，橙橙黄绿，GX 一等线可能到 280+。

中午

$12:30$ ，恰饭（不好吃）。
$12:50$ ，听会歌，再看点模板。
$13:20$ ，有点困，睡个午觉。
$14:00$ ，起床，准备迎接绝望。
$14:20$ ，调试 CodeBlocks，一切正常。
$14:30$ ，噩梦降临。

S 组

T1 / club

给我看蒙了，这就是 S 组吗。

一开始想到是 dp，浪费 1.75h。后面发现推不出式子就转向部分分（真没想到正解是贪心），做了个特殊性质 A，打算写完 T2 回来补个 B。

特性 A 做法就是按

a_{i,1}

降序排列，然后累加前

\frac{n}{2}

项。

T2 / road

考完出来上洛谷天塌了：这是蓝题？！！

赛时瞪一眼看出 MST 变式题（~~其实不然是变异题~~），想着自己暑假集训记得最清楚的就是 MST，打算 0.75h 搞定。

但是实操后。。。怎么这么恶心！

（小插曲：init() 放在输入前面卡了 0.3h。）

一共足足磕了 1.7h，实在是给我干红温了，转头 0.3h 写个特殊性质 A，将权值设为直接走和绕虚点的较小值然后跑 Kruskal，但是大样例没过。

管不了那么多了，还剩 15min，T1 的特性 B 也别写了，先去写 T3T4 运气局。

T3 / replace

太急了没看题，看到样例 2，果断全输 0。

T4 / employ

Sometimes giving up is also a great choice.

总结

这次时间分配极度不合理，对于写正解过于自信了。

得奖应该是没希望了，吸取教训，下次争取。（~~如果还有下次~~

赛后

$18:40$ ，出考场发现教练给我们买了 KFC。
$19:30$ ，在考场边吃🍔边闲聊和骂题目了好久，现在大巴才发车。
$20:00$ ，回到学校，教室没几个人了。
$20:20$ ，拣好作业和衣服被子，回出租屋了。
$21:30$ ，开始写本篇游记。
$23:00$ ，洗个澡。
$23:20$ ，继续写。
$01:00$ ，终于写完了，睡觉。

结语

祝所有 OIer CSP2025-J2/S2 rp++！

CSP2025 游记

文章操作