sdyzpf
2024-11-04 11:22:55
最后一年 NOIP 了，CSP 考炸了一定是因为我没提前写游记（），遂决定在 11 月 4 日开始本文的创作。
用小号打了 CF div3，AK 了，比赛结束后发现自己不在 trust participants 的榜单里，以为被 Mike 迫害了，准备接受审判了。上午到机房 @PengAo 告诉只有打了五场以上的 rated 比赛才能进榜。果然我号还活着，小号上 expert 了。
模拟赛情况：
A 题简单最优化问题，写了个记搜秒了。但很多大佬，包括机房内同学写了错误的贪心，挂成 10 分了。（赛后讲题：如果是写了贪心的同学，那你能获得 10 分的好成绩，能过
B 题二维平面内求与 x 最接近的值，想了半天不会啊，交了个双 log 的树套树，有 60 分。赛后听正解是换维扫描线，怎么赛时就没往这方面想呢（）。
C 题写了白给的 30 分暴力走人。
D 题同样也写了白给的 30 分，是个 DAG 上 DP，但是 sub1 数据锅了不是个 DAG，并且 sub1 和 sub2 有子任务依赖关系，然后就喜提 0 分了。
今天有两场 XCPC，看了看学长们的情况。惊奇的发现和有一大学位大连理工的选手和我们教练同名。
今天没什么比赛，上午在学数数。
下午查分发现 CSP 没挂，挺好。就是 D 题 0 分也太丑陋了吧。
模拟赛情况：
A 题题面锅了，不过机房同学们很快就根据题目名称和小样例猜测出了题意 （然后这个锅到了比赛快结束的时候才修）。是个期望 DP，可以用数论分块优化。但是一开始没有套根号分治所以觉得复杂度有问题，想了半天才意识到可以根分后再数论分块（这两个东西契合度这么好为什么不想啊）。
B 题写了前两档部分分，第三档是个 2-sat 没想到。正解是大学拓扑排序后贪心构造，但这个贪心赛时觉得很不对啊，讲题的时候说可以借助 2-sat 的构造去理解（2-sat 构造部分我逃课直接背结论的报应来了）。
C 题指数级暴力挂了，只拿到了一档本质不同子序列数 DP 的分，听完讲解只能说整到题目我的思考方向就完全是错的。
D 题分治题。然而两档该拿的部分分没拿到，对 01 串偶数位 flip 的套路都见过多少次了，怎么该往这方面想的时候想不到，不该想到的时候满脑子都是这东西。此外，构造矩阵进行哈希判括号匹配我怎么也给忘了。
晚上应该会大学继续写数数题，再去补一下 2-sat 的构造正确性证明。
update:补完了，并没有搞懂字典序最小 2-sat 的贪心为什么是对的，学习博客学到了证明显然和请读者自行证明。
上午做数数题，其中一道题标算是容斥+矩阵快速幂，我用了 FWT+矩阵快速幂解决，发现题解区没有和我一样的做法，写了篇题解。
下午听课，讲的是 DS，发现第一道例题就是前两天刚做过的。例题里还有一道区间值域连续段数量，口胡了，假掉了。质疑 div1 最后一题的难度我怎么敢的啊。
晚上被各种思维题创，似掉了。
模拟赛情况：
A 题乍一看是个 DP 题，有一档部分分是 P3188，写了。然后就卡住不会了。正解是个智慧贪心。实际上可以在 P3188 的基础上加以优化。打表发现这东西有凸性，直接上闵可夫斯基和就行。但是这个凸性的并不显然，证明绕不开上文所述的智慧贪心，所以此做法非常不本质。
B、C 赛时只打了暴力，D 题会 50 分，但是这场不知道为什么早上八点才开，为了不延误吃饭时间所以我没打（）。
晚上做做+贺贺简单图论题吧。
上午在贺简单图论题。发现洛谷次短路板子题解里出现了这样一种做法：将堆优化 dij 中的 vis 数组去除，改为判断 dis2[i] 是否与 w 相等。感觉复杂度假完了，有点像给 spfa 套了个堆然后加了个玄学剪枝。
下午发现自己之前出的题目的数据咕了好久，造了。
模拟赛情况：
A 题是个均摊题，不是非常难。
B 题是个实现起来不难的 dp 套 dp，但是这个状态数感觉很反直觉啊。反正最后跑得飞快就是了。
C 题有一点细节的 CDQ，赛时脑子变异没想出来。
D 题是观察题，但是 CF 数据能过的代码会被 hack。
ABC 情况：
C 题罚时 4 发，从头假到脚趾尖。
E 题没做出来，该退役了。
G 题一眼轮廓线然后就没有然后了，写完 F 已经来不及了。
CF 情况：
A 秒了。
B 被骗了一小会儿，然后意识到了。
C 题一开始想二分来着，后发现没必要，贪心的考虑一个简单的结论后就能做简单的 DP 了。
D 题想了一会儿，把问题转换成二维平面上问题，感觉思考方向有问题，不太会。
E 题打了个 2 的表，发现除了质数都能表示出来，很神奇啊。想了想证明，证明是简单的。顺着证明想了想其他情况，就做出来了。
回去想 D 题，思考为什么有树和一条边都不剩了两种情况，这或许说明了可以先删边，然后基于一条边构造。想了想会了。
开 F 题，观察到答案和连续段长度奇偶性有关，然后就不会了。
题解被打回了，找了一圈发现有个 latex 后面的逗号打错了，哭。
晚上 CF 时间太阴间了，没打。
上午口胡了一堆简单图论题，晚上贺吧。
下午讲课刚好讲了上场 div1+2 的题，只能说难度够恐怖的。
VP 了一下 CF，整个人好难受，前三题秒了，写第三题的时候已经难受起来了，简单的代码写了 25 分钟。第四题已经完全没有脑子思考了。
晚上回家吐了之后舒服了很多
模拟赛情况：
A 题是我第一次手写高精度，写了半天，离谱。
B 题多手玩一会儿就会了。
C 题写了暴力 DP，性质观察少了，观察完就是个比较简单的线段树整体转移。
D 题移球游戏，不想看。
晚上和同学 VP 了一场 ICPC，被题目橄榄了。简述一下：
A 题签到题，我写的唯一一道题。
B 题逆天结论题不会。
C 题逆天结论题不会。
D 题是个特殊图上的最大独立集。一开始以为是个弦图，然而并不是。经过一些贪心之后能转成二分图。
E 题不会，但是机房大佬 PA 通过各种启发式贪心通过了，是正解，膜拜。
F 题签到题。
G 题换根题，但我胡了个码量巨大的双老哥做法，又被 PA 的小码量线性爆了。
H 题看都没看。
I 题不会题，将全排列按逆序对个数和字典序大小从小到大进行双关键字排序，求第 k 大。
J 题签到题。
K 题签到题。
L 题不会题。构造一个数独使得进行一些行列交换操作后和原来同构。
某位同学不知道怎么模拟置换的过程，给我教红温了。
随后他又试图证明一等式：
机房内其他人：？？？
晚上 vp 了成都站，切了七题切得比较快发现刚好金尾，就提前下班了几小时。情况简述：
A 题签到题，有点细节，甩给 Floze3 写了。
B 题 PA 写的。
D 题可做题，但是提前下班就没想了。
E 题换根题，本来想甩给 PA 写的但被 PA 拒绝最后自己写了，吃了一发罚时。
G 题我会了之后，发现 PA 已经写上了，而且这不是这场第一次撞题。
I 题小清新数据结构，Floze3 甩给了我，我甩给了 PA，最后 PA 很快就一遍过了。
J 题模拟题，我签了。
K 题费用流题，我甩给 PA，PA 觉得跑不过去，我们最后都没写这题。看题解后出题人被怒斥，费用流题目数据范围开太大了。
L 题 PA 签了。
模拟赛情况：
A 题是曾经 MX 的 A 题，做过。写代码的时候发现自己代码出现了问题，但因为还有其他锅就去修别的锅了，修完其他锅后便通过了所有大样例。然后我就把最开始找到的锅忘了，100->0。
B、C、D 都不会，太困难。
洛谷比赛情况：
A、B 都是简单题，秒了。
C、D 不是简单题，困了。
今天除了 CF 没什么比赛，重学了遍 wqs 二分，现在脑子里算是比较清楚了。晚上记录下小号打 div2 的情况吧（不知道小号能不能顺利上 CM，本人中了 CM 诅咒，可能 IM 诅咒也要来了）。 div2 情况：五题，没上 CM。
A 题 lis 板子。
B 题逆向考虑就是小清新诈骗题。
C 题创人构造。以为 101 一下都无解然后猛吃罚时。
D 题小清新 DP。
E 题小清新 DP，写了带 log 的，实际上和合并果子一样，容易优化成线性。
F 不会啊。
模拟赛情况：
A 题卡精度题，差评。
B 题不会。
C 题是拿之前考过的一道神仙期望 DP 改的，改完后又不会了。
D 题看上去是比较传统的数据结构。
ABC 情况：六题，手速慢了，感觉所有题都挺简单的，收获了第一场
第二天早上去打市赛，学弟问我为什么昨晚没打 G 题，他觉得 G 比 F 简单，我去看了眼，好像确实简单。
市赛内容我觉得精彩到有必要单独开一篇游记讲讲了。
市赛游记
晚上开小号打了 div3,感觉这场整体都很简单啊，但 AK 的更慢了怎么回事呢？
下午验了场模拟赛，很简单。
晚上打 ICPC，六题下班。我签了 A 题，然后 B 题写了发错解。B 题可以带状高消，但大家都没去写。
模拟赛题比较简单，略过了。
ICPC 的题解出来了，还没仔细读，晚上读一下。
给验了的题加强了数据。其中一道题计算过程中是会爆 long long 的，但是最后结果在 long long 范围内，导致溢出不影响最终答案。
发现验题时不会的 D 题其实很简单，哭了。现在看当时脑子好糊啊。
上午信心赛同学们都被 D 诈骗了。 下午不想再碰图论了决定把我的欠的几道数数题写了。
上午模拟赛：
A 题是笛卡尔树上简单 DP。
B 题是排列计数，可以转成数合法的笛卡尔树个数，遂区间 DP。
C、D 题不会。
下午终于把反射容斥弄懂了。
晚上复习平衡树。
上午模拟赛：
A 题是一个我熟知的结论，但由于我结论是背的没想过证明而这题涉及到比较本质的东西，一开始写了个
B 题是经典挑战 NPC 环节，特殊性质藏得挺深，最后卡着时间切了。
C 题一眼平衡树维护矩阵乘法，会 T，二眼平衡树维护置换，能 A。本以为这题就这么秒了，结果平衡树分裂的时候调用左儿子的大小写成了调用父亲节点的大小，因此调了 30min。
D 题以前见过，但不会做。
晚上有 ABC 诶，已经连下五场分了，那感觉第六场就在今天。
上分了，不在今天，但在明天。
ARC 只切了一题，下分，我真棒。
CF 切不出第六题，下分，我真棒。
模拟赛只会 T1，我真棒。
模拟赛只会 T1，挂成 0 分了，我真棒。
晚上 AGC 不敢打，我真棒。
发现不会楼房重建了，看懂了自己以前的代码，我真棒。
写游记为了灌水写了这么多“我真棒”，我真棒。
模拟赛情况：
A 题老套路了，和为
B 题是动态加边求树的直径的板子。
C 题发现需要维护的两种操作为取 min 和加法，随手捏一捏矩阵就出来了，上线段树秒了，一遍写对是真爽啊。
D 题通读题目，发现是 0/1 背包，特殊性质是每个物品的体积较小。开始的思路是将相同体积的物品合成泛化物品，用闵可夫斯基和合并，假了。 然后就完全不会了。
正解是像单调队列优化背包一样取模后分组，此时就有决策单调性了，可以乱做。
晚上在练 USACO 的题。
发现早上 A 题洛谷原是个紫，逆天。
模拟赛爆 0 了，怎么回事呢。
感觉星期四让教练组一场信心赛就差不多了。
下午写平衡树题一发过了非常爽。
晚上能不能写掉三题啊。
上午模拟赛痛失 AK。
A 题是启发式的贪心。
B 题是简单 DS，不知道为什么 CF 有 2800。
C 题是简单贪心后 DP。
D 题是经典的 dsu on tree。
赛后发现我没有 AK，怎么回事呢。
我 D 题的主函数消失了，怎么回事呢。
全机房只有我没 AK，怎么回事呢。
快到我 OI 生涯最重要的转折点了，最近沉不下来心写题。
复习了树上链交。感觉前几天模拟赛都挺适合我的，让我不太熟悉的东西都敲了一遍。
最后一天了，在机房再试下 noilinux。
这会题目下发没出锅，令人欣慰。
先看了第一题，吓人啊。本来以为会是和词典一个难度的东西，结果想了想并不是。发现自己并不太会，想了会儿又会了。于是就写啊写，很快就写完了。肉眼 diff 了一下，怎么有几个不一样？差点被吓死了，以为做法假了。结果发现我的输出比答案更优，那没事了，应该是写假了。修了修过了大样例。
开第二题，读完之后发现可以按照关键点分段，每段的方案数是独立的。想到这里就大概知道这不会是什么难题，肯定是我能切的题，于是去上了个厕所冷静了一下。回来发现是个等比数列求和，想着最后有时间的话可以写个光速幂，但最后并没有时间，还是快速幂。
开第三题，不会。
开第四题，不会。
最后想正解无果，写了 28 pts+ 32 pts 的暴力。最后时间在写 D 题整体二分，没调出来。赛后由同学得知我整体二分复杂度还是假的，那没什么遗憾了。
D 题场上我并不知道 A 性质大样例满足 B 性质，所以没测。感觉 B 性质的分可能会挂。
update:没挂分，但是卡着队线，和我一样卡着队线的是两位铜牌爷，队线外还有个银牌爷，要死了。