考试前几星期

我偶然获得了去北大参加夏令营（就是去垫底的）的机会，然后在强大的中考压力之下我毅然决然地选择了去（误），然后竟然申请通过了！然后就跟着学校一起去北京，一共就三个学生。

Day 0

这是考试前一天，5 MAY 2023，早上10点做飞机飞往北京，下飞机后经过大约30min的车程，我们来到了北大的对面的酒店。不得不说，大学是真的大。虽说我小时候曾到清华里去游览过，但是不同时候，不同年龄，做着不同的事，心境也不同，难免有些感慨时光如梭，白驹过隙了。

午饭在飞机上吃的，挺好吃的，我吃得一干二净。玩了一个下午，和同房间的小伙伴犹豫了半天去吃 KFC (我也是服了) 。又玩了一个晚上，没有做题，CF 时间太晚也没打，然后就睡觉了。一直睡不着，难受。

P.S. 我妈给我了一个什么辣鸡手机啊，不充电熄屏的时候就会自动关机，shift！
P.S. 今天好像空调坏了，热死了，外面又冷死了，晚上就又好了。
P.S. 吃晚饭的时候我只穿了个短袖，走在北京市海淀区的街头，冷风飕飕，心里凉凉。

Day 1

5 MAY 2023

早晨起床，心情良好。吃过早饭（早饭拿多了，但我还是坚持吃完了），进到北大里面（现在我清华北大都进去过啦 OHHHHH ）。早上是一个开营仪式，先极其简略地介绍了一下嘉宾，然后又稍微说明了一下信息科学技术学院的历史，还给几位优秀学长发奖状（貌似说ICPC金奖有奖学金3W，爱了爱了我们可是脱离了低级趣味的人，计算机才是我们的老婆！）。

然后去试机，那道题我没做出来（悲，然后又问了室友搞出来了。

然后去了未名湖，挺大的，还有很多校友在那里，漂亮。

食堂是真的爽，吃了接近块钱，我觉得都多了，没吃完，后来又买了一瓶芬达，才3块，最后还剩块，怎么花完啊！P.S. 食堂是免费的，这个”燕园卡“是送的，上面说《尽量吃完》，谁吃那么多啊。

下午去考试了，我比较 calm ，毕竟是出来玩体验的嘛，我觉得100以上就行。

T1

#KMP #字符串hash

给两个相同长度小写字母组成的字符串和，然后从第一个字母到第个字母令（每次操作都互不影响，都在原串上操作），然后求的 border，border 就是最大的相等的前缀和后缀的长度，输出行。

这道题搞了大概 2 hours ，我先用 KMP 算法处理，正着倒着各处理一次，就有两个那个啥数组我就分别定义为 p[i] , 和 dp[i] （ d 是倒的首字母），然后假设现在交换第 i 个，那么我就求出当前更改后这一位的 p 和 dp ，然后我就考虑这一位在后缀中，那么此时的 p[i] 对应的前缀刚好就也是以 i 为结尾的后缀，那么再验证从是否等于一样了，这里我就用的双 hash 来搞的，然后这一位在前缀中同理，就用的 dp 数组。然后还有这一位不在前后缀中的情况，就用原始的 p 从 p[n] 不断往前找到第一个前后缀不包含 i 这一位。

结果这道题貌似卡常，拿了 91 pts 。

T2

#dp #min-max

有个人，已知第个人是狼人，剩下个人中每个人都有等概率成为预言家（只有一个），预言家每天可以判断狼人是否在一个玩家区间中，且区间是随机的，也就是随机个区间中随机的一个，然后求能确定狼人的天数的期望。

这道题没做出来，当时想的是 DP ，又想到了 min-max ，但是我不是很会，就没做。
后来听室友说确实可以这样做，正解不知道。

T3

#dp #树

有一个以1为根的树，每个结点只有偶数个儿子。每个结点的值要么为，要么为，然后每个结点还有一个分析值，一个结点的分析值等于其自身的值和其子节点的值一起的众数。现在已知每个结点为的概率，求根节点的分析值为的概率。

这道题我也不太知道怎么做，也不知道怎么 dp （我真的没怎么做过 dp），然后就用递归套递归（我真是个人才）暴力过了 subtask 1 ，最后得到了 12 pts 。听室友说了一下，貌似知道怎么暴力拿35 pts 。

P.S. 在考试开始前就听到疯狂的敲代码的声音，吓死我了，写快读或者定义 for 循环的宏也没必要这么夸张吧 （反正我是不很喜欢搞这些的），而且考试开始没几分钟就感觉很多人就开始不停地敲代码了我真的差点心态爆炸，感觉人均神犇，好在后来心态恢复，集中注意力，就没管了。

然后今天晚上教练请我们吃饭，还请来了之前的学生一桌子。影响深刻的有：学校招牌学长 zjj ，社交恐怖分子 lyw ，高中毕业比我出生还早的学生 zks （差点又被 zgs 忘掉了），然后 fsy 没来，可惜。

结束了，明天，来吧！这么说又要回学校了，北京的生活真舒服（ money 是个问题）。

Day 2

最后一天了，晚上就要回去，竟有些不舍。

早上有个讲座，两个人讲。一个讲信息学竞赛的发展，另一个给北大宣传。第二个讲的我全程录下来了，40分钟，手都要废了。介绍图灵班的那个四合院，真是壮观。然后去逛了逛北大的校园，在燕南园中，仿佛置身于置身于几十年前。漂亮的是有一些院系在一个古老而又繁华的四合院中，现代与历史的完美结合实在令人唏嘘不已，却又十分壮观。

中午又去食堂吃饭，吃了25块钱多一点，本来想少拿一点，结果又拿多了（悲。然后去买了一个冰淇淋，才2块半毛钱，简直是太爽了。

下午又要考试了，最后一场，加油！

T1

#数据结构 #平衡树 #FHQ-Treap

就是有一个 queue，有三个操作：

• 再读入一个数，表示新进队伍一个人，其编号依次顺延，从1开始。表示这个人站在编号为的人后。
• 再读入两个数和，表示将编号为的人入队时的那条指令改为，为表示在队首。
• 再读入一个数，表示查询当前编号为的人站在第几个。

思路：我发现这相当于是一个树形的结构，先序遍历的结果就是这个队列的样子，然后我开了一个 set<pair<int, int> > 来记录每一个的儿子，第一项是时间的相反数，第二项是编号，因为时间越小肯定越在前面（后面发现好像不需要，毕竟兄弟编号越大肯定越在前面），然后再开一个 siz 数组来记录每个编号其子树大小。对于操作，就相当于把那个结点的父结点改了。求位置就只需要不断往上走每次把这个结点在它之前的兄弟的 siz 都加起来再加不断往上直到就行了。这里更新 siz 我就是不断往上枚举增加，计算也是枚举的。当时考场上我发现计算 siz 的和的时候可以写 FHQ-Treap 分裂来求之前所有兄弟 siz 的和，但是考场上没有调试出来。这样貌似可以多过一个点。至于每次入队更新 siz 怎么搞，当时考场上我想不出来，我觉得可能是树链剖分，反正我想不出来。

成绩：25 pts 。

T2

#数学

这个题目应该是个 NP-hard 问题，所以最后要求求近似解。

首先输入，表示多组数据。

每组数据先输入一个，表示有多少组数。

然后每组数先输入一个数，表示这组数有对数。

然后读入个数，表示。

然后读入，表示组询问。

每组询问读入两个数,，然后需要你求出尽量大的一种方案，输出个数字，要求要大。

思路：这道题我确实不知道怎么做，最开始想用模拟退火看人品，结果恁地一分没有，最后打了个暴力然后写了一个迷惑 dp 过了两个点。30 pts （这两个成绩可能反了，我记不太清了）。

T3

#数学 #数论

什么玩意儿，完全不会好吧，就是一个含有模的参数式子，给出几个参数的值，构成一个方程组，求解。好吧，确实不会，暴力都不会打。

最后总共拿了分，超过了25%的得分率。

后记

随后我们便启程去机场返回成都了。吃了一顿肯德基，天色渐暗。三天时间转瞬即逝，蓦然回首，几天前我从这里走过，几天后我将再从这里返回。离中考还有30多天，30多天后再回首，亦不过是陈年旧事罢了。三年后，我又将何去何从？上了飞机，看着北京的夜晚灯火辉煌。慢慢爬升，北京也离我们越来越远了。窗外逐渐变得漆黑，我要了一个耳机，听着飞机上的音乐，便坠入了梦乡。再次醒来，离成都已经不远。我心中充满了紧张，如同三天前将要飞到北京一样，只不过这时，我心中又多了一丝自信与笃定。窗外下起了雨，淅淅沥沥，一丝一丝打在飞机的舷窗上。窗外雾气弥漫，不知这雨是欢迎我的归来，亦是将我心中的愁思，化作雨，一滴滴飘散在世间。站在摆渡车上，望着机场一架架飞机离我远去，我坐着摆渡车前往机场大厅，我也坐着摆渡车，驶向未来。我知道，未来是未知，充满了不确定。但是我相信，只要未知成为了已知，它便不会再令人恐惧，我追寻我的梦想，未知必定会给予我梦想的馈赠。一个晚上，闭上眼睛，再睁开眼，天亮了；一呼一吸间，时光飞逝，美好的生活，终会到来的！

P.S. 后面的内容是我后来补的，主要是当天到成都太晚，后面有在做作业，于是在今天将其补完，也算是一次难忘的经历了罢！

这升华主题真是完美呢