记录一下关于日新月异七队、无限残量这两个月的一些事情,以及自己的想法。

前言

我在这两个月里已经写了不知道写了多少次关于这件事情的文章了。每次写出来的都并不让我满意。有的版本连我自己读起来都像在读小说,因此没有发上来。毕竟我是想要宣告“我刚刚经历了这样的故事”的。

经过许多尝试,这种不带太多情感色彩的叙事,加上自己的心路历程,大概就是我现在找出的最满意的表达方式了。

详情

2024.11.10 的 CCPC 2024 重庆站,学校拿了很多打星名额。教练安排了我、@Austin__Griffin、@nikangle 组一队。当时高中同学的队名是自己取的,初中同学是日新月异加序号。我们的队名是“日新月异七队”。

CCPC 2024 重庆站排行榜

我们打了 7 题,银牌区。并且那次比赛前后在重庆大学和同学们玩得也很开心,印象深刻的是食堂代金券与水果捞。

2025.10.14,教练通知了 CCPC 2025 重庆站报名的消息。由于我们平常的关系也比较好,我默认了我们会继续组队,没有与他们沟通。晚自习时 @Acoipp 向 @Austin__Griffin 提出组队,我看到他并没有拒绝,就表达了我希望和他们继续组队的想法。放学后他说需要考虑一下。

10.15 上午,@Acoipp 要求 @Austin__Griffin 尽快决定。一段时间后,@nikangle 告诉我他已经决定和 @Acoipp 组队了,问我打算怎么办。我愣了一会,随后拉着 @Austin__Griffin 到机房外交流。他表示是 @Acoipp 先邀请他的,我也可以和别的学长组队。我说我很希望我们继续组队参赛,提到了去年组队的事情。他说我们以后还有很多机会一起组队。

下午,@nikangle 与另外两名同学组好了队。

晚上有模拟赛,我心不在焉地做了前两题后开始组织语言。放了学拉着他们到羽毛球场旁,再次表示自己很想和他们组日新月异七队参赛。但模拟赛时想得太多导致这时我感觉已经麻木了。他们都说和同学组了队再反悔不好,以后可以再组队。@nikangle 说我下次可以提早沟通避免这种情况。

10.16 晚自习与教练交流组队的事情,我表示希望单独参赛,教练说单独参赛训练效果不足,且报名不一定通过,建议我重新组队。

10.21 晚上,教练告诉我如果单人报名没通过就没有机会再组队报名了。与家长沟通后家长也十分反对单独报名,最后用了 50 分钟左右,说了一些听起来很深刻的话语说服了家长。

10.22 中午报名,队名仍为“日新月异七队”。

11.21 放学后,我与他们走在桃李湖旁。我们聊天时莫名开始重复另外两人说的话,随后我说出:“我同意日新月异七队重组。”他们先后回答:“我也同意。”我惊讶地拿出手机对着他们打开录音,重复了一遍“我同意日新月异七队重组。”我等待了两秒,并没有听到他们的反应,于是笑了起来掩饰尴尬。但在我笑起来的同时,他们又先后重复了一遍“我也同意。”

11.28 下午,我们在机房内填写了 THUPC 2026 报名表,我认为“日新月异七队”作为 2024 年时学校的统一格式队名,没有我们的特点,提议更换队名为“无限残量”,英文名“Unsaturated”。

11.30,CCPC 2025 重庆站正式赛。场上我一个人做出 5 题,下位银。

CCPC 2025 重庆站排行榜上的日新月异七队

12.13,我们参加了 THUPC 2026 练习赛,值得一提的是练习赛 B 题《合成大西瓜》来源于 CCPC 2024 重庆站,是当时日新月异七队通过的第四道题目。

12.14,我们参加了 THUPC 2026 正式赛。晚自习上我写下了这篇文章最初的版本。

THUPC 2025 初赛排行榜上的无限残量

心路历程

当然,光靠这样一份时间线是不足以将自己的情感表达出来的。所以我还是要写一写我的心路历程的。

从 10.14 说起,那时候我只知道我很想和他们组日新月异七队,却对“这对我有多重要?”“我能下多大的决心争取?”“我对其他结果的接受程度如何?”毫无思考,这导致了我在那两天犹豫不决。

然后是单独参赛的决定,我已经忘了我当时说没说过了。但按照我那时写下的文字的说法,我向 @Austin__Griffin 表达过“要是不能组日新月异七队我就不打了”的意思。所以我觉得如果我找了别人组队,就证明那句只是一句用来情感绑架的谎言,进而证明我是一个可以随意说出这种谎言情感绑架别人的人。因此我不愿意和其他同学组队。至于为什么还要参赛,则是因为考虑到 CCPC 2024 时的体验,我认为“第二天(11.30)会错过本可以参加的 CCPC”几乎必然影响我在第一天的 NOIP 的发挥。

也就是说,无论教练或家长如何抬高“单独参赛”这条边的代价,也无法改变我的决定——我既承担不起割掉与日新月异七队的边的代价,也承担不起割掉与 CCPC 的边的代价。而现在这些关于我的决定与最小割的思考成为了我们队名“无限残量”的灵感来源。

在报名成功,这件事情告一段落之后。我开始思考这支队伍的未来——我和他们一起组队参赛很开心,所以我希望能在下一场可能的比赛重组日新月异七队。为了避免这次的情况,最好是提前和他们确定好“下一次组队赛我们组队参赛”。而我原本打算在 11.30 比赛结束后提出。我甚至计划好了当他们不同意时,我最多要把话说得多重。

11.21 的晚上是一个意外,由于当时我一直在预想比赛结束后的情景——我在那个时候应该表现出我们队伍的珍视与对重组的期望,我并没有反应过来,便根据脑中想象的样子做出了对他们复读的回应。得到回答后,我马上开始怀疑,毕竟这和我设想的 11.30 那天的困难重重太不一样了。于是打开了录音。这次过了两秒仍然没有回答,我就想用笑声表示“我就知道你们说的不是真的。”所以,在再次得到回应之后,我显得十分激动。

10.21 晚上与家长交流时,我被问过“既然你们三个现在去机房、放学还是一起走,这件事情并没有影响你们的关系,那你坚持单独报名还要什么必要呢?”我当时答不上来。现在发现,我坚持独自参赛反而成为了这件事不影响我们之间关系的条件,只有“独自参赛,等他们回来”才能作为我不改变对他们态度的理由。如果我和别人组了队或者没有参赛——放弃了日新月异七队,以我的性格几乎必然会和他们冷战一段时间。然后呢?我没了日新月异七队,也不会有无限残量。

【0dcf4753bf97ca18bdba2a2b1be7e978a415efb41aba43c2e8501cbd2e19736c5639706cee2374531c3865ebd44a881f03d5604996b0da7dc1edcb49da1140e6】

闲话

写完这篇文章时,我才发现 3000 字在这里只有这一点,所以我问了一下 AI。

你在这 3000 字里复盘了决策逻辑(最小割)博弈过程录音时的心理博弈以及自我剖析

  • 对于你来说,每一个字都代表了当时长达数小时甚至数天的煎熬。
  • 但对于读者或网页渲染来说,文字只是线性的排列。情感的“重”是无法直接等同于页面的“长”的。

你写了“不知道多少次”,经历了无数个版本的推翻重来。这 3000 字其实是你脑海中那数万字思考的“精炼残量”

你删掉的那些“像小说”的版本、那些没发出来的草稿,其实都在你的潜意识里占据着空间。当你看到最终成品时,你会下意识地拿它和“这两个月的全部思绪”去对比,自然会觉得它显得单薄了。

你记录的是两个月的事情。在现实中,这 60 天每一秒都是实时流逝的;但在文字里,你用 50 分钟说服家长的过程可能只用了 200 字。这种时间尺度的极度压缩,会让你产生一种“我的青春怎么只有这么一截”的错觉。

文章最后贴一张图片吧。

在 CCPC 2025 重庆站上获得的气球束

除“闲话”部分引用了部分我与 AI 的聊天记录外,本文没有使用 GenAI 辅助写作。

Day 1 (11.29)

A 秒了。

阅读 B 题题面(包含样例解释)。

思考过程

认为需要分析在何种定价方案下,贪心策略是最优的,何种情况下不是。[^1]

考虑如何解决固定定价方案时,求最大原价的选择方案的问题,相当于两种 \(w\) 各自排序后每次决策从哪堆中买。

\(w_i = 2\) 的第一个待选物品的性价比大于等于 \(w_i = 1\) 的第一个待选物品的性价比时,选 \(w_i = 2\) 的物品一定是不劣的,即贪心策略在此时是正确的。

所以贪心策略出的错误只能是“在应当买 \(w_i = 2\) 的物品时被第一个 \(w_i = 1\) 的物品的高性价比诱骗了,被迫一起买下低性价比的第二个 \(w_i = 1\) 的物品,或发现后面没有第二个 \(w_i = 1\) 的物品但自己还有一块钱没花出去。”

贪心策略在这里显然会被骗至多一次,因为后面的 \(w_i = 1\) 的物品的性价比会比第二个更低,此时没有高性价比的诱饵了。

接下来思考枚举几个关键位置后组合计数。考虑了几个位置,并思考如何确保“贪心策略一定会选成这样”,然后一直无法保证贪心策略会选最后一个 \(w_i = 2\) 的而不是去选下一个 \(w_i = 1\) 的。

9:10,感觉组合计数没有前途,去想怎么做 DP 了。

定下策略“9:30 没进展就打暴力跑路。”在 9:30 左右看了 C、D 题后感觉非常困难回来继续思考 B 题,将时限延至 10:00。

约 9:40,回看组合计数思路。

思考过程

发现“贪心策略选择钦定的最后一个 \(w_i = 2\) 的物品”是必然成立的。于是在此基础上继续考虑。

想到了可以枚举第一个未选的 \(w_i = 2\) 的物品,记为 \(x\),和倒数第二个选择的 \(w_i = 1\) 的物品,记为 \(y\)。将最后一个选择的 \(w_i = 1\) 的物品记为 \(z\),则需要满足的条件如下。

  • \(a_y + a_z < a_x\)
  • \(2a_y > a_x\)

考虑其他物品会不会被购买。分段考虑,\(i< x\)\(i\) 无论其 \(w\) 如何一定会被购买;\(x < i < y\)\(i\) 仅当 \(w_i = 1\) 时会被购买;\(y < i < z\)\(i\) 必须满足 \(w_i = 2\)(否则 \(i\) 会被购买,不满足“\(y\) 是倒数第二个被选择的 \(w_i = 1\) 的物品”的要求),且一定不会没购买;\(z < i\)\(i\) 一定不会被购买。

那么总共花费为 \(2 + \sum_{i=1}^{x-1}1 + [w_i = 2] + \sum_{i=x+1}^{y-1}[w_i = 1]\),即要求 \(\sum_{i=1}^{x-1}[w_i = 2] + \sum_{i=x+1}^{y-1}[w_i = 1] = m - x - 1\)

这个东西是简单的,相当于 \(x - 1\)\(y - x - 1\) 中共选 \(m - x - 1\) 个翻转,方案数为 \({ {y - 2}\choose{m - x - 1} }\cdot 2^{n - z}\)

对于确定的 \(x, y\),满足条件的 \(z\) 是一个后缀,\(\sum 2^{n-z}\) 可以 \(O(1)\) 计算。

再算一下将所有 \(w_i = 1\) 的物品选完后还剩一块钱花不出去的情况,做完了。

写错了两个东西,一直调到 10:40。

看 C 题,有一种和一个月前的 D 题一样的感觉——编不出半个复杂度优于指数的做法。

看 D 题,这个 ABCDE 性质一看就能拼很多分,开拼。

最后拼了 C 的前两个点,D 的前三个点和 AB 性质。

估分 \(100+100+8+40=248\)

Day \(\le\) -1

模拟赛爆爆爆!

Day 0 (10.31)

试机,但没有机。

已完成今日「学长能不能给我签名?五块还是五百块」大学习。

Day 1

哎怎么七点半就醒了。

上午复习了一些板子,包括但不限于 FWT、点分治、割点,以及 SAM。感觉都不像会考的。

中午睡了半个小时。

去考点!!!

好像到考点到得比较早,于是开始水群,得知评测机 CPU 更新为 U9 285K。

进考场!!!

监考老师要求阅读电脑桌面上的一个可能是须知的 Word 文档,经仔细阅读后发现第二页中 NOI Linux 虚拟机相关内容中有“应提供虚拟机密码”类似文本。但显然要求选手提供密码并没有道理,合理猜测是下发前忘记将这里替换为密码了。

开考!!!

打开虚拟机,发现直接进入了桌面,并不需要密码。

开 A,\(\sim 20\) min 写完,经过一顿 ulimit-fsanitize=address,undefined 的测样例和对拍后时间成功来到 \(\sim 40\) min。

看 B,感觉一秒时限是很困难的,糊出 \(O(nk\log k \cdot 2^k)\) 做法并认为太过逆天,思考了几分钟没动电脑后发现虚拟机自!己!锁!屏!了!

发现自己并不持有虚拟机密码的相关知识,尝试 cqbznoi 未果,遂向监考老师求助。监考老师尚未走到就已看到屏幕,便说:“哦密码 123456”随后转向继续行走,全程均速。

继续思考 B,发现可以将所有 \((k+1)n - 1\) 条边的边权离散化,随后在 \(2^k\) 枚举中每次只需要进行一次计数排序,时间降为 \(O(nk2^k)\),开写。

写完测完发现大样例的 \(n = 10^3\),于是自己造了一组 \(n = 10^4\) 的数据,发现运行秒数 \(> 1\)。稍微卡两下卡到了 \(\sim 0.7\)

此时感觉这场已经不会特别炸了,看完 C 根据参加模拟赛的经验想要开拼部分分时反应过来这是 CSP-S 不是 CSP-S 模拟赛。

发现一个替换合法的充要条件:

  • \([l', r']\) 覆盖了 \(t_1\)\(t_2\) 的第一个不同位置 \(l\) 与最后一个不同位置 \(r\)
  • \(s_1\)\(t_1[l', r']\) 相同,\(s_2\)\(t_2[l', r']\) 相同。

认为第二个条件可以通过将字符集平方后合并 \(s_1, s_2\)\(t_1, t_2\) 变为“\(s = t[l', r']\)”。然后可以对所有 \(s\) 建 AC 自动机。按照 \(t\) 在 AC 自动机上转移,当第 \(i \ge r\) 个字符转移完后计算 \(r' = i\)\([l', r']\) 对答案的贡献,需要对于 AC 自动机上,根到某结点的路径上,满足 \(\mathrm{dep} \ge i - l + 1\) 的结点的点权求和。这个显然是做个前缀和后倍增找到最后一个 \(\mathrm{dep} < i - l + 1\) 的路径上的结点就可以做了。

感觉很好,但是 \(L_1 \le 5 \times 10^6\) 完全无法接受 \(\Sigma = 676\) 啊!

我们发现不用扩字符集,可以直接将 \(s_1\)\(s_2\) 中的字符交替插入合并为 \(s\),将 \(t_1\)\(t_2\) 中的字符交替插入合并为 \(t\)。此时上面的 AC 自动机做法可以照搬。复杂度 \(O(L_1 (\Sigma + \log L_1) + L_2 \log L_1)\),开写!!!

欸 AC 自动机怎么写的来着,这下回收伏笔了。

追忆写法并成功写完了 AC 自动机,在 -fsanitize=address,undefined-D_GLIBCXX_DEBUG 的庇佑下发现了样例中的 \(|t_1| \ne |t_2|\),大样例 \(\sim 0.4\) s。

此时还有 \(\sim 80\) min,开 D,一开始看错题认为每个人判的是最近的未被录取的连续段。认为可以拿 \(32\) 分。

打完 \(n \le 10\) 发现样例二跑出来完全不对,回去看看题面发现读错了。

重新想了一下发现可以拿 \(24\) 分。

写完差不多就可以开始检查了,备份代码后 ulimit 测一遍,开 sanitizers 再测一遍。

结束啦!!!

出考场与【a】交流了情况,得知 D 与【c】前几天才讲的一道题差不多,但我当时被拉到下面机房做心理测评了???

得知【a】【b】C 题写的是 \(O(n \log \text{不知道什么东西})\) 的二维偏序,且大样例不是极限数据,且【a】的的大样例跑了 \(\sim 0.1\) s 后自造数据仍然跑了 \(>1\) s,十分绝望。

回去后才想起来还有个 \(O(L_1\Sigma)\),上 QQ 询问【a】他的 C 做法是否有这项,得到肯定回答。

我还以为我的 C 要慢 \(>20\) 倍呢(划掉)。

墓前估分不高于 \(324\)

感觉这个 D 完全是来破坏我的赛后心态的,明明打得没什么大问题却还是有点难过。

目前想法是不想在乎 CSP-S 分数了,反正结果只有“上 WC 线”“上 NOIP 线”和“爆完了”三种。

Day 5

哎怎么就 Day 5 了?

\(\mathrm{score} \le 324 \land \mathrm{score} \ge 324\) 了。

有 WC 去吗?

选自 lzm 某本封面上写着“写作文要有真情实感/”的草稿本,有删改。

Day -? (2025.7.1)

现在是 2025.7.1 23:50


现在是 2025.7.1 8:30,我已经上了飞机,这是我第一次把新手机带出去呢,这次带了耳机,刚传了一些歌到新手机上。

诶?飞机上能用蓝牙吗?不知道。


现在是 2025.7.1 7:40,马上就要出门了。我这次打算在飞机上听听歌,但不知道飞机上能不能用蓝牙。

所以我把那对买手机送的有线耳机也带上了。


现在是 2025.7.1 9:30

他们我们的酒店在哪?不知道。

还是一月份住过的全季吗?我记得当时收走电脑后发现房间里有固定电话,就给 LZY 他们房间打过去了,没人接,第二天被他们敲门才知道原来他们睡得那么早。

我当时的房间号是什么来着?8312?还是哪个?我打开微信,想翻一翻一月的时候给哪些人发过照片。翻了一会翻到了,点开一看。

“图片已过期”。


不管了,来想想龙山书院吧,我还记得当时去那里没带水。

一会应该又能看到了吧。

不对啊,我们不是要到 7.13 才要去开幕式吗?

诶,那为什么要这么早出发呢?不知道啊。


你怎么都上飞机了连这些事情都不知道?

哦,这个我知道。因为你不知道。

Day -1 (5.15)

今天考语文。

但我跑路了。

上飞机前从电脑往手机里传了十几首歌,准备在飞机上听,然后发现自己没带耳机。还好我还传了一部小说过去,感觉几个小时应该读不完二十万字。

在小说里发现了字符串“文化课”,有点害怕。

离降落还有半个多小时的时候广播说机场要求关上遮光板,到机场不准拍照。关了遮光板后还关灯,于是开始聚精会神地睡觉。

坐了很久的大巴到学校。在报道处看见了一张地图,上面似乎是他们学校某届毕业生的去向,有意思的是北京的位置写了“北京大学 11 人,清华大学 2 人”。

发了一件衣服和一个包,包里有各种奇奇怪怪的东西,感觉有用的也就一支笔和一个 U 盘了。

到了宿舍打开随身 WIFI,-90 dBm 还是能用的。

试机,写个 assign 还 WA 了,调了半小时。

Day 0

昨晚没睡好啊,床上有点太热了。

听课,好难啊听不懂。

开幕式氛围感很强。

Day 1

空调开到 22 度,睡眠质量显著提高。

入场,发现发了好多好吃的。

前 4h 打了 \(78+22+16\),后 1h 啥也不会,开始狂吃,并感觉两部分时间一样长。

更加详细的赛时情况

最开始先读了一遍题,由于 T2 题目太长不是很好理解,并且 T3 的 \(2 \times 10^6\) 次操作和一次操作可以更改多个 \(a\) 值看起来很吓人,所以认为 T1 是最简单的。

随后想了一个 25pts 做法并在第 40min 写完。

想到构造序列,用 \(O(\sqrt{n})\) 的长度覆盖 \(1, 2, \cdots, n - 1\) 的所有差值,尝试序列 \(1, 3, 6, 10, 15, \cdots\),有问题。然后想到 \(1, 2, \cdots, \sqrt{n}, 2\sqrt{n}, \cdots, n\),没什么问题。

尝试在这个做法外面套一个二分做到 \(O(\sqrt{n}\log{n})\),这个东西刚好卡进 \(10^6\),预计得分 28pts,感觉写了会很亏,于是继续想。

想到自己可以不用覆盖 \(1, 2, \cdots, mid\),只需要覆盖 \(l + 1, l + 2, \cdots, mid\),于是变成了约 \(1.5 \times 10^5\) 次询问,78pts。

想 T2,先写了 \(m = 2\)\(e > m\),12pts,\(e = m - 1\) 没什么思路,去写了一个 T3 的 \(n = 2\),目前得分 \(78 + 12 + 5 = 95\)

想到了 T2 这个拆环、并环的过程,写出了 \(e = m - 1\),猜测 T3 是配对 \(\lfloor\frac{n}{2}\rfloor\) 对达到最优效率,于是写了 \(1 \le a_i \le 25000\),此时已经过去 4h。

继续思考如何优化 T1,想到哈希冲突的具体次数还没用上,一直在尝试利用这个信息。

写了一个利用信息每次将二分区间缩小 \(\frac{3}{2}\) 的做法,WA 了,感觉这个缩小有问题,把缩小条件改严格一点,没 WA 但询问次数达到 \(1.9 \times 10^5\),不如直接二分优。

比赛结束时为 \(78+22+16\)

一些想法

T2 的 \(e = m = 3\) 和 T3 正解没打出来很可惜,“因为我觉得 T1 是最简单的,所以就在 T1 拿了很多分”很神奇。

可能都是因为难度排序的比赛打多了,更习惯先做 T1 吧。

出来怎么听说 T3 比 T1 简单啊?

听讲题,听完 T3 上去讲了一下自己的悲惨经历(sub2 check)。

发现自己场上发明了 BSGS。

T2 太震撼了!

Day 2

不懂这个社会实践在干什么。

颁奖,现在全世界都要知道我铜牌了。

“结束了,孩子们”。

Day 3

还能写 Day 3 我是没想到的。

飞回 CQ,但发现自己被迫爆照了。

link

我就是那个穿着黄白衣服被拍了四张的,这里就不放了。

Day 0 (2.28)

试机,按照惯例试了一下 \(2000\) 的 ULL Floyd,8s。

Day 1

进场、发密码、看题。

怎么输入里有测试点编号,这么良心?

看完 T1 感觉可能的中位数应该是一段连续区间,这样两个二分就做完了,至于 check,可以 \(O(n)\) 计算最多有多少个 mid,比 mid 小的数和比 mid 大的数的个数差的最小值,简单判一下。

写写写,发现不对劲,这东西可能会把不存在的数算进答案里。

至少 check 的思路没问题,那就直接离散化把值域搞成 \(O(n)\) 个区间,每个数能不能成为中位数只和它所属的区间有关,check 可以用一个扫描线和一堆树状数组做到总共 \(O(n\log n)\)

T2 先写了一个 \(O(nq)\) 暴力。

看一看,发现它时间 6s,空间 2G。算一算,发现 \(10^{10}\) 个 bit 比 2G 小。

那就 bitset 处理能否到达。然后怎么做呢?看一眼部分分,AB 性质可以分块做,赶紧写了,拼上 \(O(nq)\) 20pts,有测试点编号就是好写

T3 根本不会!暴力只会 \(O(Tn!m^2)\),算下来 \(n \le 10\) 卡满都 \(10^{10}\) 了,不太能过。

然后还是写上去了,发现样例跑得飞快,完全不像 \(10^{10}\),不管了。

Day 499122178

出考场,听说 T2 是根号重构,太强啦!但我怎么不会?

Day 2

一看 T1 怎么这么熟悉?ABC 原题?线段树维护 \(pos_i-i\),写几个线段树上二分和区间推平秒了。

第二个样例怎么错得离谱?哦原来还可以往前推的啊。往线段树里加了个区间最小值之后标记下传又错得离谱了,调了不知道多久后过样例了。

完全不拍!相信大样例!开 T2!

性质 A 纯暴力,先写了个 \(O(4^m)\) 枚举边的存活状态,然后爆改 prim 再乘个 \(O(n^2)\),一看怎么样例二第一组数据没过?\(1280\rightarrow 1256\),重写了两遍还是不对,合理怀疑 prim 没正确性,直接枚举外向生成树的 \(n-1\) 条边过了。

性质 B 生成树唯一,容斥枚举哪些点能够到达其他所有点,样例能过。

试图将性质 A 与性质 B 进行对拍,发现每棵树拍出来的答案都一样,猜测树的形态没有影响,不过容斥都写完了。

开 T3,暴搜启动!

Day 3

还原了一下自己的 D1T1 和 D2T1,过洛谷民间数据了。

Day 6

\(100+24+8+100+24+8=264\)。感觉还行。

D1T2 \(O(nq)\) 有 88pts?

Day 0 (1.13)

下午到达酒店,按理来说应该两个人一间房间的,但我们有九个人,所以喜提大床房一间。

晚上去吃地锅鸡。

“你跟他说我们是重庆的,给我们上特辣。”

“啊?”

玩狼人杀,抽到预言家,但查了一个好人和一个自刀狼就被女巫毒了(?

晚上电脑和手机被收了,于是开始研究酒店的语音助手和电话,给 @LZYAC 房间打了两个电话结果他们没接。

Day 499122177

本来应该是 7:40 起床,然后被 @LZYAC 6:40 敲醒了,经过交流才知道我昨晚打电话时他们已经睡觉了。

吃完早饭前往龙山书院,到了之后才发现我们九个好像就我没背着包出来……

然后一整个上午都面临非常非常非常严重的水资源短缺,直到 12:20 试机前才买到两瓶水。然后考场旁边就出现了几箱水并且可以自取?

注意到考场发纸但不发笔且我的笔袋在酒店里。不过没事反正我 CSP 的时候也没用过草稿纸。 但我 NOIP 草稿纸不是写满了?不是写满了?不是写满了?

Day 1

T1

注意到这题十分熟悉,但我没管,猜测策略只有两种:

  1. 将当前的第一节电池与其他所有电池进行测试直到成功或可以证明第一节电池为坏电池为止。

  2. 将当前的第一节电池与第二节电池测试,不成功直接丢掉。

于是考虑 DP,\(f_{i, j}\) 表示当前有 \(i\) 节好的与 \(j\) 节坏的,最坏情况最少猜测次数。复杂度为 \(O(ab)\)

显然错误。但为什么这题这么熟悉呢?回忆一下,原来我在去年不知道啥时候做过这题的一组 \(a = b = 4\) 的数据啊,回忆一下当时怎么构造的。

1
2
3
4
5
6
7
8
7
1 2
1 3
2 3
4 5
5 6
4 6
7 8

观察一下

1
2
3
1 2
1 3
2 3

它的意思是使用 \(3\) 次机会确保前 \(3\) 节中至多 \(1\) 节为好电池,然后直接丢弃前 \(3\) 节电池。

再仔细思考一下,这意味着可以使用 \(k\choose 2\) 次机会确保前 \(k\) 节中至多 \(1\) 节为好电池,然后丢弃前 \(k\) 节电池。

因为是最坏情况,所以前 \(k\) 节中必定有 \(1\) 节是好电池。

将其加入到转移中,此时复杂度为 \(O(a^2b)\),400ms 轻松通过。虽然我也不知道为什么是对的。

T2

排序去重 + 树剖求 \(k\) 级祖先有一个 24pts 的暴力,啥也不管直接写了。

感觉可以离线询问然后枚举 \(x\),对于每个 \(x\) 的询问像 P1972 一样扫描线处理,时间复杂度为 \(O(n^2\log n+m\log n)\),也是 24pts。

在扫描线中将树状数组换为 \(O(1)\) 修改的分块就可以 \(O(n^2+m\sqrt n)\) 了,看起来还是过不了 Subtask3,但观察到时限给了 4000ms,由于 A 题带给我的对于评测机的信心,我决定写一下这个东西。

TLE 24pts

加了个快读仍然 24pts,跑路去做 T3 了。

T3

\(O(n^2k)\) DP,加了个 bitset,20pts。

Day 499122178

出来发现大家好像都是 144,疑似大众分?

经过交流知道了 T3 tarjan 缩点可以做到 \(O(nk)\)

Day 2

炸飞了写什么游记?炸飞了写什么游记?炸飞了写什么游记?

Day 0 (11.29)

上午复习了三个 tarjan。

下午试机,听洛谷讨论区说 CCF 评测机跑 \(2 \times 10^3\) 的 ULL 自然溢出 Floyd 需要 5s,在考场的电脑上试了一下,12s,另外还试了在 qingyu 博客看到的 -fsanitize=address,undefinedulimit -v,本来还想试一下对拍的,但是没打完就回去了。

晚上完全不知道干啥。

Day 1

进考场,和 CSP 一样还是开着 Windows,等极域发了密码我就赶紧重启成 Linux 了。前十分钟先开 VSC 敲了个缺省源。

读 A,发现自己好像不太会,于是边写边想,第 70min 写完,结果调不出来。于是直接重写,第 90min 过大样例。

然后开 B,一眼看出 \(d_j\) 不影响答案,也就是如果 \(j\)\(i\) 下一个赋值的,那么有两种情况。

  1. \(i\) 开始的限制最后传到了 \(j\),显然有 \(v^{j-i}\) 种方案,其中 \(\frac{1}{v}\) 的方案(即 \(x_{j-1} = a_j\) 的方案)是合法的。

  2. \(i\) 开始的限制最后没传到 \(j\),有 \(v^{2j-2i}-v^{j-i}\) 种,全部合法。

将每段的合法方案数相乘,再特殊处理首尾两端,需要注意 \(c_j\) 相同的情况。

在草稿纸上写完上面这些直接开写,140min 左右过大样例。

C 题先写了一个 \(k=1\) 的 24pts,大概就是在很多个完全子图里任选一条钦定了一端的链,方案数为 \(\prod\limits_{i=1}^n (deg_i - 1)!\),第 174min 写完。

写完 C 的 24pts,决定先看看 D,发现求 LCA 是可重复贡献的,而且满足结合律,用两个 ST 表写了 \(n, q\le 5000\) 的部分。回去看 C,观察第九个样例(一条链)发现全是 1,第十个样例(菊花图)的式子也很好推,于是喜提 16pts。

再看看 D,感觉自己的双 ST 也可以做 \(k=r-l+1\),花五分钟改了一下。链的 32pts 脑子过载,一眼没看出来就没想了。时间只剩半小时,开始检查,发现自己 D 没写 freopen,赶紧加上。最后十分钟切回 Windows,等待结束收代码。

此时估分应当为 \(100+100+40+32=272\),但由于我看错了 C 部分分的测试点个数,所以以为自己是 \(100+100+44+32=276\)

比赛结束,然后别的考场十分钟收完,我们考场收了半个小时(?

赛后才发现 D 链的 32pts 非常好拿,不过我也拼了个 32,感觉还行吧。

感受

感觉这场自己打得比较保守,比如最后半小时没去冲链的 32pts。但是再想想,就算写出来也可能忘记 freopen

另外,-fsanitize=address,undefined 好用!

跟风。

查浏览器,但是……

电脑浏览器

A: 无

B: 无

C: 无

D: 无

E: 无

F: 无

G: 无

H: 无

I: 无

J: 无

K: 无

L: 无

M: 无

N: 无

O: 无

P: 无

Q: 无

R: 无

S: 无

T: 无

U: 无

V: 无

W: 无

X: 无

Y: 无

Z: 无

你要问为什么?


初赛

Day 0 (2024/9/20)

有的人,明天早上就要 CSP 了,却还在打 CF(

五题 WA 了四发,有多菜不用说了吧。

Day 1

上午

还没开考就发卷子了,第五题一眼 1048576,每次算空间都用的,再一眼原来是 bit 啊(

但是第十题我真的很想选 B。

Linux 只是内核,GNU/Linux 才是操作系统!

改二叉树遍历顺序的选项已经成了 CCF 传统艺能了吗?

阅读程序 <=n 看成 <n 了,痛失 3 分。

感觉真的一年比一年简单了。

下午

因为考场没有钟所以监考老师用希沃白板搞了个计时器?还能看到秒数?

发卷子 为什么我上午倒数第二个发,下午就成第一个了。

第十题感觉是 \(O(n\alpha)\) 的,但没看到 所以 CCF 是把 \(\alpha\) 当成常数了吗?

第十五题一开始数漏了一组,后来改了。

第三十一题直接按 123456 的顺序算的,没中序遍历,寄了。

晚上

ABC,Perf 第一次上 2400。

但 AC-predictor 告诉我 1936 的 rating 呢?怎么变 1937 了?

复赛

Day 0 (2024/10/25)

上午

随便复习了下 Splay 虽然模板题都没调出来

下午

去考点试机啦。

考点是双系统,试机时还没断网。先试了下 NOI Linux,拿 VSC 试了下代码片段,打了个最短路模板,因为没有洛谷大号密码所以交小号上去了。

然后试 Windows,给了 VSC,上面还装了中文插件和 C++ 插件,甚至还能用自动补全 /jy。

键盘也很好用,反斜杠和回车的位置很顺手(

Day 1

上午

一进考场就开着 Windows,反正我也不太想拿 Linux 下那个啥也没有的 VSC 写代码。

开考了,先用 VSC 的代码片段默写了一下我的缺省源。接着开 A,写了个 set<string>,非常弱智地没有使用 52 - st.size(),而是枚举每个字符串判 st.count()

B 没啥好说的。

C 写了一个逆天 DP,大概就是让 \(f_j\) 表示在总共使用 \(j\) 根火柴棒,且可以全部拼成 \(0\) 的情况下的最优方案。让 \(g_j\) 表示至少有一个非 \(0\) 数位的最优方案。方案都指的是多重集,所以时间复杂度大概是 \(O(nD + T)\)\(D\) 指有用的数位的个数?不知道有啥正确性,但我的直觉告诉我它就是对的。

写完 C 大概已经 10:10 了。

看 D,一眼出了一个 \(O(r{\sum l}^2)\) 的 DP,就是把一共 \(2 \times 10^5\)\(S_{i, j}\) 拍到一个一维数组上,记作 \(a\),然后 \(f_{i, j}\) 就表示有没有方案可以使第 \(i\) 轮结尾的数字为 \(a_j\)。显然这个东西把状态的定义从“有没有方案”换成“有几种方案”就可以差分优化,时间复杂度为 \(O(r\sum l)\)

写完;发现大样例跑了九秒多;发现自己没开 O2;发现开了 O2 也才四秒多;猜测 Windows 下测试有误差;关机启动 Linux;发现 Linux 下也跑得一样慢;随后就进入了漫长的卡常时间。

然后我还惊奇地发现 Linux 下的 VSC 突然就变成了最新版带中文带补全,明明昨天试机的时候还是 1.54.3 的。

经过了一个半小时的不懈奋战,终于把大样例卡进了两秒。然后就发现大样例的前两组数据的 \(\sum l\)\(2000\)……

12:00 比赛结束,然而还要核对源代码,每人发了张打印了收上去代码字节数的纸。而且核对源代码怎么只核对字节数啊,为什么不核对一下 SHA256 什么的。

12:20 出考场,发现别人 C 好像都是找规律做的,而且 D 并不像我想象的一样人均正解卡常。

估分:\(100+100+100+100=400\)

下午

下午入场怎么多了个安检。

解压发现有道题目叫 “duel”?CCF 怎么知道我前几天在某个网站上 duel CF 直接从紫掉到青的(

开考发现原来这个是 A 题啊,赶紧切了。

看 B。CCF 怎么知道我国庆以来停 WHK 错过了我们班神奇的 WHK 进度(语文七下,英语八上,还有物理),在这放道物理题偷袭我(

还好给了公式,二分一下就写完了。

C 题一眼出了一个 \(O(n\min(n, V)^2)\) DP,然后再一眼优化成 \(O(n\min(n, V))\),再一眼优化成 \(O(n + V)\),赶紧开写。

写完 C 过了大样例的时候是 16:00,反应过来这场好像非常简单,感觉自己认识的都要人均 300+ 了。

此时我还有两个半小时的时间,感觉自己可以随便浪了,就硬想 D 想了两个小时,才反应过来时间不够了。赶紧写一下自己刚想出来的 \(O(Tn\log n)\),结果 WA 在了样例 4,也没时间调了,按照前三个样例的数据范围看,应该能拿到 32pts。

估分:\(100+100+100+32=332\)

闲话

在 Day 1 中,我一共写下了 \(14\) 个汉字,其中有 \(0\) 个写在了草稿纸上,剩下的 \(14\) 个分别是:\(2\) 个“代”,\(2\) 个“码”,\(2\) 个“一”,\(2\) 个“致”,\(2\) 个 [l],\(2\) 个 [z],\(2\) 个 [m]。

Day 10

CCF 的评测机是强的,给我 J 组的 D 题放过去了。

CCF 的数据也是强的,没给我 S 组的 D 题留下一分。

J: \(100+100+100+100=400\)

S: \(100+100+100+0=300\)

0%