四川CSP-S2025游寄 暨 退役前的回忆录

· · 生活·游记

坐标：SC xdyz（初中在qzby）
Grade：高一
去年S:140 2= J:220 2=
考场：成外高中部
微信：DreamofAKIOI0890，欢迎聊天（这个微信号很OIer了）
结果：11*(45-1)/4 （121） :::::info[考试前的事情]

Day -1 在xdyz机房

白天6节自习课（4数学+1心理+1体锻）。作业写完了，好耶，可以在机房泡三节晚自习了！！
啊啊啊怎么刷了1节课bilibili，水了1节课讨论区？？？
小崩。
::::info[废话] 一直在听歌，还在听未闻花名，哈基泽你这家伙（@cxzcxzcxz），你还记得那些属于OIers的留校晚上的时候，小学部台阶下的钢琴么？你，还有你们，多久之前就离开了，现在到了高中，竟然仅剩我一人了。你们还看得见么？列表里的灰色名字，承载着多少的故事啊。
初中机房旁边的小天台现在是什么样子了呢？快要CSP了，还会有OIers在那里吹着风聊天么？ \ 今年再拿不到1=我也该退役了吧。（悲） :::epigraph[一期一会·未闻花名 周深] 我们将奔向各自的那片碧海蓝天，而这是远行前最后告别。谢谢你曾陪我走过那岁月，我知有太多人太多事。 :::
\ 去成外也算是故地重游了，既是开心的也是伤心地。曾在这里集训共计约一个月。第一次是和 wyz leq wwy xwt 一起去，在初中部，虽然被各种大佬虐爆了，但和朋友一起还是很开心啊。一群人在食堂聊着自己的梦想，我说我要AKIOI然后回qzby当信息老师，让这里的学生不用再扣上强省弱校的帽子。

第二次就是独自一人在高中部训练了，依旧被虐爆，略显孤单，但是谢谢来自重庆的室友cze和zzh的鼓励，以及集训教练该校NOI银牌大佬mzx。怀念一起打CS、MC的时光。
:::: \ 许多whker觉得一个OIer怎么样怎么样，但是我只是一个普通的OIer。我试图向别人讲述我的全世界，却一次又一次的失败。这里是我1/3的世界，我将它放在这里向你们讲述了。如果要以我的OI生活做一个墓碑的话，这篇文章就算是墓志铭了哈哈哈。
\ 第三节课在讨论区和游记里过去了。明天要过一过模板，过过线段树ST表和最短路。还有什么要过的？想不起来了。好烦啊啊啊啊。
\ 会有人看么？

Day 0 在xdyz机房

总算是干了一点正事，过了一下线段树和Dij，学了一下Manacher。Dij调了半天发现大小于号写反了。然后水了一会讨论区，又是几个B哥和几个可怜的孩子呢。
突然想起来NOIP非0即进，苦日子突然增加一个月，加油吧。好累啊。 ::::success[疯话] 好累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累累啊！！！！！！！ :::: 手机没电了，回寝室充电了。（谁TM考前一晚上还在学校啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊）。
心态小炸，但愿rp++。
全部毁灭吧 :::::

正篇：考试当天

:::warning[吐槽] 谁家好人S组出绿蓝紫紫啊，没吃过21年的苦在25年吃是么？？？S组靠绿蓝紫紫NOIP考什么？？这么想要选拔人才考四道黑得了，NOI都不用比了！！！！ （日常发癫不要介意） ::: ::::info[非代码方面的考试个人经验] 拿了三瓶乐虎和五包苏打饼干，饼干没有怎么吃，瞪着题目越瞪越想要骂人，一怒之下给三瓶乐虎喝完了。然后……进入了一种奇妙的状态，像是 喝醉了 ？？然后虽然没有思路爆发，但是敲代码调代码效率upupup。 :::warning[但是这种方法也有弊端]{open} 首先，我在考试时脑子微微有一种清醒的发昏，可能不会那么容易想到正解。然后是考试后的副作用，我在地铁上有点晕，回家后又困又睡不着，模糊又清醒地打瓦刷抖音看番看到早上八点，其中几次想要关闭电子产品睡觉，可是关了之后还是根本睡不着。去年本人考CSP时更猛，JS双打，一天喝了5瓶乐虎，第二天晚自习直接吐了。
谨慎，谨慎。 ::: ::::

T1 期望得分：75pts result：65

一眼贪心，但是就是不知道怎么贪。瞪了20分钟除了要用贪心没有一点关于正解的想法，于是开始研究子任务，最终共计花了大概1.5-2h打了各子任务，最终提交代码长度（包含注释代码，注释思路，代码中的疯话）约4000字符，也是神奇。

:::info[直接将数据范围复制过来]

::cute-table{tuack}

测试点编号 n= 特殊性质 做法
1 2 无 直接判断
2 4 ^ 暴力DFS
3, 4 10 ^ ^
5 \sim 8 30 ^ DP
10, 11 200 ^ ^
9 ^ B 贪心
13, 14 10^5 ^ ^
12 ^ A 排序，贪心选择
15, 16 ^ C while(1);
17 \sim 20 ^ 无 ^

特殊性质 A：对于所有 1 \leq i \leq n，均有 a_{i,2} = a_{i,3} = 0。

特殊性质 B：对于所有 1 \leq i \leq n，均有 a_{i,3} = 0。

特殊性质 C：对于所有 1 \leq i \leq n，1 \leq j \leq 3，a_{i,j} 均在 [0, 2 \times 10^4] 中独立均匀随机生成。 ::: :::info[n=2 时，5pts] 只有两个人，肯定是一个人去一个部门另一个人去其他部门，直接枚举所有6种情况即可。 :::

:::info[n\le200 时 暴力DP，25pts ] 状态 f_{i,j,k} 表示考虑前 i 个人，其中部门1招了 j 个人，部门2招了k 个人，则部门3招了 (i-j-k) 个人，其中： j,k,(i-j-k) \le i,\frac{n}{2} 。
\ 转移方程式：

f_{i,j,k}=max(f_{i-1,j-1,k}+v_{i,1},f_{i-1,j,k-1}+v_{i,2},f_{i-1,j,k}+v_{i,3})

::: :::info[特殊性质A 贪心 5pts] 明显的贪心，选择 frac{n}{2} 个满意度最大的就可以啦。 ::: :::info[特殊性质B 贪心 15pts] 贪心依旧很明显的，但是以什么为标准来排序呢？ 像特殊性质A一样，以这些人对某部门的满意度排序吗？看这组数据：

11 9 0
10 1 0

以这个思路，应该将第一个人放到部门1，第二个人放到部门2时，此时总满意度为12 但是，将第一个人放到部门2，第二个人放到部门1时，总满意度为19才是最优。 那么第二个方案凭什么牛逼？观察发现，是因为第二个方案是以一个人关于两个部门的满意度之差排序的。 这个就是正确解法啦。 ::: :::info[正解 贪心 （主包在考场上居然没有想出来呜呜呜）] 如果先将每个人放到他们想要的部门再做处理，这时不考虑人数限制，记录总满意度为 ans1 。
由于人数限制是一半，那么至多有一个部门会超出人数限制，那么就要选一些人放到其他部门去，这时会有一个代价。 仔细想想，是不是跟特殊性质B的做法很像？只要将特殊性质B的做法推广即可。 :::

T2 预期：48 结果：48

后面就不是题解主要是思路啦毕竟主包很fw
看T2的时候已经过了1h，主包居然忘记在开始时过一遍全题面啦！
看了一眼，咦？最小生成树板子出到T2啦？还是在这么难的T1后面？
结果想多了
:::info[依旧放数据范围] ::cute-table{tuack}

测试点编号 n \leq m \leq k \leq 特殊性质
1 \sim 4 10^4 10^6 0 无
5, 6 10^3 10^5 5 A
7, 8 ^ ^ ^ 无
9, 10 ^ 10^6 ^ A
11, 12 ^ ^ ^ 无
13, 14 ^ ^ 10 A
15, 16 ^ ^ ^ 无
17, 18 10^4 ^ 5 A
19, 20 ^ ^ ^ 无
21 \sim 25 ^ ^ 10 ^

特殊性质 A：对于所有 1 \leq j \leq k，均有 c_j = 0 且均存在 1 \leq i \leq n 满足 a_{j,i} = 0。 :::

注意到#1\~#4的 k = 0 ，坏了，真让主包写上板子了。
写完板子偷到16pts快逃啊
注意到特殊性质A，\forall j c_j=0 \text{?} \exist i \in [1,n],a_{j,i}=0
这可以转化成板子啊！再看看时间复杂度，可过！！！ 骗完48pts后主包就逃了，这次是真的逃了

\color{white}\text{为什么主包的游记偷感这么重啊，为什么呢？}

T4（T3字符串不想做）结果：4pts

一眼DP+容斥，但是主包不会
:::info[依旧复制数据范围]		 测试点编号 n \leq m 特殊性质
1,2 10 \leq n 无
3 \sim 5 18 ^ ^
6 \sim 8 10^2 ^ A
9 \sim 11 ^ ^ 无
12 \sim 14 500 =1 ^
15 ^ =n ^
16,17 ^ \leq n A
18 \sim 21 ^ ^ B
22 \sim 25 ^ ^ 无

特殊性质 A: 对于所有 1 \leq i \leq n，均有 s_i = 1。
特殊性质 B: 在 s_1, s_2, \dots, s_n 中最多只有 18 个取值为 1，即 \sum_{i=1}^{n} s_i \leq 18。
::: 特殊性质A看起来很好骗的样子，因为每天的题都easy，所以，答案是n!
骗完后主包跑路了
但是现在看来，#1-#5暴力也很好拿，允许DFS启动（但是主包喝醉了脑抽没打）

T3（主包最后1h决定不留遗憾还是打了T3）结果：5pts

一堆string？看起来还要匹配？
一眼自动AC机AC自动机，主包已经998244353年没有打过这玩意了，只能打打暴力
特殊性质B似乎很好打，对一个字符串，只需要记录‘b'的位置和总长度。 那对于一个替换方案，所有b的位置差相等的可以放一块，再逐个判断。然后就跑路了。 主包也不知道主包为什么那么爱特殊性质，甚至连小数据都没打，可能脑袋太昏了。

如果代码不炸的话

坐标SC，估分150-165pts。等NOIP吧 :::info[最后的最后] 主包的微信DreamofAKIOI0890，欢迎聊天，记得备注你是谁。 主包也很废物啦，但是很期待和人聊聊天，也想看看别人的小世界是什么样子。 :::

但是代码炸啦哈哈哈哈哈哈

::::warning[] :::epigraph[] 夜太深，心跳呢？ :::

\color{white}\text{ 炸啦哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 呵呵哈哈哈 哈哈哈哈哈哈哈哈 【数据删除】，【数据删除】} €€£ \text{，你【数据删除】，【数据删除】，【数据删除】【数据删除】【数据删除】。把T1放简单一点会【数据删除】吗，啊？？？？？？ 注意到不可以写tang字，所以： 我是【数据删除】人。 已经经过和谐。然后继续发疯： 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 全炸啦 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 全部毁灭了 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈呵呵呵呵呵呵呵呵呵呵哈哈哈哈哈哈哈哈哈哈呵呵 呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜 三年了，两个J2=，两个S2=是么？？？？？？？？？？？ 哈哈哈哈哈呵呵哈呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵 呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜}

::::