真 CSP 2025 游记

过往业绩与分析预测。

Day -x

Day -1

Day 0

Day 1

• 哈夫曼树是啥？我记得深入浅出的描述是 if else 区分不同的选项，权值应该就是每个选项出现的频次 * 确认到这个选项要经过多少 if else 的和。启发式算法（就是脑子感性理解）手玩出了 186，感觉不会更优，直接选了。
• $n = 8$ 你的意思是要我手算 $336$ 个三元组？直接使用 $\gcd$ 的定义，组合计数得到 $25$。这么小？我不信，又暴力手算了一遍，找了半天错发现确实是。最开始很不想算，想直接蒙 A/C 的。
• 最后那个函数交互题属实不会，不过也只错了第三个。赛后发现原题是黑，ARC070D，高深莫测。

Day $eps$

重置 Day 1 的定义是 2025/11/1。

Day -1.152922e+018

Day 0

Day 1

CSP-J

• 生成“命令行中运行程序生成文件和比较文件的命令”的脚本、
• T3 的数据生成器、
• T4 的数据生成器、
• T4 的多测形式、
• T4 的暴力的多测形式、
• T4 的 $\max_{a_i} = 1$ 性质的多测形式、
• T2 的通用 $O(1)$ 求解函数。
• luogu uid: 1096384（和 $1048576$ 有点像，不信你仔细看）
• freeopen,froopen,froepen
• #include<bits\stdc++.h>
• 我常常追忆过去
• Genshin
• 所有的样例名称
• 题目类型：传统型、传统型、传统型、多边形
• 上述所有内容全贴注释里面了

• T4 搞了老半天没拍出问题，最大的点 0.5s。
• T3 造完输入数据，在命令行生成输出时发现有些输出是 0 KB，吓哭了。
  我想到如果 RE，命令行是不会报错的，但是程序提前结束，导致没输出或者不完全。一进去测，真是 RE，吓哭了。
  我仔细检查，发现 lst 数组只开了 500050，但题目给定的是 $a_i < 2^{20}$。感谢上苍保佑，这确实挽回了 30pts，能让我阿克，要不然我明年还得再来一次再坐两个半小时牢。
  于是我把数组大小改成了 1000050。
  再测，果真 RE 消失了！也有输出了，点进去看看！
  等等，为什么随机数据，$n = 5 \times 10^5$ 的情况下，答案 $ans$ 是 49????，四十九万多啊？？？
  我今天运气真是太好了，纯随机数据都能给我造出来这么强的样例！
  再看看输入文件，却发现我怎么凑也凑不出来四十九万多个互不相交的异或起来是 $k$ 的区间，吓哭了。
  我猛的想起 $2^{20} = 1048576$，显然是 $> 1000050$ 的。但是居然没报错，它只是静静地告诉我，这里确实有四十九万多个互不相交的异或起来是 $k$ 的区间。
  我本来准备把它改成 $105 \times 10^4$，与《热爱105度的你》相得益彰，后来想了想还是改成 $2 \times 10^6 + eps$ 吧。
  其实现在想起来，我应该改成 $2.1 \times 10^6$ 的。
  终于它诚实地告诉我，只有四百多个区间了，就像我这场考试，不出意外的话也只有四百多分了。

CSP-S

• T1 用了 40 min+？或者一小时。
  思路方向正确，但似乎做复杂了，做成了 hard ver 级别的，可以把 $\frac{n}{2}$ 替换为任何有解的值。
  看上去和很多人做法不同，其实可能是本质一样的东西。但具体怎么我也不知道。
  没来得及对拍，只把大样例过了。我没有给小 n 专门写 DP 的子任务，因此一旦挂分就是挂一片，至少会少 50pts。
• T2 这个 trick 我平时就研究过，还出过题。所以略想了一下就秒掉了。
  被卡常了，写了一个基于 queue + vector 的大常数归并。
  复杂度不仅要乘 log k，还要乘 6 倍常数。本机 1.7s，可能要挂 20pts+。
  考场上没想到直接预先排序，然后直接提取子序列（ljy 做法）。这个是没有任何风险的。
• T3 知道是 trie 树（注意到逆天的空间限制），但是不会正解。
  转化到最后甚至需要变成字符集大小为 $26^2$ 的随机数意义下的 trie 上前后缀二维数点（注意数点部分是不连续的，也就是两维度选择的点要看做是纯随机数）
  所以写了一个任意可能分数的部分分做法。
  核心问题：样例弱，并且出现了灵异事件。
  在自己造的（具备 B 性质）的数据上，B 性质的子任务做法和正常做法两个东西输出不一样。正常做法会输出一堆 0，B 性质子任务则至少输出五位数。所以至今生死未卜，我只记得大样例都过了（这个来源不可靠，由于后面的灵异事件，我不确定我是否误触而变更了代码），第三个样例跑了 6s。但显然这不是正解，它是 $O(q \times |input|^2)$ 甚至很可能更高的。并且不管是 B 性质模块挂了还是正常模块挂了，都是我完全不能承受的挂分。
• T4 是唯一有把握的，能够稳定拿 20pts。但也并没有真正的把握，因为我只测试过 n=10 的样例，从未测试过 n=18 的情况。所以具体怎么样仍然是个未知数。
• 所有题我都没有切到 Linux 测试能否过编译。

你都已经学了两年 OI 了，已经是初三的中老年人了，所以没啥资格和理由说以自己学的时间短为借口的。

那你今年 J 组不阿克，S 组不是 3 打头，NOIP 没 1=，你不就白学了吗？你不就是 sunjioker 吗？

还说去重开中学的极客版进修了一年，然后破产倒闭成这个样子。

闲话

回到文章开头的分析预测，你会发现其实后面几个题基本预测对了。不管是难度还是知识点还是分数。

Day UKE-1

Day UKE

• NOIP 线（~rk 320）今年约 150pts。
• CQ 1=（~rk 210）今年约 210pts。
• 对照去年数据，6 钩对应 ~rk 353，今年约 128 pts。
• 7 钩对应 ~rk 243（此处按去年洛谷线 221pts 计算），今年约 200pts。
• WC 线对应 ~rk 99，今年约 272pts。