CCF CCSP2023游记
第八届CCSP全国总决赛 2023年10月25-26日 沈阳
序
自从5年前11月11日的NOIP2018原地退役之后，没再打过OI了
上了大学，没有进唐计的机会，转到了计算机之后也已经失去了打ACM的机会
打了三次CSP认证，编程竞赛打了两届蓝桥杯省赛+国赛，一次水赛（以及两次青云杯）
多多少少有些出于功利目的，保研加分，综测加分，课外学分……
总觉得缺了些过去打OI时候的味道
如今保研事宜尘埃落定，有幸获得了CCSP2023参赛机会
应该是自NOIP2018后第一次参加官方的程序设计竞赛
不知能否找回属于OIer的那份热忱
当初报名的时候以为只是一个单纯的算法比赛，仔细看看赛制之后才发现别有洞天
3算法题+2系统题，12小时超长战线，早9点打到晚9点，IOI赛制的NOIP-黑客松
之后得知被选入参赛名单是因为老师觉得大四写系统题会写的好hhh
不过能和校队ACMer一起比赛已经很荣幸了
由于之前搞软工课设，没拿出太多时间准备，只研究了一道历年系统题/性能题，根据性能实时评分还是挺新奇的（虽然青云杯也有）
题目
T1 装修（decorate）
有 $M(\leq10^4)$ 种素材 $a_1,a_2,\cdots,a_M$ ，这些素材共分为两种：
- 直接素材：可花费 $c_i(\leq10^4)$ 元直接购买
- 间接素材：只能用其它素材合成（合成无费用），一种素材最多只能作为一种素材的子素材，且保证不会成环。
此外，有两种特殊的素材获取方式：
- 共有 $P(\leq5)$ 个邻居，可用 $s_i$ 换取邻居的 $r_i$ 素材（单向）（交换无费用）
- 共有 $Q(\leq5)$ 个礼包，礼包价格为 $w_i$，内含 $k(\leq M)$ 种素材 $g_1,g_2,\cdots,g_k$
需求为 $N(\leq100)(\leq M)$ 种素材 $b_1,b_2,\cdots,b_N$
求满足需求的最小花费
T2 摸球（ball）
有 $N$ 种颜色的球各 $a$ 个，每种颜色的球编号 $1\to a$。
另有 $M$ 种颜色的球各 $b$ 个，编号 $1 \to b$ 。
求选取 $k$ 个不同颜色的球，其中任何编号出现次数都不超过 $s$ 的方案数（结果$\bmod 998244353$）
$1 \leq N , M , a , b , k \leq 10^3 ,\ \ s\in{1,2}$ 。
T3 次元波动平衡（surge）
一个长为 $N$ 的数列 $\left(a_i\right)$，要求选取其中最多 $K$ 个位置减去一个常数 $D$，使得到新的数列 $\left(a_i^{\prime}\right)$ 的最大子段和最小，求这个最小值，即
$$
\min \left( \max_{1\leq l\leq r\leq N}\sum_{i=l}^r a^{\prime}_i\right)
$$
$1 \leq K \leq N \leq 5\times 10^5 ,\ \ \ 1 \leq D \leq 10^9 ,\ \ −10^9 \leq a_i \leq 10^9$
（T4是一道编译系统题；T5是系统实现题，非性能题）
（题解部分见文末）
比赛心路历程
T1第一感觉是贪心，可以直接根据收益大小交换/买礼包
T2感觉正解dp，可以用组合数拿部分分
T3第一眼单调队列，k个修改似乎要线段树
T4编译系统题，果断放弃
T5给好了框架，像是程序填空，似乎是能写的
先打了T1的贪心，拿了60
后来换了几种贪法，骗到70，后无果，故搁置
T2先写了s=1的情况，拿到50
T3没想到什么好方法，暴搜了个10分
反复看榜，一直在200名左右徘徊
又回去搞T1，又交了10多发，依然是70……
打了T2的s=2,a=b的部分分，拿到60
午饭时间看T5，好像能搞
去看T5，题面很长，但是意外地很简单
下午的时间依次拿下T5的第一二三子任务，拿到70
最后两小时封榜，当前总分210，银牌线230
去搞T2的剩下的40分里的10分，一个组合数没想到直接A掉
忽然意识到T1的P和Q都只有5，1<<10只有1024，这不铁二进制枚举嘛
迅速重构A掉T1（早干啥去了*1）
最后20分钟发现第三题的“最小化最大值”
这不铁二分答案嘛（早干啥去了*2）
不过还是没想好怎样check，不断向前减D复杂度是$O\left(n^2\right)$，最多也就20分的样子
最终定格100+100+10+0+70=280分
后记
比赛刚结束稍微有些遗憾，感觉摸不到银牌线了。
不过终归是打完了12h的比赛，本科期间能参加一次这样的比赛，和各校大佬们同场竞技，结果如何已经不重要了。
赛后和本校的三位佬简单复盘了一下，发现T5的后30分其实很简单，被题面吓退了（早干啥去了*3）
上次感受这种氛围还是在高二OI机房里听佬们讨论题，颇为感慨
感觉赛中思路有些混乱，有些本来静下心来很容易想到的东西没有迅速反应到，反倒是比赛最终时刻出现了可观的思路，赛中还是心不够静，而且缺少“一定要把这题A掉”的决心。
第二天上午拿着CNCC参会证白嫖地铁票白嫖景点门票hhh
下午CCSP颁奖典礼，银线刚刚好280，惊险收获银牌（总算是没有重蹈NOIP2018的覆辙）
当然，也再次深刻地感受到了和佬们思维上 和格局上 的差距。
差距归差距，尽全力发挥到最好，战胜过去的自己，已经很满足了。
不虚此行，也算是为OI生涯画上圆满的句号了。
（emmmmm说不定 大四下天梯赛还去凑热闹？
Mathison 编辑 于2023年10月27日
题解
佬，您还真的翻到这里想看我的题解嘛？
我这么菜就算了叭
请移步我的大神队友 韦神的博客 叭
