序
居然过了 PKU，纯属幸运，看来要抓住机会了。
让我来好好享受这次体验吧……
2025-01-11
来到机房找大佬教用 Linux（丢人）。
学习了 vscode，以及对拍技巧。大佬哥哥还不省心，教了我如何建树、排列。
紧张。
2025-01-14
Go to shaoxing.
状态不稳定，但依旧乐观。
2025-01-15
终于到正文了。
早上去拿了牌，第一次参加 PKU 的活动，兴奋。
参加开幕式，全在介绍 PKU，跳过。
旁边的同学按耐不住，开始抓拍做表情包了。
中午拿了饭票去吃饭，然后休息一下，就去试机了。
试机题好难……T1 只拿了 \(20pts\)……危机好像要降临了。
下午开题。
T1
有 \(a\) 个有点电池和 \(b\) 个无电电池，每次可以选两个到手电筒上，问在最佳策略情况下至少要几次才能使它亮起来。
一眼先瞪出鸽巢原理，不太会，先放着。手玩了几组数据，发现 \(a>b+1\) 时答案为 \(b+1\)，WA 了几发，在 13:10 左右达到 5pts。后来发现当 \(a=2\) 时，两两分最优，大概在 13:20 左右又拿到 5pts，优势在我。
后来开始打 sub1，交了十多发。途中顺便开了 T2，随便写了 24pts 的做法，先放着。T3 神秘博弈论，先放着。
T1 sub1 怎么那么难写！于是不想推了，写了打表程序，其中 check 复杂度 \(O(2^{(a+b)^2}2^{(a+b)}(a+b))\)，可能还估计错了，反正居然能将 \(n\le 4,m\le 4\) 的表打出。发现 \(a=3,b=3\) 挂了，输出了一下构造，发现建完全图。
去了趟厕所，突然发现好像就是鸽巢原理，回来是已经 15:55，这下完了（不是我把鸽巢原理放着是什么意思）。
后来推一推，发现似乎均分更优。居然是贪心，写写写。
交了，0pts。此后写了好几种，但赛后发现没一个对的……甚至最后一个版本写对了，然后后面又加上一些奇怪分配操作。
已经 16:35，才 \(15+24+0\)，完了。
后来放弃贪心，采用 DP。转移方程推出了，可以是个 \(O(n^3)\)。交上去依旧是 0pts，当时上界应该改成 \(100\) 的！这样也有 70pts 了！
最后 5min，又交了一发错误贪心，30pts。
结局
最终 \(30+24+0=54\) 遗憾离场。
发现好像都没讲 T2 与 T3 耶，那是因为都只是在做 T1 时抽空看 & 写的。
转折
晚上难过，于是用摆烂麻痹自己。
睡觉时，突然，我想起了什么：
居然过了 PKU，纯属幸运，看来要抓住机会了。
让我来好好享受这次体验吧……
来绍兴参加北大营，是把期未考都请假了才有的机会。你很努力，但还要更加努力，面对高手如云，你要有必胜心理以及分秒必争状态！
回味这个晚上做的事，后悔无穷。
又想起这次的挫折。
我，输了。
时间流逝，并不是给人假性放松，而是要发挥自己的光彩。生命并不是要靠别人给你光，你要自己成为那道光，点亮自己。生命从来不是为了比赛，而是为了自己、为了爱你的人……
枕边一片湿……
努力？天赋？时间？
我该何去何从……
2025-01-16
一夜未睡好，睡眼朦胧。
在酒店吃了早饭，然后分析了一下局势。
等等……试机赛的 T1 说是 PKUWC2024 Day2 T1……Day2T1……Day2T1？！
试机题好难……T1 只拿了 \(20pts\)……危机好像要降临了。
不愧是我。
12:00 准时开赛。现在，并没有昨天的轻松愉悦，只有千万斤的压力。
洗净 CSP 耻辱？可笑。
想拿一等？可笑。
T1
交互题，可以询问 \(query(x,y,z)\) 其中询问的数互不相等，返回 \(dis_{x,y}+dis_{y,z}+dis_{z,x}\)。或是询问 \(in(x,y,z)\)，返回 \(x\) 是否在 \(y\) 到 \(z\) 的路径中。然后让你求树的直径。
跳了。
T2
不放题面了。
感觉很贪心，交上去，只过了 \(c=1\) 的部分分，11pts 到账。
13:20 就有了 11pts，优势在我。
后来分析出 \(dp_{i,j}\) 表示前 \(i\) 个，\(a_i=j\) 时的最小代价。然后 \(j\) 的状态并不多，好像可以乱搞减少空间，应该就 A 了。实现复杂，先跳了（不确定对不对）。
T3
先写了爆搜，6pts。
后来想了想，发现可以倒着搜以减少乘法时多余的空间，过了 \(l=r,B\le 4\) 的部分分，已经 18pts 了。
此时已经 14:00。
后面的时间
开 T1。先发现若可以钦定两个相邻的点，那么就可以用两遍 dfs 求出。
但好像不能钦定啊，怎么办？没办法了。
于是尽力搞第一档，弄了一个 \(C_{n}^{3}\) 的假做法，但当时找不出来。
等等，好像可以生成树啊……
大佬哥哥还不省心，教了我如何建树。
于是造了组 gen.cpp 和 check.cpp，结果拍了 \(3000\) 组没出来。
后来发现一种可能能卡掉的情况，但居然过了。
难道要将树上的点重排？那就映射一组排列。
大佬哥哥还不省心，教了我如何建树、排列。
16:55，决定生死的时刻到了：
Wrong Answer in test 2.
呵呵……我笑了。或许，也不过如此吗……
耗到 17:00，\(0+11+18=29\) 遗憾退场。
结局
2days 总分 \(54+29=83\)，遗憾结束。
听了大佬讲了最简单的 \(n^3\) 做法，晚饭时搞出了 \(8n\) 的做法，其实前面都对的，就差一步啊！
后来又听了一些讲解，发掘出 \(4n\) 的做法，但不太好实现。
讲解概括：
-
Day1T1 不说了。
-
Day1T2 当时一看 \(n\le 5\times 10^4\)，一眼莫队或分块，看起来更像莫队。结果还真是莫队。
-
Day2T1 差一点。
-
Day2T2 dp 设计想对了，方程写对了，懒了。
总结
一段平凡的路，一段不平凡的生涯……
愿继续努力，朝着心中之梦迈进，多想想自己是来做什么事情的……
努力？天赋？时间？我该何去何从……
不用“去”和“从”，要坚定走好每一步。
I have lost before,
I don't want to lose,
I won't lose.
此时，心中感慨万千。我必将努力，创造独属于自己的光辉！
——linjunye,an ordinary oier.
标签：发现,le,PKU,试机,PKUWC2025,T1,2025,游记 From： https://www.cnblogs.com/linjunye/p/18678757