这次 csp 对我来说意义还是挺重大的。（但我还是太菜了）

坐标：GD。

目标：提一。

Week -4

初赛也是不出意外地双过了。一开始压力还挺大的（毕竟去年 J 没过 S 压线过），一去考场发现出题人放大海了.

Week -3

也是开始停课了。不用补 whk 作业还是挺爽的，毕竟玩了一整个国庆没写作业。一开始还是比较颓的，没怎么学习。主要贡献就是复习了一下平衡树和网络流，然后学了一下可持久化 FHQ Treap。

10.8 入门赛 #1

ACM 赛制，总共 15 题，全是黄题以下，大部分是去年的入门专题。主要目的应该是找回码题手感。

开局倒序开题看 T15，区间修改、单点查询，准备线段树直接冲过去，发现数据范围 1e7，打算打个离散化，然后白白浪费了十分钟。最后发现好像是差分树状数组（但我居然把树状数组忘干净了），果断放弃回看 T1。

T1 是个数学题，感觉题面有点抽象。手玩几组样例发现就是判断网格图两点连线上有没有整点，猜了个结论直接秒了。

T2 也是数学题，洛谷上看过原题，但是感觉太麻烦就没做。继续跳题。

T3 也是 tm 数学题，看到只有 10 的范围感觉可以打表，打了一半发现好像是杨辉三角。写完一测样例居然不对，仔细想了一下原来没考虑完全。于是打算放弃思考，使用纯粹力量打个搜索过了。

T4 一眼二分，洛谷也做过原题，考场上打了一半然后发现不会写 check，觉得浪费太多时间继续跳题。

T5 巨水题，忘了线性做法，然后打了个二分秒了。

T6 一开始想 dp。但是由于当时我 dp 很差，再加上时间所剩不多，果断跳题。

T7 马走日，也是水题。看了眼题面感觉要双向广搜。但是来不及想那么多了，先打了个 dfs，极限数据死翘翘。换 bfs，样例过了。一交 WA，懒得调了，继续跳题。

T8 第一眼好像是背包，然后就跳了。

T9 发现是 LIS，跳。

T10 第一眼没看到翻译，以为要自己翻译，而且当时 CF 的题也交不了，跳。

T11 这道题原题也看过，考场上感觉好熟悉，但好像是树形 dp，继续跳。

T12 因为最近刚学费用流，SPFA 板子在脑子里还热乎着，秒了。

T13 第一眼双源最短路，又看了眼数据范围，Floyd 肯定过不了，而且来不及了，跳。

T14 也看过原题，一眼最小生成树。但是一开始没想到 K 和连通块的关系，所以也没打。

然后就结束了。被全机房打爆了。基础太差的下场应该莫过于此。

后来做回的时候发现没做的题都是巨水题，而且犯了一堆弱智错误，对自己的实力感到深深怀疑，emo 了一晚。

Week -2

大部分同学也都开始停课了。开始对自己颓废行为感到十分焦虑，对未来发展感到懊恼，于是开始努力刷题。巩固了之前学过的东西，写了个平衡树学习笔记避免自己忘记，开始猛复习 dp，顺便学了个模拟退火。

10.12 模拟赛 #1

好像是之前某套洛谷模拟赛的题。以为 J 和 S 都要打，于是先开了 J。

T1 纯模拟水题，五分钟秒了。

T2 第一眼好像是找规律，手玩几组样例，越来越没规律可循。再仔细看一眼好像可以平衡树，花了半小时打了个 FHQ Treap，赛时过大样例了就没多想。

T3 好像是贪心，但不知道怎么贪。然后发现对于排列每次影响答案的只有一次操作，于是打了个模拟退火，没过样例懒得调参直接放弃。

T4 一眼 dp。先打了个二维的，推了一遍感觉没什么问题，一测样例发现不对，仔细看了好久还是没想出来，以为是样例问题。后来又看了题面，发现买的票不一定只能在下一次花掉，心态直接崩溃，交完开看 S。

预期得分：100+100+0+0=200 pts。

时间所剩不多，这个时候旁边的人告诉我过 S 的只要打 S，心态继续崩溃。

T1 一眼线段树，但维护了一堆恶心 tag，整场比赛都在死磕，但最后还是没过样例。

预期得分：0+0+0+0=0 pt。

然后比赛结束了，放学回去继续颓废。

实际得分：

J：100+50+0+0=150 pts。\ S：35+0+0+0=35 pts。

J T2 的平衡树也是挂了，没想到常数这么大，10^6 都只有 50 分，警钟敲烂。

后来做回了 S T2 发现是一个很好的经典树形 dp，于是顺便写了个题解水咕。

Week -1

时间仅剩两周，片刻不容懈怠。继续刷了很多 dp 训练自己的思维，做了很多树形 dp，学了一下换根 dp。这里推荐一篇讲得比较好的学习笔记。对着考纲补了一些知识点。做了一些去年的真题，顺便解决了一道去年挂 50pts 的历史遗留问题。

10.17 模拟赛 #2

说好模拟赛是 S 的，放的题是 noip 模拟的，人是在睡觉的，分是挂得死死的。

T1 一看这名字差点想种一排。第一眼好像数学题，仔细想想是贪心。先对每个高度分解质因数，再利用考场结论全靠猜定理，每次把 k 的质因数分给一个没有这个质因数的高度就好。然后发现有一堆细节问题，改来改去死活没过最后一个大样例。坐我旁边的 @nnn233 大佬已经开切 T2，只好寄希望于 rp 直接交。

T2 恶心构造题。一开始 @nnn233 靠着打表找到了规律，本来要直接往下切的，突然被我 hack 掉了。经过一番简单讨论，仍无果，含泪拿 10pts 继续往下看。

实际上这个时候比赛已经快结束了，略扫了眼 T3，看到几个关键词：区间、第 k 小、排列，猜是主席树，但是看了数据范围感觉不太可能，结束前大概五分钟看懂了题意，继续往下了。

T4 赛场上听人说是黑，一眼看到了麻将（大模拟症差点发作），又一眼看到双人博弈，没来得及理解题意比赛结束了。

预期得分：20+10+0+0=30pts。

实际得分：50+10+0+0=60pts。

赛后发现 T1 贪心策略错了，我是把 k 的质因数全部分给质因数含量最少的 p_i，但实际上是一个个给，挂 50 分。

10.18 入门赛 #2

洛谷官方的入门赛。和同学一起玩的，每个人随机四道题，谁最后一个做完有惩罚。我的题是 T1、T2、T4、T8。虽然最后还是不出所料地被全机房吊打，过程总体还是比较欢乐的。当作赛前放松吧。

Week 0

备战最后一周了。周一学校组织了秋游，本来不是很想去的，但由于某种不可控的力量我还是去了。玩了一天，什么过山车跳楼机包不敢玩的，只敢玩 pvp（

10.20 模拟赛 #3

某人因太早起不来，于是就叫我们星期天早上七点起床回学校打上午和下午的洛谷 MX 线上赛，彻底破防。

上午

T1 脑中稍微具象化很容易想到正解，求最大和次大值即可，秒了。

T2 一开始没什么思路，仔细重读题面发现对于黑洞的每个轴的坐标是有上下界的，想到了 2^n 相关的东西。旁边的 @nnn233 已经过小样例，遂感十分慌张。进一步想到有线性做法，统计每条轴的坐标上界多出来的部分乘起来就好。蓟县过掉所有大样例。

T3 第一眼题面又臭又长的恶心大模拟。想到每次都需要去减一遍所有的 k_i，还要判断蔓延的时候是不是在湖旁边，深感无力。转去看特殊性质，一眼看到了没有湖的性质，还以为输出 0 这么多分。打一半又想到只要有树连在一起就可以都活，只是不会蔓延而已。打完了手捏 hack 感觉没问题，但没过大样例。继续看有没有拿分的点，发现有两个只会种一棵树的点，直接看蔓延的极限就好了。遗憾的是还剩十分钟仍没过大样例，直接放弃。

T4 一眼不会做，发现有模数为 2 的点，又想到操作完全镜像的话一定也是合法的，所以答案为偶数，直接输出了 0。

期望得分：100+100+0+4=204pts。

实际得分：90+100+0+0=190pts。

T1 由于没判一条线段完全覆盖的情况挂了 10pts，警钟敲烂。T4 由于没判 n=1 的情况挂了 4pts，服了。

中午吃了顿教师餐（星期天学生食堂哪有饭啊）。

下午

T1 一眼线段树，每次翻倍想到倍增。但后来发现具体的翻倍和回合有关系，打了个二分水过去了。测了一下蓟县数据发现跑得有点久，有点慌，但又想到学校机子比较烂，稍微卡了点常就继续了。

T2 没看懂题面，有点烦。听 @nnn233 说性质 A 是最大子段和，发现之前的最大子段和还没过，赶紧复习了一下，也不知道过了没，去洗澡了。

回来的时候还剩半小时，看了一下 T3，好像打个线段树具体判一下可以骗点分，猜了点结论，没过大样例，直接放弃。

预期得分：80+8+0+0=88pts。

实际得分：100+0+0+0=100pts。

洛谷神机还是没让我失望，最大子段和也不知道为什么炸了，懒得管了。

10.24 模拟赛 #4

终于是肯自己组题了。赛前最后一次模拟，至关重要。

T1 怎么那么眼熟，第一眼给就我怔住了。就算是原题也别给这么最近的题啊。大概十分钟切了。

T2 第一眼是平衡树。一开始叕看错题，以为是区间反转而非翻转，好心的 @nnn233 看到后直接指出错误。感觉浪费太多时间直接跳了。

T3 又是最近做的原题，但好像没过。于是打了个暴力建树直接跳。

T4 最脑抽的一次。第一眼居然没看出来是什么玩意，回去看 T2 了。

接下来一直死磕 T2，换了线段树后维护了四个恶心 tag，一直没过样例。这个时候 @nnn233 好像已经 AK 了，被打爆了 %%%。

最后五分钟放弃了，打算看一眼 T4。仔细一看是换根 dp 板子，发现后狂打，比赛结束仍没打完，原地【数据删除】。

预期得分：100+0+72+0=172pts。

实际得分：100+0+72+0=172pts。

Day -1

明天就考试，有点小紧张。看了点之前做过的经典题，对着 @nnn233 的笔记学习了一下 Tarjan，补了点题，下午比较早回去了，颓废一晚上。

CSP

上午

好像没睡醒就去考场了。

T1 一眼题，三分钟过大样例。一开始感觉有什么坑，造了点 hack 发现好像没问题，浪费三分钟。

T2 两眼题，一眼看题面一眼看范围。五分钟过了大样例。

T3 一开始感觉有点抽象。第一眼想到要字符串，先打了个记搜，然后发现有点问题，直接把值拼接好像会导致结果有问题，去掉记忆化居然过样例了。测了一下大点的数据，卡到起飞。然后想到记搜和 dp 不是一家的吗，又开始想了 dp。简单推了个式子记忆化加预处理，勉强降了一点常数，但是还是很慢。然后就想了特殊性质，发现只有 8 需要花 7 根棍，不难猜出性质 A 就是全放 8。然后又想了一下性质 B，没有花费 1 或 8 的数，但是可以用比较小的 1 和 0 凑够 8 的花费，简单对拍一下没有问题。但是测了蓟县数据还是跑了一秒多，有点慌，希望 ccf 机子能快一点。

就在这个时候，监考员开始下来搜每个人的袋子。然后我由于没睡醒忘记检查袋子，把教练给的《防爆〇攻略》带进了考场，监考员看到后面色难看，我直接原地【数据删除】。被监考拍了准考证和资料，上报上级。心里开始慌乱，不过善解人意的监考简单安慰了我一下，后来也没下文了。彻底丸辣！

上了个厕所解决肠道里的残留。回来继续紧张地看题。

由于当时心里非常的慌乱，神情非常的紧张，所以也没怎么看 T4。简单看到了什么子序列之类的，简单猜大概是个 dp。打了个随机数开始睡觉。

预期得分：100+100+90+0=290pts。

下午

带着紧张和激动回到了熟悉的考场。

T1 一眼大概线性做法。一开始看错以为是活的越多越好，发现样例不对。先打了个排序，猜是尽量打自己的前驱，但打完发现没过最后的大样例。发现还需要维护上次杀到哪了，尽量从上次的地方开始杀，然后再往后杀直到不够杀完剩下的。打完半小时过完大样例。

T2 第一眼差点就放弃（物理太差的后果），有点像二分。先打了个 2^n 暴力，发现好像只能过一个点，去想了特殊性质。看到性质 A，发现加速度为 0，那就只能是要么一开始就超速，要么就一直都不超速，最优策略保留最后一个检查点，简单过了性质 A 的大样例。然后估计当时脑抽了，没仔细看后面的特殊性质，而且当时以为 130pts 已经够高了，就直接跳了。

T3 第一眼大概是 dp。列出来一个非常抽象的式子。刚想到 \mathcal{O(n^2)} 优化成 \mathcal{O(n)} 沾沾自喜，手玩样例发现有后效性。懒得改了。但估计又是脑抽了，连暴力都忘记打了。

T4 用剩下的时间看懂了题意，打了个随机数。

最后再检查了一遍 freopen，在虚拟机上跑了一遍没有什么编译问题。

预期得分：100+30+0+0=130pts。

后来跟同学讨论发现全机房就我分最低。J 倒没什么问题。S T1 居然求个众数就可以了，T2 的性质 B 做法和 A 是一样的，为自己的脑抽付出 20pts 的代价，正解真是二分超速区间。T3 出考场才反应过来错失 20pts 暴力分，后悔不已。被自己菜到了，又 emo 一晚上。

后记

出分了。实际得分：

J：100+100+90+0=290pts。\ S：100+30+0+0=130pts。

大概率目标无望。noip 也别想了。

过去的事情就让它过去了吧，还得补 whk 的课。明年见。