CSP2025邮寄

· · 生活·游记

注：本篇文章中 day 0 为考试日。

day -inf ~ -1

一直在打摆，且在水橙到黄的题目。没什么好说的。

day 0

J

看到了题目名字，发现存在 xor，感觉是一个位运算离谱题目，不可做。还有 polygon，也感觉不可做。

开场先看了一眼 T1，直接把字符串内的数字提取出来从大到小排个序输出就做完了，直接秒掉。

T2 就是一眼模拟。把成绩按照结构体存储，按成绩从大到小排序然后模拟排位置就行了，因为 n\le 10,m\le 10，随便跑。

时间仅仅过去 40min，我还有足够的时间慢慢想 T3 和 T4。（话说 @yimao2013 1h AK，@齐芒 40min AK，我是不是太菜了）

T3 一开始我的想法是求一遍前缀异或和，然后把能构成 k 的建边，跑拓扑排序。然后，写完之后我发现一个重要问题：有环！（而且时间复杂度也是 O(n^2) 的）于是打算换一种做法。联想到 SCP S T1，是前缀和，差不多也是这种类型的题目。但是想了半天没想出来在那道题目上改什么东西。然后不知道怎么搞的，想到了 dp。令 dp_i 表示前 i 个数构成的最大答案。一开始 dp_i=dp_{i-1}，如果 a_i=k，那么 dp_i+1。然后枚举前面的所有点，如果异或前缀和求这段异或之后得到是 k，那么 dp_i=\max(dp_i,dp_j+1)。这样就是 O(n^2) 的了，跑了大样例，是对的。考虑优化。显然，dp 存在单调性，但是直觉告诉我并不需要二分，因为值域较小，直接拿个桶记着最后面的 j 然后直接求 \max 就可以了。大样例过了，时间复杂度 O(n)，应该能过。

赛后问了一车人 T3 全写的带 \log，出考场感觉会挂，实际没有挂。

T4 我想了半天没有想出来，于是打个暴力加上特殊性质走人。后面的时间就没事干了。

预期：100+100+100+64=364。

实际：100+100+100+40=340。

T4 特殊性质挂了，具体原因未知。

S

决心：切掉第一题。

实际：没切掉一道题，而且挂一堆题 QwQ。

T1 上场打了个 O(n^3) 的 dp，然后又瞎写了点特殊性质，然后思考无果后先看下一题。

T2 的 k=0 我看了一眼是 MST 板子，然后敲了一个 MST 板子然后乱搞的一个做法就走人了。

T3 是我最不熟悉的字符串，写了个卡评测代码：

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;

signed main()
{
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(true){
        cout<<"I AK IOI!\n";
    } 
    return 0;
}

对应考号 HN-S01291，欢迎把我加入迷惑行为大赏。

T4 暴力走人。

剩下的时间全在玩，没有检查，导致最后的成绩及其差，以后不能不检查代码了。

我写过最短的邮寄（特指 S 组）虽然我在这之前只写过一篇邮寄。

预期：60+16+0+16=92。

实际：55+0+0+8=63。

出分发现很多人都 J 组 AK 了，S 组 T1 过了。我能不能考虑 AFO 呢？

感觉是没检查导致的，但是 T2 MST 板子为什么 0 分就很奇怪了。

认真反省为什么 S 组挂分这么大！