CSP-J/S 2026游记

· · 生活·游记

前提紧要:上海初一生,24年作为小学生参加了csp-J和S,爆炸了(J245,S10),后来改规定小学生没法参加了(悲)。

今年终于能再战csp了(喜)。

上午J组

T1,快乐地15min写完了(居然考场上注意到了没有E座)

T2,第一眼直接循环,然后看见数据范围 n\le2 * 10^5,a_i \le 10^9,吓哭了。 后来想到双指针调了30min过了(什么是双指针)

T3,按位贪心有点板了,总感觉打abc做过类似的(差点拐到01-trie去了)

T4,考场上模拟了几次样例,想出了一个神秘的线性dp,大样例居然过了?!

令dp_i表示 i 及以前有几个起点能让颜色a_i留到最后,递推式如下:

dp_i= \begin{cases} dp_{prv_i}+1+dp_{i-1}, & lst_{a_{i-1}}=i-1,\\[6pt] dp_{prv_i}+1, & lst_{a_{i-1}}\neq i-1. \end{cases}

其中prv_i表示颜色a_i上一次出现的位置,lst_i表示颜色a_i最后一次出现的位置。

大概意思是:如果i-1是颜色a_{i-1}的最后一次出现,那么以颜色为a_{i-1}的牌为起点,颜色a_i也能留到最后,所以多一个+dp_{i-1};否则只能继承上一个同色位置。

别忘了都要加上i自己作为新起点(+1)

最终,颜色 c 的答案就是 dp_{lst_c} 。

总分: 100 + 100 + 100 + 100 = 400(居然ak了!)

下午S组

T1,神秘能量水晶(X X XXX),前缀和+二分秒了,其实双指针也行,复杂度还更优 (但我是真不擅长写双指针啊)

T2,考场上0秒想到建图对线路点跑最短路,但是后来没看见1\le d\le 20,想到Floyd但以为会爆。

结果写了个Dijkstra,骗了68pts......

T3,想到个类似单调队列的部分分思路,但是细节有点多,暴力调挂了,0pts悲。 (赛后再看思路有点混乱,应该是错的)

T4,来不及了题都没看()

总分: 100 + 68 + 0 + 0 = 168

后记

J组好像没什么悬念(),稳稳一等。

上海的S一级线居然足足有183分,比去年涨了32分,差一点就一等奖了... (至少没写错freopen和文件名)

好在过了全国基准线159分,能去体验NOIP了(大喜)。

只能明年再战CSP了!下次我S要争取200+(小声)。

AI使用说明

本文中J组T4个人解法的部分,在写作完成后使用了DeepSeek辅助检查表述和拼写错误,作者根据建议自行进行了修改。