Day -23

下午得到 ACM 比赛消息，和 lsq 默契地想到加上 hwh 组个队，晚上 hwh 也不约而同地提出来，三人一拍即合，hwh 语出惊人：“我们仨经常在一块搞......”

最终和巨神 hwh，lsq 组队

Day -21

进行第一次模拟练习，一开始我们有两个备选策略：

$2.$ 三个人分别看不同的题，这样的好处就是做简单题会很快，基本上唯一的一台电脑不会闲下来，效率会很高。但是缺点也很显著，就是有可能一个题每个人都会其中的一部分，拼起来正好是答案，但是如果不全看这个题就做不出来，遇到这样的情况相当于白给了一个题；而且如果一个人看的那个题写代码出锅了，另外两个人就得重新看这个题帮忙debug或者让那个人自己debug，这样的话效率反倒不如第一种策略 但第一场模拟赛我们还是采取了第二种策略，开始他们俩拖出 $A$ 题，我随便点着看剩下的题，估计一下难度和有无思路。~~手气是真好，一上来就开到了全场最难题~~。但是我马上确定了全场第二简单的题，并提议大家一起做这个题（此时我已经意识到这场题目比较难，分开做很难做出来） 但是 $lsq$ 摁住 $A$ 题不放，说如果放弃我们仨前一个小时就相当于什么也没干，~~但是你如果还一直干下去不就相当于浪费五个小时~~？$hwh$ 在中间遇到一个有思路的蓝题就开始肝，结果最后谁都没做出来，~~还不如帮我做那两个最简单的题~~，必须禁止他们俩的瞎操作 一波操作，五个小时，结果惨遭爆 $0

Day -20

进行第二次模拟练习，比上次好了一些，至少和 hwh 配合做出了一道题。 lsq 以不知名的理由咕了模拟赛，但是我和 hwh 却打得比昨天好，控制变量法实锤

题目还是调的过难了，打了三四个小时只做出来两个，第二题真正体现了配合，我不会判 -1 但是会求最优解， hwh 不会求最优解但是会判 -1 ，最终合作切掉了这题。我还质疑匈牙利必然会 TLE，没想到复杂度是 O(?)，欠下一台电脑没吃

发现最后不是不会了，是心态被打炸题目做不下去了

Day -17

被数据结构打得心态爆炸，抄题解都抄不过，非常伤心

垃圾糖果公园

Day -15

由于做 CF 题要用到回滚莫队，不得不重新拾起数据结构开始学习。中间找了好久的 bug 都没有什么发现，对着题解抄也没发现什么锅，最后是发现别的地方写错了，看题解其实并没有帮到我什么......最终还是把回滚莫队过了，感谢上天让我睡个好觉

Day -14

进行第三次模拟练习，找了一场 Div3 和一场 Div2 拼起来，感觉信心大增，切题手感火热，14 个题切了 7 个，感觉很爽

但是好像稍微难点的思维题还是做不出来，一看题解就直呼妙啊，我写了那么多蓝紫数据结构写给**了

Day -13

进行第四次模拟练习，Div2 + Div1 ，感觉难度适中，切了三个题，好像分别是 Div1 A 和 Div2 A+B ，这什么阴间场，Div2 C 怎么就蓝了，还 2400 分，这能做出来才怪呢

全场最水的题 WA 了四发，不知道为什么，删了删前导 0 就过了，也不知道是为什么

自己仿佛是打代码的机器，不过不得不说打暴力打多了代码实现很少出锅，而且有了手感。我都不知道我打了些什么就把 Div1 A 给过了......

“一开始最厉害的选手先打代码”

第二天过来很快又把一个 dp 给补掉了，发现做 dp 挺顺的，但是一遇到数学题就完蛋了（一个只会线性筛素数的蒟蒻瑟瑟发抖）

Day -9

晚上 CF 手感火热，50min 竟然连切 ABCD ，都是一发过，由于 D 和 E 是一道分水岭（好久之前我就想吐槽，D 题到 E 题之间一下由我能独立做出来的题变成了我连题解都看不懂的题，这难度跨越有点离谱），看了眼 E 题直接就扔了，但是由于做得快且一发 AC ，打到了历史最好排名，RK 334 （20000+ 人比赛），或许能苟上蓝名

这个比赛结果也无愧于我在学校停晚自习每天过来先打一场 CF ，确实是肉眼可见的进步

Day -7~Day 0 省队集训

首先声明，我没进队，我只是过去感受一下被巨神碾压的恐惧感

参加省队集训，这真的是人能做出来的题吗?

第一天由于打 CF 打多了，看到 YES 和 NO 直接忽略大小写，痛失 32pts

后面两天骗分和暴力非常骚，随机和卡时全用了，结果发现这玩意儿好像挺好使，某一天的 A 假贪心还干过去 72pts ，最有意思的是粉兔第一份数据我是 72pts ，他重造数据我还是 72pts ，感觉我这假贪心有点厉害

然后靠着一张巨白无比的脸和稳如老狗的暴力，连续两天取得了 RK23 和 RK25 两个不错的成绩，甚至侥幸超过了几个省队选手

反正要是正常实力基本就排在 RK40 左右吧，基本就是垫底，别人切题如喝水，我切题......我切不出来题

右边坐了个巨强无比的小学生，学习很专注，考得也不低，我是不是该被pop()掉了。有一天他做着做着题突然“哇”一声吐了一身，看来是猫出的题太毒瘤了，给孩子都做吐了

一开始我和周围的兄弟都抱怨题太难听不懂，下午课疯狂摸鱼，因为根本不知道他在说啥。我只能听懂他在说汉字，并用我的语言中枢转化，完全无法调动逻辑思维的区域，持续掉线

“非省队的同学可以重连了啊！这个题比较简单”

“好，有没有思路？很明显这个题可以莫比乌斯反演......”

？？？？？？？？？？？？？？？？

对不起，是我不配听懂

但是最尴尬的是，我以为周围的兄弟都和我一样菜，结果发现左边是个省一，左边的左边是今年对线外 RK2 ！！！

sto ftq orz，太强了太强了，WC 银太强了太强了，今年就要去打 NOI 太强了太强了，苟富贵勿相忘啊

也正是因为他，我才真正认识到了与巨神的差距。Day8 的第一题，可以用 excrt 来维护区间内的同余方程，但是我不仅不会 excrt ，而且也不会 O(n) 维护区间。于是我请教巨神 fqt ，他一一解答了我的疑惑。但是我在自己想的时候又发现，这个区间 lcm 不好搞，我就又问他，他就很轻松的来了一句 ST ，我恍然大悟，他又顺带提了一句要用龟速乘防止爆精度。就是这样一份细节较多且在我看来推式子较难的题，他只花了不到半个小时就打完了，而且只有 ST 表写挂了。展现了敏捷的思维和强大的码力，让我对他“肃然起敬”

虽然基本上啥也没听懂，但是发现自己的科技树点的有点太偏了， dp 基本上学个差不多了，只是这玩意要靠多刷题；数据结构也学了好多了，但是基本上一个也没用着。反而平常忽视的数学和字符串，反反复复来回考，光一个序列自动机就看见三四回，粉兔第一天下午讲图论还讲了半个下午矩阵树定理。最悲惨的就是讲数学的那两天，啥也不会做

收获基本上就有三点吧：

$2.$ 找到了学习算法的方向，知道了哪些算法是常考的，可以转化为哪些模型来考（比如说 $2-SAT$） $3.$ 暴力和骗分技巧日益精湛，而且还学会了模拟退火，它将成为我暴力骗分的最后一块拼图 # 比赛日 早上起来发现还是一如既往地困，希望不会影响到比赛 来到比赛场地和兄弟们集合，拿到了衣服，气球和横幅（原来衣服和横幅都是统一的啊，不是私人定制的......） 八点半就进场了，但是要等到十点才能开始考。于是和 $hwh$ ， $lsq$ 开始上 $B$ 站颓废。给他们推荐了我觉得超巨的打野，他们却表示完全看不懂吗。只好跟着他们看“弱智”搞笑视频。不过为什么我也笑得那么欢，难道我也是弱智？ ~~最重要的是~~，我们桌子后面坐了一组男女混搭，而那个女生好像很好康的样子，穿了个短裙，腿也挺细的/se 等等，我好像是来比赛的，不过至少这样我就不会睡着了（不是） ~~不过 $lsq$ 表示也有同样的感受~~ 终于颓到十点了，开题，然后发现考试系统进不去 $QAQ

吓了一跳，还好重登了一波账号就能进去了

下面按照开题顺序记录每道题的操作：

A 题，无人提供思路，最终放弃

题意：给出一个棋盘，在其中有 n 个白子，询问是否能够吃掉这些白子（按照围棋的规则），可以就输出 YES， 否则输出 NO

顺序开题，一看 A 题是个围棋，而且又是求能不能活，感觉和那场月赛的 B 题很像，马上想到了 BFS 但是又感觉不太可做。可别又开到最难的题，吃一堑长一智，在思考了十分钟之后我确认了那是一道我做不出来的题。精通围棋的 hwh 也表示没思路，于是换题

G 题，思路提供：hwh，xmz，代码实现：hwh，结果：AC

题意：给出 n 个数，求这 n 个数的平均数，并保留 k 位小数，其中 n \leq 100,k\leq10^5。（答案向下取整）

在放弃 A 题之后，我们发现 G 题已经通过了十几个人，于是马上选择转战 G 题。然后发现这就是个大水题。一开始看到保留这么多位小数有点懵，但是很快想到我们可以不断的把整型变量*10然后再除以个数，这样正好向下取整，总时间复杂度 O(k)

H 题，思路提供：xmz，代码实现：xmz ，结果：AC

题意：你现在有 H 点健康值， S 点耐力值，在你面前有 n 只怪物，杀掉第 i 只怪物会掉 h_i 点健康值和 s_i 点耐力值，但是可以得到 w_i 枚金币。如果你的健康值 \leq0 ，那么你就挂了；如果你的耐力值 \leq 0 ，可以从健康值那里补。比如说你现在有 3 点健康值和 1 点耐力值，遇到一只打死会掉 1 点健康值和 2 点耐力值的怪，那么你的耐力值会变成 -1 ，这个时候为了保持耐力值不小于 0 ，就要拿 1 点健康值来补偿，相当于打完这只怪你还有 1 点健康值和 0 点耐力值。求在不死的情况下，能获得的最多金币数。其中 0\leq n \leq1000, 0\leq H,S \leq 500

由于我太菜了前面的题不会做，所以就一直投机取巧观察榜单，于是发现 H 题已经过了不少人，就悄悄地研究 H 题。看完之后第一思路贪心，毕竟那么多打怪的题都是贪心。但是很快我发现由于耐力值的限制我很难排序，所以根据经验，这应该是个 dp ，并且我很快发现了它是个二维背包板子题，只需要在转移的时候特判一下耐力值是否小于 0 即可。中间 lsq 对我的思路提出质疑，但是由于对自己 dp 水平的自信，我自顾自开始打，很快过掉了这题，lsq 也向我投来赞许而不甘的目光（bushi）

悄悄地就把这题过了，后面那哥们每次过一个题都吼出一声能让全场安静的欢呼，真心感觉不太好

M 题，思路提供：hwh，lsq，xmz，代码实现：lsq，hwh，xmz，结果：WA*3

题意：现在有 3 个 n*n 的 0/1 矩阵 A,B,C ，给出 C 矩阵，要求构造出两个满足条件的 A,B 矩阵：A 中的元素且上 B 中对应位置上的元素等于 C 中对于位置上的元素，同时还要保证两个矩阵中的 1 不是孤立的，即上下左右任意一个方向上的数也是 1 。n,m \leq 500 ，保证 C 矩阵的第一行，第一列，最后一行，最后一列全是 0

一看到构造题就有点害怕，害怕又是什么人类智慧题。第一遍看完题之后理解错题意了（英文题面差评），以为是两个矩阵内的 1 必须全部四联通，这样的话其实无形中大大增加了难度，于是一脸的不可做。后来机智的 hwh 及时发现了题意理解错误，大家一起口胡了一个类似随机的方法：就顺着枚举四个方向，能填就填，不能填散伙。感觉还挺对的，就写完交了一发

WA

心态有点炸裂，写了个 checker 对拍了半天也拍不出哪有问题，在最后一小时我才发现可能有孤立 1 的情况，而我们只判了第一个条件是否合法。改过来之后发现果然是这里挂了。由于模拟退火打多了，我对随机特别有信心，便提出用四个方向都跑一遍，绝对能过。但是打完发现还是会被 hack ，于是心态裂了。 hwh 提出贪心的找点，虽然我觉得这是不对的，但是由于时间不足只好让他打了。hwh 手速惊人，在 10min 内 rush 了出来，在最后 1min 点上了提交，我心脏砰砰直跳。可惜最终还是 WA 了，这玄学方法果然还是不太行啊

C 题，思路提供：lsq，代码实现：xmz，结果：AC

题意：如果有一棵树，每个节点可以染成黑色或者白色，如果一个节点被染成黑色，那么它的子树内所有节点都会被染成黑色，设这棵树不同的染色方案为 k （两种方案不同当且仅当至少有一个节点颜色不一样）。现在给出 k ，要求构造一棵树，满足染色方案是 k 。k\leq2*10^{18},n\leq10^5，其中 n 是构造出的树的节点个数

一开始看到这个题我一脸不可做，但是场上已经有很多人把这题过了，所以只好认真想这个题。想了十分钟也毫无思路，一直在乱七八糟地口胡。此时 lsq 大显神威，一波操作把这题秒了。具体就是如果我们考虑一个点，若这个点被染成黑色，就是一种方案；如果被染成白色就递归下去：如果当前方案数是偶数，那么可以开一个左儿子作为叶子结点，然后再去递归右儿子。这样做是因为一个左儿子如果是叶子结点，就只有两种方案。根据乘法原理就相当于把整个方案除以 2 ；如果当前方案数是奇数，那么就在下面加一个结点连上，就相当于减去 1 了。这样构造出来的树应该是 logk 级别的，可以通过这道题

D 题，思路提供：hwh，lsq，代码实现：hwh，结果：AC

题意：在一个 n*m 的方格图上有 q 个小正方形，每次询问将所有小正方形推到左边界和下边界后组成的组合图形的周长。就像引力吸引一样，比如：(1,2),(1,3) 的两个小正方形如果受到向下的引力吸引，坐标就会变成 (1,1),(1,2) 。输出前 1~q 个小正方形得到的答案。0\leq n,m,q \leq 2*10^5

一开始和 lsq 翻译这题翻译了半天也没看懂样例，结果 hwh 一眼就把这题题意和正解秒了，这波我完美拖后腿，质疑 hwh ，然后 hwh 飞速码完一发就过了，狂打我脸

正解应该就是每次操作可以继承上次操作的结果，开几个数组记录行列的正方形，加几个 if 判一下容斥就好了，其实这是本场第三简单的题

F 题，思路提供：lsq，代码实现：lsq，结果：没过样例

题意：给出 n 个字符串，求出有几对字符串满足以下条件：其中一个字符串作为另一个字符串的前缀或后缀后组成的大字符串，如果可以从中间劈开成为两个相同的字符串，则符合条件。0 \leq n,|S| \leq 2*10^5，其中 |S| 指每个字符串的长度

卿哥看了这题之后感觉很有思路，并口胡出了一个 nlog|S| 的算法，我总感觉有问题，因为这个题是很难的，整场比赛在封榜前提交了 140 次，而仅仅就只过了 9 个人，但是还是让卿哥打了。在最后 10 分钟打完了，可惜没有过样例

非常可惜，不过卿哥勇气可嘉。由于时间原因没来得及调，可能真的打的是正解吧

B 题，思路提供：xmz（但被众议否决），由于时间原因放弃思考

题意：给出 n 个点，每个点有一个权值 a_i ，i,j 两点之间的边的边权是 gcd(a_i,a_j) ，求最小生成树。n\leq2*10^5,0\leq a_i \leq 10^9

完了呀，这啥题啊，我只会 n^2logn^2 的暴力啊 QAQ 。一脸的不可做，于是把目光投向 hwh 这个数学巨神。但是他也表示无能为力。接着我发现这算是一个最优解问题，我可以用上我刚学的骗分神器——模拟退火

但是考虑到这个题单次更新答案的复杂度已经很高了，而且随机化过题的概率本身就很低，只能骗取比较高的分数，而 ACM 是没有部分分的，再加上时间紧张等等原因，最终放弃了这个思路

Result

最终友情队+正式队合起来算是 RK85 ，友情队中 RK6 ，在现场应该是 RK1 吧，毕竟我们过了的题都是一发过，而且不是第一队就是第二队先切了四个题，得了个 Cu ，算是不虚此行

当然大部分巨神都在省队集训没有来（tyytxdy），混个 Cu 我也挺满意的

我感觉这次比赛比之前任何一次模拟赛打的都好，因为我们完美体现了 1+1+1=3 的优势，每个人都竭尽全力，做出了巨大贡献，都是功不可没的。这场比赛没有 MVP ，又或是每个人都是 MVP

上面把每个题的思路提供和代码实现都列出来也不是为了突显每个人的贡献，而只是为了说明每个人都有贡献

闲扯

和 hwh ， lsq 照了几张相，开了个闭幕式就溜回省队集训了，剩下的一个小时又是啥也没听懂，干得漂亮

## Day 2 最后一天省队集训，没想到竟然奇迹般的完成了梦寐以求的任务——省队集训时场切一道题。其实我并不会这道题的正解， $n\leq2000$ 的数据范围我只打了个 $O(n^3)$ 的暴力，就算是 $CCF$ 刚换的少爷机再吸口氧也是不可能卡过去的。但是我发现这个暴力在随机数据下跑得异常优秀，大样例只需要 $0.3s$ 就能跑完，于是怀着梦想提交，~~反正我也不会正解~~ 中午吃完饭 $fqt$ 激动地告诉我我 $B$ 题暴力干过去了 $100pts$ ，我也非常激动。不过他就很惨了，忘记写文件读入输出而惨遭爆 $0

又是啥也没听懂的下午，习惯了

下午放学 yyq 和 fqt 都走了，挺舍不得的，期待 200 天后的 NOIp 再次同台竞技，同时奢望着能在明年省队集训的时候和你们一起坐在前四排

放学之后又和两位巨神老师交流了一下学习，反正总结就是：多刷题没有用，要多找一些在自己能力边界的题目来锻炼，最好是不能一眼秒掉但是思考上一两个小时或者三四个小时能独立解出来的题目，不要害怕浪费时间，这样才能真正提高水平。不过这类题目的难度标准不太好把控，一般四个小时还做不出来就说明这道题已经超出了我的能力范围，可以查看题解了

还有就是一定要构建出清晰的知识框架，对于每道题要清晰地认识到考察了哪些算法，并加以运用

Day 3

返校补文化课

完结撒花