NOIP2025 游记

· · 生活·游记

前

CSP2025 游记

Day -10

S 打成这样子也能去 NOIP 啊？

Day -1

和老蛋一起去，爽吃了 jzx 的披萨。

晚上 fsb 开会，说我喜欢绿色，怎么回事呢？

感觉会考树剖，看一下。

Day 1

拿下共享单车一辆。

发现和大量人一个考场，对面 jf 和老蛋。

密码一直错，怎么回事呢？

大概 8:35 开始看题，这个 candy 和 sale 怎么还有关联咧，tree 神秘感觉不可做，query 大 DS。

感觉 candy 简单，写一发，这个键盘怎么这么烂，换一个。

样例怎么假了，哦哦，看错题了。

然后发现这个循环节取最小就行，其他贪心取大的，简单，9:00 过了大样例，扔了。

你就说这个 sale 和 candy 有关联那难度肯定差不多吧，没事，我先看看 query，万一又有 32 是送的。

感觉可以把询问离线下来然后枚举区间搞一下，线段树推一下？好像是 O(n(n+q)\log n)，一看数据范围拿下 5\text{pts}，卡卡可以拿 15\text{pts}，这个太 low 了。

欸，枚举区间好像可以分块啊，每 B 个数一块，块内暴力枚举，多个块维护一下以左、右端点的最大值不就行了，好像是 O(nB\log n+(\frac{n}{B})^2\log n) 的，B=\sqrt[3]{n} 好像是最优的，可以做到 O(n^{\frac{4}{3}}q\log n)，稳拿 25，写写写，怎么假了。哦哦，有区间好像覆盖不到啊，那假了。没事没事，感觉这个做法很有前途，这还有送的性质 A,B，滑动窗口秒了，我先写 sale 再回来，大概 9:45，优势在我。

回来写 sale，但是以为 m\ge n 的答案是 \sum \limits_{i=n}^m C_n^{2n-i}，10:30 一直过不去大样例，哦哦，题读错了。

原来这个小 R 就是贪心策略啊，容斥一下，实际问你有多少种方案使得小 R 的贪心被 hack 掉。

考虑枚举 i,j,k 使得选 j,k 比选 i 更优但是选 i，然后发现这个不等式不成立，选 j,k 好像是一样的。我是不是把题读错了。撕，手模一把样例，此时 11:00。

哦哦，这个是选 i,k 啊，有点对，尝试枚举一个例子发现本质就是一个 1 把 2 堵上了，然后选了 1 选不了 2，这是不是正解？我突然感觉我要胜了。

11:25 发现上述做法在 m=2 时十分好写，11:35 通过所有 m=2 的大样例，感觉离胜利不远，然后老蛋上厕所归来，看起来他感觉不错，不会过 sale 了？没事没事，这 T2 长得就一脸人均题，我 query 还有思路呢，完全不慌，先写了再说。

12:00 写完，过样例 1，感觉要胜！但是样例 2 WA 了，不急不急。哦哦，没考虑 1 后面全是 2 啊，写完了，但是样例 1 WA 了，欸，怎么还会算重，改改改，过样例 1 但是不过样例 2 第四组，怎么少了 1 啊，哦哦，组合数算错了，改改改，怎么又过不了样例 2 第一组啊，不对啊，这怎么会是 23 啊，这怎么可能有 9 个 hack 啊？？？

12:30 想写个暴力验证一下，12:35 写完，欸？怎么重复数字还能争啊，瞪到了 12:45 无果，cinema，这要负了，赶紧把暴力和 m=2 拼起来，最后 10min 气势 query 做法没有写完，12:59 匆匆忙忙交上代码。

我好像忘记有 tree 这个题了。

出场看见 jf 六亲不认的眼神，他说他写完 candy 后冲 4h T2 最终保单，后三题只取 8\text{pts}，老蛋和 jzx 也是如此，不过写了暴力，有 151\text{pts}。

回去发现我 sale 我实际上写了性质 B 但是没看见，性质 A 和 m=2n-1 忘记判了，-28\text{pts}。

倒闭。