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日

题解#

佬，您还真的翻到这里想看我的题解嘛？

我这么菜就算了叭

请移步我的大神队友韦神的博客叭

CCF CCSP2023游记#

序#

题目#

T1 装修（decorate）#

T2 摸球（ball）#

T3 次元波动平衡（surge）#

比赛心路历程#

后记#

题解#

文章分享

目录