Misaka16172's Blog

引子 美好的时光曾流过我的身体，我便心满意足。 每位 OI 选手可能都看过无数前辈写下的墓志铭。但或许到了由自己提笔的这一刻，感触才最为深刻。 尽管与 OI 相伴的时间相对短暂，但在这次旅途中得到的东西对我的某些思维和行事方式造成了深远的影响。 我是一个感情来时热烈，去时却健忘的人。许多儿时重要的事件，现在再去追忆却也只能大概查询到一个粗糙的轮廓。因此我的过去有一半都活在屏幕的另一端。对我来说，防止这段时光退化成几个难看的分数或许是这篇文章比较重要的意义之一。『失败什么的才不可怕，可怕的是什么都无法留下啊。』 算法竞赛可以重拾，OI 却仅有中学时代一次。不知我是否真正做到珍惜属于自己的 OI 了呢？ 前传：擦肩而过 小学四五年级的时候，我对信息技术似乎有着略微超过同龄人的涉猎，例如能够熟练与高速下载器搏斗或使用任务管理器关掉极域之类。后来因为一些机缘巧合了解到了计算机编程，遂报名了某机构的 python 课程，在初中的时候也拿了几个类似所谓“信息素养大赛”的水奖，难度大概在于掌握基本输入输出语句和小学数学知识的那种。 机构老师比较年轻，不知他是否有算法竞赛经历，竟在一次课上让我注 ...

To Misaka16172：\text{To Misaka16172：}To Misaka16172： 如果你飘了： 至少就目前阶段来说，你的水平离你的目标还有非常大的差距。 不要妄想能用短时间的努力追上他人长时间的积累，只有脚踏实地、坚持训练才是正道。 在打上那个分段之前，永远不要觉得自己有某个分段的实力，“场数不够” “之前没发挥好掉分了” 都不能作为借口。 做题数量甚至 rating 都并不与赛场表现成正比。 多找找你和周围其他人的差距。 如果你颓了： 世界上没有好打的逆风局，阶段性的挫折几乎是必然的。 无论上限如何，先相信自己的下限。 向前看，不要老是羡慕年龄比自己小的选手。 其他选手的水平都是动态的，在“找找与周围人的差距”之前不妨先与自己对比。 一场比赛并不能给你下定义，即使是正式比赛也是如此。 最后，在 whk 上多花点时间，有时间的话可以给自己找点别的事干。同时，注意身体状况和心理状况也是极为必要的。

前言 感觉比 NOIP 前心情平和很多了，因为不管结局怎么样，境遇都不会太差对吧，也没什么可遗憾的了。 Day -1 在学校颓了一天，也没写啥题或者打啥板子，倒是玩了挺多坦克世界闪击战，不得不说确实好玩！ 中午提议要不要像 NOIP 前集体点个外卖，但好像没啥人想点，就去食堂吃了。 下午倒是写了个 yjh 给的题，挺简单的，非常适合省选前放松一下压力找找手感，结果不到半个小时打完过了样例，一交获得 0 分，虚空调试到放学，结果发现是离散化没排序。。。一看发现两个样例给的序列全是升序的，有点搞笑。 晚上坐车前往 ssf 旁边的酒店。第一次 CSP（CSP-J 2023）和最后一次省选（大概）都在 ssf，也算是有始有终了。 睡前在学校表白墙发现自己名字是啥鬼？？ Day 0 考试日。 早上心情挺平静的。 开场 0.5h 给 t2 秒了，冲着过题去的，写了 2h 发现假的。此时还有 2.5h。上个厕所调整一下心态，疑似天崩开局。 回来成功签上了 t1，没发现中间有数不能取所以还调了一会。 还剩 1.5h 的时候会了 t2 52（性质 A）。于是开始豪赌。12:30 写完，拍出了几个错，调 ...

高二 NOIP 后写了个这种东西，学了一个月文化课，考得还可以，所以再写一个。但是不是考得还行其实是因为渴望去省选来着。 感觉自己 OI 失败很大一部分程度是由于一直没有目标，每个阶段也没有进行过总结，不知道自己是个什么水平，也没想过自己想要达到什么水平，看起来很卷写了很多题，实际上只是在逃避而已。 2025.9 什么也没干。开学考 100+110+125.5+52+61+82=530.5。 2025.10 目标是 110+125+135+76+70+91=607。 语文 别错非连了。古诗少错几个，闲暇时间训几个题。 默写尽量背。背一点是一点。 安排好时间。作文争取 >35。 数学 别错弱智选填了。控制在 10pts 以内。 填空最后一个题千万别选错。 大题不会就不会，别算错东西。新定义第二问要做出来。 英语 严肃加训语法。 你是洋文大蛇，阅读完型应该阿克才对。 听口也应该阿克。 物理 按照自己的节奏走，一轮没学到的东西就先别看了。 keep moving。 化学 学一学元素性质，学一学实验，学一学有机。 keep moving。 政 ...

思路 朴素的想法是对于任意能到达 vvv 的 uuu，连无向边 (u,v)(u,v)(u,v) 然后求图的最大独立集，然而这是困难的。 前置知识：在偏序集中，一个链是指集合中的元素可以相互比较大小的子集，而一个反链则是指集合中任意元素之间都不可比较大小的子集。在这里如果把有向边视作偏序关系，那么根据定义，求最大不可达节点集就是在求最长反链的长度。 Dilworth 定理告诉我们，最长反链等于最小链划分中链的个数，这也是在图上选出若干条路径后，满足所有路径 PPP 作为集合的并为 V={1,2,3,⋯ ,n}V=\{1,2,3,\cdots,n\}V={1,2,3,⋯,n} 的最小路径条数。对于前后两句话这里都不作证明。 最小链划分怎么求？ 对于每一个点，其在最小链划分的入度和出度都不大于 111。把每个点拆成入点和出点。对于原图上每一对可达的 (u,v)(u,v)(u,v)，连无向边 (uout,vin)(u_{\textbf{out}},v_{\textbf{in}})(uout​,vin​)。 对新图跑二分图最大匹配。开始时，整个图被划分成 nnn 条链，每个链是一个孤点。往 ...

前言 是啊，我觉得我打 oi 的时候会做这个题， 思路 正难则反，从最后全 000 的状态往前做。 考虑每个时刻 aia_iai​ 最大是多少（上界）。对于一个能在 ttt 次操作后被清零的数组 aia_iai​，任意一个满足 bi≤aib_i\leq a_ibi​≤ai​ 的数组 bbb 也可以在 ttt 次操作后被清零。 在第 ttt 个时刻，对于这一次被选中的下标 iii，aia_iai​ 的上界可以是 2ai+12a_i\color{red}+12ai​+1，而对于没有选中的下标 jjj，其上界则会变为 2aj2a_j2aj​。 如果答案为 TTT，那么在第 ttt 个时刻选中 aia_iai​，相当于给最终 aia_iai​ 的上界加上了 2T−t2^{T-t}2T−t。 固定答案 TTT 后，问题的形式变成：你现在有 S=20,21,22,⋯ ,2T−1S=2^0,2^1,2^2,\cdots,2^{T-1}S=20,21,22,⋯,2T−1，每次你可以选定一个下标 iii，将其中的一个数字 x∈Sx\in Sx∈S 分配给 aia_iai​，让 ai←ai+xa_i\l ...

思路 经典地，对于排列 ppp，连边 i→pii\rightarrow p_ii→pi​ 形成若干个置换环。 称 i→aii\rightarrow a_ii→ai​ 为红边，i→bii\rightarrow b_ii→bi​ 为蓝边；设 aaa 的逆排列为 iaiaia（满足 iaai=iia_{a_i}=iiaai​​=i，即 iaiia_iiai​ 为 iii 在红色置换环上的前驱）。 如果某个红色置换环中存在 bbb 不为 −1-1−1 的元素 iii，整个置换环的 bbb 值会同时被确定（或发现无解）：因为存在红边 iai→iia_{i}\rightarrow iiai​→i 和蓝边 i→bii\rightarrow b_ii→bi​，按照题目限制，应当存在一条新的蓝边 iai→iabiia_i \rightarrow ia_{b_i}iai​→iabi​​，循环下去就能确定整个置换环的 bbb 值。 手玩之后会发现这实质上是两个大小相同的红色置换环的对应关系： 如果一个红色置换环中连出了两条到不同红色置换环的蓝边，或是连到了与自己大小不相等的红色置换环，就直接输出无解。 ...

5.25 Codeforces Round 1057 (Div. 2) CF2153D CF2153E CF2153F 5.26 Codeforces Round 1052 (Div. 2) CF2146D2 CF2146E CF2146F 5.27 Codeforces Round 1053 (Div. 1) CF2150D CF2150E1 CF2150E2 CF2150F CF2150G Codeforces Round 1051 (Div. 2) CF2143D2 CF2143E CF2143F 5.28 Codeforces Round 1045 (Div. 2) CF2134F 5.29 Codeforces Round 1039 (Div. 2) CF2128E1 CF2128E2 CF2128F 5.30 Codeforces Round 1101 (Div. 2) CF2232D CF2232E CF2232F

前言 很小清新的一道题。 思路 考虑什么样的数对会产生贡献。不妨设 x<yx<yx<y，那么 f(x,y)=x+ymod  xf(x,y)=x+y\mod xf(x,y)=x+ymodx。一个很重要的观察是：f(x,y)∈[x,2x)f(x,y)\in [x,2x)f(x,y)∈[x,2x)。因此对于长为 nnn 的有序序列 aaa，考虑答案下界：取 x,yx,yx,y 分别为次大值和最大值，即 x=an−1,y=anx=a_{n-1},y=a_nx=an−1​,y=an​ 时，答案一定 ≥an−1\geq a_{n-1}≥an−1​。 分类讨论各种情况的贡献： 对于 x≤an−12x\leq \frac{a_{n-1}}{2}x≤2an−1​​，其贡献上界小于这个下界，是没有意义的。 当 x>an−12x>\frac{a_{n-1}}{2}x>2an−1​​ 时，若 y≤an−1y\leq a_{n-1}y≤an−1​，此时因为 x>y2x>\frac{y}{2}x>2y​，取模操作变成了减法！即 f(x,y)=x+(y−x) ...

前言 最近状态好差好差好差好差。。。。。。好难受 思路 最小化交换次数这种东西嘛，一个常见的结论是维持中位数的位置不变，然后把两边的东西都聚拢到中位数的位置，证明可以用调整法。具体到这个题里，假设我们知道了最后要选哪些数，就可以直接算出答案为 ∑i=1k∣pi−px∣−∣x−i∣\sum\limits_{i=1}^k |p_i-p_x|-|x-i|i=1∑k​∣pi​−px​∣−∣x−i∣，其中 xxx 是中位数的排名（即 k2\frac{k}{2}2k​，容易证明向上取整和向下取整无所谓，不影响正确性），pip_ipi​ 代表第 iii 个选择的数的下标。 既然这个答案形式跟中位数强相关，我们直接枚举中位数在哪个下标 xxx 然后对所有答案取 min⁡\minmin。那么现在的目标是要在 xxx 左边选一半，右边选一半，凑出 1∼k1\sim k1∼k 内的所有数。 首先，上面贡献式子右边不带 ppp 的那一项是独立的，只需要关心左边。容易发现对于每个值 ccc，如果其在最后的答案中在 xxx 左边，那么此时 pcp_cpc​ 必定为满足 ai=c,i<xa_i=c,i< ...