2025ccf非专业级别收容能力认证游记

· · 生活·游记

上午

J组

8:00

进了考场

哦我座了半天原来进了考室就能打缺省源了

8:30

发了密码 上善若水

T1怎么这么简单秒赤 T2怎么这么简单秒赤

T3怎么这么神㊙ 这个区间一看就是前缀异或， 选了区间直接贪心区间覆盖秒赤

此时是8：30 稳啦！

T4看起来是一个神秘dp

首先dfs有40pts， 特殊性质a_i = 1有24pts, 有特殊性质想到计算那些不合法的答案 。9点多的时候写出了一个O(n*a_i^2)的dp， 有80pts

然后开始疯狂组合数学+sleep(10000)

11点多发现要寄了T4这么简单一定很多人AC

11：30发现只需前一段dp后一段dp拼到一起 空间复杂度是O(16n^2)

11：45AC了

出了考场发现有一亿个人AK了

下午

到了下午zjy说ccf换评测机了，比 becoder 还快。

S组

我学会了！一进考场就开始打缺省源

打开题面， T1 应该是贪心， T2 应该是 MST， T3有神秘字符串，T4看不懂

T1 很快想到一个贪心，每次放兴趣最高的， 但是满了该怎么处理？把最小的弹出来？怎么再放进去？我当时以为会有多个满的。想了半个多小时觉得要炸了去想T2。

T2看起来是最小生成树，非常慌忙地打了一个 O(2^k(m +kn)\log_2(m + kn)) 的暴力和测试点1~4。

此时已经过去了一个小时了，我一看布什哥们怎么一个小时了才40+再不切 T1T2是不要原地去世了赶紧回去看 T1。对着样例虚空调试一会发现只要一个满了其他的就都不会满直接优先队列维护即可。

光速 AC 了 T1 , T2 想到可以先进行一次 MST 把时间复杂度变成O(2^k(kn + m)\log_2(kn + m) 但是RE了。不得不先大了A性质，

再写T3。T3一看是一个很神秘的字符串，要进行多次匹配。这个时候我突然想起了kkk的《深入浅出》里写到了 AC 自动机可以同时匹配多个模式串。但是我不会！只得写了一个哈希的暴力 O(nq + L_2^2) 。

T4 像 dp ，我好像见过一些关于顺序的 dp， 然而我从来没有做过。考场的我没看见c_i \ge 0的条件于是自信的打了32pts的特殊性质。然后继续看T2。

在还剩没多少的时间里，我注意到可以先进行一次MST再枚举即可把时间复杂度优化至O(2^knk\log_2nk) 获得80pts。

但是， 我建的虚点是全为0，并且由于神秘原因误认为它TLE了只有40+，于是开始使用随机化(???)并且神秘的过了1~3的大样例。又测了INF秒发现原来不会TLE并且获得了80pts。之后就没有写出其他分了。

预估：

J : 100 + 100 + 100 + 100 = 400

S : 100 + [80, 100] + 25 + 32 = [237, 257]

反思：

J和S都没有很认真读题，特别是S

到了 2~3h 的时候也有些懈怠了， 蹬着屏幕发呆。

Update:

官方成绩： J : 100 + 100 + 100 + 0 = 300

S : 100 + 80 + 25 + 12 = 217

J组因为T4 dp MLE了 -100pts

S组T4因为没看到c_i可以等于0 -20pts

不过S依然是全机房rk1

坐标CQ， J0566， S593， 希望能上迷惑代码大赏（虽然一点也不迷惑）