HZEZ OIer Dilute 的故事虽然已经结束……
但是接下来是属于 HIT ACMer Dilute 的时间！
vp 了 18年的青岛站
开场发现 A 和 B 一眼不可做，但是 tyf 发现 M 和 J 是签到，在 tyf 写 M 的时候我也发现 C 是个小签到，于是快速把这三题都过了。
然后 zcw 会了 E ，但是交上去 wa 了，他觉得做法假了之后去看别的题了
但是我觉得做法没问题，调了半天最后发现其实是把 和 搞混 + 爆 long long 了。
之后我发现 D 是个好想不好写的题，期间下了两次机让 tyf 写了个 F ，zcw 写了个 I，最后成功在10点半前下班打cf去了。
（虽然我没打，zcw A 卡太久直接当逃兵了）
（唯一打了的tyf -2，基本等于三个人都没打）
vp 了 19年的山西省赛
感觉状态有些回暖，杀的很爽。
开场 tyf 开了 L ，迅速把到签上了，然后我看了 E 发现也是个签到。
然后就因为枚举范围写错寄了一发。
同时 tyf 也把 F 给过了。
然后发现 B 也是个简单题，只需要随便找一个入度是0的点跑一边dfs就行了（如果没有就随便找一个）
之后 tyf 开了 K，我发现 C 是个诈骗题，很快就过了。
之后看 J 题，发现贪心时被切断的区间都可以直接删掉，非常好写，于是也迅速过了。
然后去帮 tyf 看 I 题，我给他讲了一遍算法，我让他去写然后自己推 ba 去了。
结果这个 b 给自己绕晕了，于是我自己去写，他去鼓捣 D。
最后他还绝杀了，可喜可贺。
vp 了 20年的长春站
因为 zcw 不在，所以是临时的两人两机的自行车场）
开场之后 A D 两个签到，我和 tyf 一人一道迅速解决了。
（tyf D 还寄了一发，这个甜甜就是逊拉！）
然后我就卡了好久的 F。最后把 给压掉才过。
再过了一个小时左右 tyf 把 J 也过了。
最后一段时间我在看 L ，tyf看 C，结果双线程假掉，最后发现 L 题其实枚举 $a_1 \mod (k+1) $ 即可，不需要枚举 本身，判断也可以做到 的。
vp 了 18届浙江省赛
陆陆续续签完 ACFGM 五个签到之后
I 题仔细一想，发现实际上可以把他每两个圆环之间的问题拆分开来，针对三个圆环的情况直接特判，然后大力分类讨论即可。
接下来胡了一个 D 的奇怪算法（不过之后直接被证伪了）
正好这个时候 qzh 叫我们去打雀魂，于是就愉快的开摆了。
vp 了 19~20的香港站
具体的不记得了（毕竟写这段话的时候已经过去半个月了）
但是我只记得这个 K 我胡了个网络流做法，交给 zcw 写结果被卡常了。
vp 了 21年的哈尔滨站
但是到都没签完大伙儿都有事于是提前离场了。
这段时间的训练记录交给了给了 tyf 来写。
所以我懒得再写一遍了！
vp 了 去年的桂林站
开场看 A 发现是签到，于是直接拿下。
然后和 tyf 一起看 M ，我指出冒泡排序交换次数本质上就是逆序对之后我们就都会了，于是交给 tyf 写。
发现 E 题是个类计算几何状物，于是我丢给 tyf 一个算法让他写，结果之后他把我做法 hack 了，于是发现这题本质是个数论题，还是让 tyf 去写。
tyf 写到一半我发现 C 题本质只有两种情况，于是上了几分钟机过了。
在这期间 zcw 一直在猛猛调 G，我在过了 C 之后想了一个 J 的乱搞（但是是假的），甚至因为对拍写挂了导致没拍出错误来，tyf写完 E 之后就润去帮忙答疑了，心态非常爆炸。
调到块结束的时候 tyf 突然回来说 L 是个结论题，于是他花了十分钟过了。
之后直接把 J 换了个算法重写了一遍，终于过了，只可惜 zcw 的 G 没有过，6 题遗憾离场了。
vp 了 去年的绵阳站
开场看了 A ，看到 dota 背景以为是个签到题，于是大胆猜了一个结论然后成功 wa 了一发。
然后 zcw 看到 C 是个签到，快速过了。
我暂时放下 A 和 tyf 去看 G，然后我听完题面反应过来最多执行 次，于是交给 tyf 去写了。
结果这个细狗甚至因为数组开小 RE 了一发。
(黄豆，笑哭，前指.png)
然后发现 H 只需要构造一条斜向直线即可，快速过了。
然后 zcw 在调 M，和我后来想的 A 正解交替上机，然后先后过了。
之后我去看 D ，zcw 看 E，D是个简单题，但是被 cin 卡了一下常数导致调了好久，zcw的 E 在 wa 了几发之后也过了。
tyf 最后 10 分钟蓟县会了 J ，只可惜没有写完。
vp 了 去年的杭州站
开场我去看 A ，zcw 看 K , tyf 跟榜。
于是 tyf 顺利的把两个签到题给签上了，K 也是个相对简单的题，zcw 很快的过了。
之后我 A 会了一半，会算答案但是不会输出方案，于是丢给 zcw 去做了，他秒了。
于是我去看 C，tyf 去看 G，我把 C 给一眼了，但是各种写挂导致 -5 。
之后我和 tyf 一起看 G ，zcw继续调 A，tyf 发现 G 题只需要考虑 的情况即可，于是我觉得只需要找出环上的子树做树上哈希即可（事实后来证明其实得间隔着判断）
之后 zcw 去看了 M ，我和 tyf 看 I，zcw 的 M 胡了一个假算法，我在想了之后发现可以通过随机化把 n 可能的范围缩小到 1e6 的级别，就可以前后分段做了，于是过了。
开场看题。三个人都在比较短的时间内各发现了一个签到题，并在半小时内 1 发过掉了。
然后我开写 G，然后 tyf 给 zcw 讲了下 L 的题意，zcw 秒了，tyf 去看了 E。
我的 G 的 hash 因为一些奇怪的小问题爆了 3 发才过，zcw 的 L 树剖花了 10min 写一发过了。
tyf 的 E 打表找了找规律爆了 1 发也过了。
我的 B 我直接大力猜结论，然后结论被 zcw 一眼证明了，于是开写之后仔细一想发现需要一个最大流。然后又因为常数过大导致被卡了两发常，最后改了个奇怪的东西把边数 >>= 1 之后才卡过了
A 题想了一个神必 LCT 做法，因为我不会写所以丢给 zcw 去了。
（其实这篇的前半部分是 tyf 帮我写的）
vp 了 去年的香港站
开场我去看了 A，zcw 去看了 H，tyf 去看了 L，然后 H 是签到，于是 zcw 直接过了。
这个时候我发现 A 也是个读题难度大于想做法的签，而且非常好写，于是花了 5 分钟过了。同时我发现 E 题是简单题，因为是数据结构所以丢给 zcw 写了。
这个时候 tyf 把 K 秒了，但是实践证明他的做法是假的。
然后我和 tyf 一起看了一眼，然后发现正确做法非常好些，最后 tyf 爆了 4 发，然后我和 tyf 一起调过去了，然后我发现 F 也是个一眼题，因为需要高精所以丢给 tyf 去写 python 了。
这个时候和 tyf 交替上机的 zcw 也把 E 给过了，他自己同时把 L 秒了。
tyf 调完 K 之后开始写 F ，期间我发现 B 题巨好写，于是把 B 给写了。
之后 tyf 和 zcw 交替写 F 和 L ，然后因为 python 常数太大了被疯狂卡常。于是我重新写了一遍 C++ 的版本，然后过了。
就在我之后没多久，zcw 那边捷豹传来，他也过了，直接下班开摆。
tyf的忏悔：今天这场我打的很不理想。关于 K 题我错了 4 次。一开始想出来的做法比较麻烦，需要离散化求线段交。事实上也不需要。给卢说了一下做法，然后他很快就想到了一个简单的做法。然后连续死于一些边界问题，有点急了。F 题卢给我报了个时间复杂度假的做法导致写了半个多小时最后T飞了。
vp 了 2021年的上海站
开场一开始去看了 A。看了几分钟觉得不可做，于是跟榜去开了 E。把当时正在写 G 写到一半的 zcw 给踢下了机。
tyf：这个 D 有点熟悉？
我：已验丁真，鉴定为之前我被 qsy 薄纱那场周测的题。
于是和 tyf 重新讲了一遍做法，他直接过了。
tyf 把 I 一眼了，然后我去看 M，期间连续胡了两个假算法。和 tyf 交替爆了好多发之后把 I 和 M 过了。之后 zcw 断断续续写的 G 也过了。
tyf: 是可行的，但是如果把 换成 ，就会出问题，被这个地方坑了。
zcw 听说 H 是个数据结构题，上了 1h 机把他做出来了，期间我口胡了个 B。
B被卡了很久，最后发现根本不需要多项式快速幂。期间 tyf 还上了 10 分钟机把 K 给过了。
最后 8 题滚粗了。
tyf：这个 to practice 是什么啊？我点点看。
于是我们的 vp 记录就没了。
成功敲诈 tyf 一杯咖啡。
E 线段树维护每个区间上最左最右的未成对左括号和右括号以及已经成对的括号数量即可。
B 傻逼题，暴力匹配就完了
F 用可持久化 Trie 树来维护，每次相当于全局异或上一个值，在询问的时候处理即可
I Trie 裸题，没啥好说的
C 暴力 dp， 代表模板和当前字符串分别匹配到第 位的情况是否可行， 转移即可。
F 高维前缀和裸题，没啥好说的
E 暴力找出所有合法的数对之后做扫描线即可，主意树状数组要替换成分块来平衡修改和查询的复杂度
A 正解应该是线段树合并或者二位数点啥的，但我写了个奇怪的 bfs序 + 倍增做法，如果有时间专门写篇题解吧。
C 因为每次修改的 不降，所以如果一个数触发了取绝对值，之后每次肯定都会触发，那么先预处理出每个点触发取绝对值的时间点，之后用两棵线段树维护即可。
A 裸莫队，没啥好说的
B 裸带修莫队，没啥好说的
F 维护一个块内排过序的数组 ，每次修改暴力重构边缘块，中间直接全体打标机即可。
E 分块维护每个点弹到块外的位置，修改暴力重构即可。
G 分块维护每个块的桶，容易发现一次询问的答案要么出现在边缘块中，要么就是中间完整块的答案，而后者可以 预处理。
A, B, F fft, ntt, fwt 模板题，没啥好讲的
C 把模式串反过来，然后把 ? 设成 0，其他的第 i 位设成 ，然后发现就可以用类哈希状物判断是否匹配。
验题场，不能写
A Manacher 裸题，没啥好说的。
B 二分 + 哈希预处理每个点开始的后缀和原串的 lcp，然后枚举即可。
C 预处理和前一题一样，不过从维护一个最大值变成了维护一个set
E 处理出 next 数组之后预处理出不考虑重复的 num’ 数组，然后通过暴力跳 next 找出满足不重复的第一个位置，取那个点的 num’ 即可。
G 和 BC 预处理一样，不过需要一个树状数组维护一下。
为什么树链剖分和主席树会在同一天同一个专题的啊
B 用主席树维护每个数在每个点上最后出现的位置，然后二分即可。
A 主席树裸题，没啥好说的。
C 把裸题维护的变成树上从根节点开始的链即可。
G 树链剖分裸题，没啥好说的。
E 也是主席树裸题，不过空间卡的比较死，很傻逼。
周测。
L 用 棵线段树维护每个数每位是 还是 。
C 经典费用流题。每个点拆点之后两个点之间连一条有费用，流量为1的边和一条无费用，流量无限的边之后跑费用流即可。
I 傻逼题，排个序之后倒着贪心即可。
J 也是费用流，对于每堵墙建点，然后向汇点连两条边，代表第一次在这堵墙开窗不需要费用，第二次要。
N 暴力 dp 即可，没啥好说的。
感冒了，还巨 tm 困，写的都是以前写过的或者傻逼题，跳过。
A 预处理出每个数作为左端点能取到的最右边的端点位置，然后 表维护即可。
B 扫描线裸题，没啥好说的
D 维护每个点作为右端点，左端点的最优选，然后可以认为一开始是右端点为 ，左端点 ，最优解为 ，之后可以拆分成 和 ，维护一个堆，贪心地取然后拆分即可。
F 从后往前枚举，此时我们已经确认了哪些节点已经被去掉，直接树状数组维护当前还剩哪些数，然后二分即可。
G 可以认为所有 的数对于答案的贡献就是 c–，然后计算所有 的数的和，可以用权值树状数组简单维护。
马拉松。
H 找出每个可能成为信标的节点（显然贪心地找右边第一个比当前大的即可）然后直接算就可以了。
F 把每个颜色相同的极长段缩成一个点之后，只需要去头去尾之后选一半的即可。
D 显然只有四种取法， 型显然好处理， 型只要枚举那个 然后用 维护最优的行 / 列即可。
E 对于每个极长的连续段，如果可以赢右边的元素，那么就将至多 个移到右边极长段的右边，主意可能要和再有边的极长段合并
M 推出柿子之后发现其实就是求 和一个类似的东西，直接用树状数组维护即可。
J 直接大力 。注意需要特别处理在左半段或右半段之直接已经取到要求的子段和的情况，有一车细节。
J 经典状压，不多赘述。
G 发现肯定是基环树森林，然后我们对于每棵基环树，找到他环上的一个节点，钦点不选他，然后再钦点不选与他相连的一个节点，分别以这两个点为根进行 dp 即可。
C 二分答案，计算 的数里有多少个可以保留下来，这个是显然可以二分的。
A 直接树上背包，因为两个点只会在 处被统计所以复杂度是 的
B wqs 二分裸题，转换成选 条不交的链之后，因为每个点的度数最多是 ，就可以二分了。
网络流专场。
H 黑白染色之后变成二分图，然后求最小割即可。
A 可以转成对偶图求最短路，也可以直接最小割。
G 经典费用流问题，不多赘述。
B 把每个点拆成两个点，因为每个点肯定最多一个入的路径一个出的路径，然后跑最大流即可。
F 对于每个技术员，建倒数第一个修的他，倒数第二个修的他……然后可以直接计算每个人的贡献 = 他后面正在等的人数 * 修他的车花的时间
D 跑一遍 floyd 之后直接二分图匹配即可。
I 对于每个人，割掉连向原点的边代表放弃文科，割掉连向汇点的边代表放弃理科，之后根据剩下的连通性可以直接计算出在每种选择下，需要放弃掉哪些同科带来的贡献，直接最小割即可。
给我打破防了，不想写了
今天是0721节，你是0721高手
A 第一个不用说，第二种直接 exgcd，第三个是 bsgs 裸题。
B 也是 bsgs 裸题，只要把数改成矩阵即可。
C 写出 的表达式之后经过一定变换可以转换成经典 bsgs 问题，但是特判巨多。
G 数论大杂烩，先用费马小定理转换成求他的指数 的问题，然后用中国剩余定理把模数拆开之后卢卡斯即可。
博弈论腐乳迪卢特, 出列！
D 就是昨天的 H。
H 发现其 SG 函数有循环节 ，而且是连续 个 和连续 个非 ，于是就结束了。
A 假博弈，只用考虑左边和右边的各一个极长上升序列，考虑当前较大的那个序列头所属的序列长度的奇偶性即可，如果是奇数直接选，否则选较小的那个序列头。
G 暴力求 SG 函数即可。
D 可以认为左边半边是正的而右半边是负的，然后右半边的问号只要自带一个 就可以和左边的问号一起考虑了
I 令 为最大的 满足 ，发现如果 ，那么 ，利用这个性质可以快速求 SG 函数。
C 显然只有 以内的元素才有用，然后肯定是一个人填奇数的空位，一个人填偶数的空位，模拟即可。
E 发现每次移动棋子的 单调上升，于是暴力求 SG 函数即可。
今天是马拉松
J 考虑对于每次访问求出让其满足条件的最小的答案，容易发现这个就是两个相同元素之间不同元素的数量，用莫队即可。是不过正解似乎是二分答案（而且很好写）。
F 找规律发现答案的差分满足形如： 个 , 个 , 个 个 ，虽然我不会证明，但是写个高精就可以了有人瞎jb压位压挂了
C 容易发现肯定取的肯定是一个线段的最左边或者最右边，于是考虑从下往上 dp，只需要多一维记录一下有多少个取在左 / 右边即可。
D 逆天构造，枚举特殊的那种数，然后维护一个三元组 第一和排序之后的数组不一样的位置 $, $ 在上述位置改成的数 $, $ 特殊的数 然后根据这个三元组排序，选择最优的特殊数即可。
H 重量级歪榜诈骗题，本来应该是签到题，结果愣是没人做。实际上只有在 这段区间，即先手可以一回合斩杀的时候先手胜。
G 考虑强制选或者不选一个点的做法，直接从左边开始和右边开始分别做一次 dp，强制选择直接简单相加即可。然后强制不选就的情况下他的左边k个，和左边选择元素的右边k个（在当前元素的右边）内肯定各有一个被选中的元素，之后的枚举左边那个并且维护一下右边选的元素的最小值即可。
A 容易发现选择的的三角形肯定没有交点，于是用线段树维护一下在当前枚举到的点，选择三角形的左端点在每个位置的时候可以覆盖到的点的权值和即可。
E 斜率优化裸题，没啥好说的。
I 高位前缀和裸题，先枚举在哪一位再枚举具体的状态，可以保证不会重复算，
C 在 AC 自动机上做 dp，注意预处理每个节点走 fail 指针能走到的节点里边有没有模式串的终点。
在暑期集训的第二周的礼拜一……
我终于决定要重启这篇文章（虽然大概率只是三分钟热度）
今天是 tarjan 主题。
A 洛谷的缩点板子题 直接缩点跑完写个 DAG 上 DP 即可。
H 经典2-SAT 板子题，没啥好说的。
C 首先直接从 开始 tarjan ，然后在判断割点的时候多加一个判断 是否在子连通块内的判断即可。
B 用 map 把每个字符串用 的二元组表示出来之后跑一边缩点之后的 DAG 上 DP 即可
D 先跑一遍割点，然后发现对于每个非割点的连通块，考虑和它项连的割点数量，如果没有或者有一个，那么在其中任选两个造出口，如果有两个即以上，那么不需要在里边造出口，因为它肯定是被其他的连通块夹在中间，不管那些割点中哪个被挂掉都会有其他的连通块与其相连。
F 将每个双连通分量缩点之后容易发现答案就是
J 把每对认识的人和猫连边之后容易发现，对于一个强连通分量中的节点，如果其中一个人当了评委，所有人都得当评委，所以只有两种情况，一种情况所有人都在一个强连通分量内直接无解，其他情况肯定存在一个出度为0的分量，选那个分量里的所有人即可。
队内训练。
在一个 furry 朋友倾力推荐下 vp 了今年的威海站。
据他原话：真的不是因为什么奇怪的原因，这场质量真的很高
（果然签到题还是交给 lqr 比较好，他做签到真的快）
开局我开 A，417 开 E，结果我因为无限读错题意导致签了半天到没签上。
做完 A 之后我去和 lqr 一起开 G。
lqr：他会不会有循环节吧！
我：不可能，绝对不可能！
（上完厕所回来）
我：卧槽还真有，卧槽我会了
J 题我看了几眼发现可以分段做，于是开写，同时 lqr 开 C ，最后差不多时间做完了。
（这个时候我们本想发挥队伍传统艺能开摆，结果在我的强力 KFC 之下成功得将队伍掰回了正轨，这波立大功！）
然后我一边摆烂一边和队友一起想 I 题，过了好久之后我大胆瞎猜结论，结果在连续寄了五发之后过了。
期间 417 因为没吃中饭所以点了一碗麻辣烫
干他妈的，真香，当时真的好像上去蹭一口
然后去看 D，一眼发现就是个 B 状压，然后开始写，越写就感觉越麻烦。
最后在离结束 10 分钟得时候过了，欢声笑语中打出 GG（大雾）
好耶！终于上 IM 力！
（这两天可能是什么良辰吉日，Venus 晚上刚上黄金 我 CF 就上 IM 了
队内训练。
vp了去年的icpc沈阳站。
开场直奔 B 题，结果脑子一傻逼一开始只想到了前半部分的转化，然后 417 秒了 J 之后一听题意说她会了于是让她去写了，lqr也把 E 过了。
于是去开 F 发现 然后暴力即可。
跟榜发现 L 似乎不难，先容斥之后转化成求树上匹配数量，一开始想了个 的树上 dp，然后发现可以通过 NTT 优化成 的，然后通过在转移的时候全部以点值的转移，可以把 去掉，于是可以通过，后来我写忘记预处理逆元了写成 的结果卡常卡了半天。
我当时的心路历程：
我：先容斥一下，然后可以树上dp，但是这空间就是 的过不了
我：啊？ ？
我：虽然复杂度是 的，但是可以加个 ntt 就 了
我：哦 好像乱搞一下就 了，开写！
在旁边插不上话的 lqr ： 你这样显得我很呆。
后来发现好像正解根本不用NTT
过了 L 之后全队直接开摆了，虽然还有整整三个小时，但是一个人在打牌，一个人在打皇室，还有一个人在看 S12 。
DRX真的牛逼，看的我根本没心思回去继续打 vp。
今天是 2022 年 10 月 26 号。
距离我上一次更新这个博客已经过了两个多月。
我其实也没什么 xcpc 相关的东西要写的。
虽然我这两个月也写了些题，但是总是因为各种各样的原因发到博客上来；
主要原因是我换了电脑 把博客迁移过来很累的啦 而且我也懒得把前两个月的题目总结一下
直到今天的俄语课上……
我们的老师，她说了一个神秘的单词——————
Ълог
「啊这个单词意思是 博客 」
「欸我们班上有同学写博客吗？」
我举起了手，但是老师似乎没有看到。
「现在好像没什么人写这东西了。」
「我以前有个学生经常写，他好像是搞什么信息学竞赛的，很厉害。」
于是我终于想起来了我的小可爱博客。
并且把它移到了我的新电脑上。
好耶！
写完之后又发现出现了奇怪的问题。
苹果的电脑有个机制 会把文件保存到icloud上面而把本地的文件删掉。
于是我的头像便惨遭了毒手。
我还得从手机相册里把我的头像的高清原图找出来发给电脑。
icloud ！我要把你那肮脏的服务器！砍断！切开！剁碎！
比赛的时候多测没清空，甚至过了几天才发现，我的评价是：寄！
肯定成一个环，绕若干圈，然后可以发现最后选择的环长一定是一个质数，直接 爆淦即可。
高三毕业的暑假里突然想起自己还有一个blog。
于是打开了那个熟悉的网址，意料之外的是这个域名竟然一直没有过期。
而意料之中的是，虽然博客还在，但是包括评论系统，相当一部分的图片和友链都已经挂掉了甚至在上传这篇文章的时候还遇到了github上的ssh key 离奇消失的奇怪事件。上一次更新是两年半以前的事情——那好像是上个世纪的东西了。
接着我翻看了一下自己过往的文章。
看着初学OI时期的青涩的题解，那些是我看着可以扣地板扣出三室一厅的黑历史。
看着随着我OI水平的提高文风日渐成熟（虽然也没好到哪里去）的文章，我仿佛回到了坐在二中机房里，一杯水一台电脑，一个bug调一天的时光。
看着各处打比赛的游记，死去的回忆突然从我的脑海中苏醒，ZJOI时mwh「你瑞兹爸爸来啦！」的战吼仿佛又回荡在了我的脑海、PKUWC时和wxw和sooke的夜晚蹦迪似乎就发生在昨天、想到了NOIp / CSP 时的欢笑与泪水……
回首往昔，我的OI生涯虽然称不上成功，但在我看来也并非是彻底的失败。
但是高中阶段的OI对我而言已然是过往云烟，我们应当向着未来去看。
换了新的头像，重新启用这个百废待兴的博客，不论是在日常生活，学习上，还是 OI / ACM 的方面上，我都希望我自己也可以成长为更加成熟，更加可以独当一面的人。
也许我还可以在大学，在ACM的舞台上发光发热。
这篇文章将会持续更新，更新我作为 ACMer 时写的题，同时大概会作为这个博客的更新日志使用吧。
Dilute 写于2022年8月1日。
