CSP2025-J/S游记
define
·
·
生活·游记
前言
坐标JS
作者语文很垃圾，希望我所写的不会让你以为在读垃圾
人名转换:
def/rlq->@define
pqw->@pqw20
tbw->@possible981
hz->@TLE
jzl->IsJason(AFOed)
dyx->@_384A
hry->@yyyyyouhruu
这是我第一年来到省丹中，不过CSP报的还是八中。
今年初三了，目标就是能拿到J组1=，S组1=/2=就行。
已经是第4次参加csp了
初赛
2025/9/3 打了一场初赛模拟，73.5pts。侥幸被pqw拿捏。
题目很抽象，1.5h时间还是太紧了。阅读程序第二篇扫了几眼，5空全蒙，成功蒙对4个。倒数第二篇有4个空都是在用倍增求LCA，剩下一个是树上差分，成功错掉。tbw和hz也错了这个空。
2025/9/7 打了S组模拟赛(存疑)，体感比J组简单。2.5hAK。体感：红+橙+橙+黄
初赛J组比去年难多了，去年花了1h就写完了，今年花了1.8h左右，估下来90.5，wty估87.5,dyx估72左右。应该稳了。
出分了，是这样的，J93，S72
复赛
之后好像又打了2场模拟赛，一场220，一场10分（没有夸张)
Day-2
晚上在机房时，胡哲突然说了一了一句奇妙的话，他说:"Def，现在我们之中只有你有机会AK J组"我问他为什么，他说他们拿过一等的今年就不去J组，省丹中过去也没有过J组ak的，包括wmd，hry...
我想想好像也是对的，只不过我觉得我没有那个实力AK J组，除非CCF今年出题人全出红题，是这样的。
Day0
666星期六居然放假，这是很好的了，但是我们放不了...
每年经典节目：在大巴车上玩海龟汤，全场要么秒杀，要么猜不出来。
6：30到了酒店，环境还不错，先打了会ADOFAI，然后打了会ADOFAI，最后打了会ADOFAI。
顺便出去买点吃的，买了2块巧克力（总计120g），两瓶饮料，两块士力架，因为本人实在是太爱吃巧克力了。
睡觉的时候很快睡着了。
Day1
早上起来，听说Cyf晚上看柯南被吓死，跑到dyx床上一起睡了。
排队进考场，跟着志愿者走在路上，感觉这个路好长啊，还有点风，啊，啊啊啊啊啊啊啊（无端
这个考场相隔的电脑居然没有隔板，我很震惊。后来才发现显示屏上装了个特质的塑料（还是玻璃？），旁边人看上去就时和黑色一样
半小时看了一下4道题，后面两道暂时没想到怎么做，在1h时把t1,t2干掉了。
接着看t3t4
t4看着是dp的样子，还很像01背包，就优先思考，接下来是我的思考过程：
题意是给n个木棒，问你有多少种方案可以组成一个多边形。
要找到最大指比较麻烦，不如先从小到大排序，显然：
max_{i=1}^ja_i=a_j
便考虑当 a_i 为最大边时的方案数 s_i，
显然有：
ans=\sum_{i=3}^{n}s_i
我们的目标是求 s_i
因为要满足条件:
\sum_{j=1}^{m}a_{c_j}>2\times max_{j=1}^ma_{c_j}
考虑最大值为 $a_i$所以说
$$
2\times max_{j=1}^mi=2\times a_i
$$
带入上式：
$$
\sum_{j=1}^{m}a_{c_j}>2\times a_i
$$
由于小木棒都是排好序的，所以说其他所选的$c_j$都是小于$i$的
因为左边有$a_i$,右边也有$a_i$，两边同时就减去一个，即：
$$
\sum_{j=1}^{m-1}a_{c_j}>a_i
$$
理解一下，就是$s_i$的数值就是求在前$i-1$个数中有多少种方案相加使得和大于$a_i$。
我们会发现这样有些难做（也许是可以做的，但本人没有在考场上想到这种做法）。
可以注意到：
$$
s_i=2^{i-1}-前i-1个数相加的和不超过a_i的方案数
$$
我们只需要求出和不超过$a_i$的方案数即可，这就是01背包了，时间复杂度$O(na)$。
在2h时写完T4，开始思考t3
t3用了个很奇葩的算法，很像双指针但不是，主要用到了前缀和还有异或的性质，搞出了一个$O(n)$的算法
这时写完T3已经是3.3h了，极限测了大样例，都过了。
那一刻我感到十分舒坦。
又检查了一下freopen之类的
Excepted Rating:
T1:红
T2:红
T3:黄
T4:黄
停笔的那一刻，hz的玩笑话似乎真的成真了...AK这件事真的让我做到了？一切仿佛在梦境之中，我飞速跑出考场，背上包，从4楼蹦到1楼。
中午看了会luogu讨论版，发现都说t4比t3难，我感觉t4就一个下位黄，t3上位黄。
下午发现省丹中今年来的人是真的多，希望今年的hry可以AK吧
进考场的路上pqw预测今年题目绿蓝紫黑，~~我觉得并没有这么高~~
下午带了一整块巧克力(68g)和一块烤鱼饼还有一瓶饮料，这次居然有隔板了666，左边的人进来的时候塑料袋拎了一堆吃的进来，我问他是哪的，他说是常州。
题目下发，但是没戴眼镜看不清密码，被硬控10min（今年csp的密码真的太好玩了J组：WuHuaTianBao，S组：RenJieDiLing）。
0.5h看玩了题目，发现没有会做的题，去年还是有一道会的。
t1又思考了一会，想出了一个$O(n^3)$的dp暴力，骗到五十分，又把abc性质打了，拿到30pts,最终定格80pts
这时已经1.2h，赶紧思考t2。emmmmm，完全没思路啊。
只能暴力考虑每一个村选不选，然后跑一边最小生成树。时间复杂度$O(2^k(m+nk)log_2(m+nk))$,又把一个性质打了，一共56pts，发现已经2.5h了，赶紧开t3
突然发现t3是AC自动机，但是我好久不看，已经忘了，只能暴力+性质50pts走人
最终80+56+50+0=186pts，不知道有没有一等呢。分类讨论大法好，就是代码量有点多，前3题打了7k多字节，最后一题没来得及动。
hz居然估分200+，666，已经不是人了，不过我对我的这个分数已经很满意了，主要是被去年的发挥给衬托的
Expected Rating:
t1:绿
t2:绿
t3:蓝
t4:紫
好吧好吧，其实我自认为是不错的，只不过出的分还是出乎了我的意料：
J：100+100+75+100=375
S：65+0+5+0=70
所以我这一年的努力仅仅只是加了1级，J组也留下了遗憾。这一年我干什么了？
# 后记
## Special Thanks:
#### hz,pqw,tbw,hry,dyx,wty