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。 政 ...

前言 。 思路 前言 。 思路 定义 f2(u)f_2(u)f2​(u) 为：在从根到 uuu 的路径上的点的点权构成的集合中插入 f(u)f(u)f(u) 后，新集合的 mex⁡\operatorname{mex}mex 值。开局先预处理所有 f(u)f(u)f(u) 和 f2(u)f_2(u)f2​(u) 的值，在 dfs 时用 set 维护从根到 uuu 的集合的补集即可。 考虑对 uuu 进行操作后对其子树的影响。 首先特判 f(u)=pu+1f(u)=p_u+1f(u)=pu​+1 的情况，此时操作后树上没有 pup_upu​，整个 uuu 子树内的点的 fff 值都会变为 pup_upu​。 我们考虑将一次操作拆成两次：插入 f(u)f(u)f(u) 和删除 pup_upu​。 插入 f(u)f(u)f(u) 时，对于所有 uuu 子树中的点 vvv，若 f(v)=f(u)f(v)=f(u)f(v)=f(u) 则 f(v)f(v)f(v) 会变成 f2(v)f_2(v)f2​(v)，否则没有影响。 删除 pup_upu​ 时，对于所有 f(v)>puf(v)&g ...

前言 最近突然想起来了，写给自己看的。 更可爱的阅读体验 思路 性质 A，52 pts 其实跟正解关系不大，但我比赛的时候会的是这个。 只修改 aaa，不修改 bbb。首先将所有点按 bbb 重标号方便后续讨论。大力对 aaa 分块，设块长为 BBB。对每个块处理 fS=max⁡u∈S{au}f_S=\max\limits_{u\in S}\{a_u\}fS​=u∈Smax​{au​}，修改的时候直接对单块暴力重构，查询的时候整块用手写 bitset 查询点 uuu 在每块所属的区间内的可达性集合，散块暴力枚举，总复杂度 O(q2B+nqB+qB)\mathcal{O}(q2^B+\frac{nq}{B}+qB)O(q2B+Bnq​+qB)，取 B=12B=12B=12 时平衡。 100 pts 定期重构。设重构周期为 BBB。对于在上次重构后有修改的点，查询时暴力枚举判断是否满足条件。这部分复杂度 O(qB)\mathcal{O}(qB)O(qB)。依旧对 aaa 分块，每次重构预处理对每个点 uuu 和每个块 iii 预处理块中能被 uuu 到达的点的 bvb_vbv​ 最大值。 ...

前言 懒得喷。。。。。。 更可爱的阅读体验 思路 考虑树形 dp。在 dp 过程中枚举每个点的状态：没有进行交换，跟父亲交换或是跟某个儿子交换。将其记在状态里，用 fu,0f_{u,0}fu,0​ 代表不交换，fu,1f_{u,1}fu,1​ 代表跟父亲交换，fu,i+2f_{u,i+2}fu,i+2​ 代表跟第 iii 个儿子交换（下标从 000 开始）。有如下转移： {fu,0=∑v∈son(u)max⁡(fv,0+[au=av]wu,max⁡x≥2{fv,x+[au=ason(v)x]wu})fu,1=∑v∈son(u)max⁡(fv,0+[afau=av]wfau,max⁡x≥2{fv,x+[afau=ason(v)x]wfau})fu,i(i≥2)=fson(u)i,1+∑v∈son(u),v≠son(u)imax⁡(fv,0+[ason(u)i=av]wson(u)i,max⁡x≥2{fv,x+[ason(u)i=ason(v)x]wson(u)i})\begin{cases} f_{u,0}=\sum\limits_{v\in son(u)}\max(f_{v,0}+[ ...

前言 更可爱的阅读体验 思路 先拆一下题目里的条件。令被矩形包含的所有点的 hih_ihi​ 构成的可重集为 SSS，从小到大对 SSS 考虑，那么对任意三个相邻的 Si,Si+1,Si+2S_{i},S_{i+1},S_{i+2}Si​,Si+1​,Si+2​ 均满足 Si+Si+1≤Si+2S_{i}+S_{i+1}\leq S_{i+2}Si​+Si+1​≤Si+2​ 是答案为 000 的充要条件。发现 SSS 中的元素增长得很快，因为值域有限制，尝试构造出一个最大的答案为 000 的 SSS，满足 Si+2=Si+1+SiS_{i+2}=S_{i+1}+S_iSi+2​=Si+1​+Si​。其实这个时候 SSS 里的数就是斐波那契数列 FFF，由于 F45>109F_{45}>10^9F45​>109，我们得到了当 ∣S∣≥45|S|\geq 45∣S∣≥45 时答案必然为 111。 做一遍矩形数点排除掉 ∣S∣≥45|S|\geq 45∣S∣≥45 的询问后，我们直接将每个点插入将其包含的剩下的询问中。这个过程可以用扫描线 + 线段树实现，对线段树每个节点 ...

所有不过滤行末空格的评测系统，祝你们的妈妈在天堂相遇。 t1 没过，真神了，数据是不是有问题？ t3 前七分调了一个半小时（比赛时间 3h），最后发现是评测系统不过滤行末空格？？？？？？？？ 后八分最后十分钟写完没过，晚上回酒店发现死因是，输出方案数输出成了行数。，。？ t4 k=0k=0k=0。 t5 没交。 认识了考场里两位 icc 的同学。蹭了顿饭😋。除了比赛之外的部分都很开心！！ 能不能不要给我发奖？？？

前言 场内选手来了。。。这个题的官方 spj 是脑残，不过滤行末空格，以及比赛的时候我没读到最后一个 sub 每个猜测选的数必须不交。。。 思路 先看前 888 分，这个 gcd⁡\gcdgcd 的条件是诈骗的，考虑更弱的限制：奇偶性。 如果两个数都是偶数它们的 gcd⁡\gcdgcd 一定 ≥2\geq 2≥2，于是考虑凑两个偶数出来： 如果序列里有两个偶数 ci,cjc_i,c_jci​,cj​，令 A={i},B={j}A=\{i\},B=\{j\}A={i},B={j}。 否则，如果序列里有一个偶数 xxx 和 ≥2\geq 2≥2 个奇数，令前两个奇数的出现位置为 i,ji,ji,j，令 A={x},B={i,j}A=\{x\},B=\{i,j\}A={x},B={i,j}。 否则，如果序列里有 ≥4\geq 4≥4 个奇数，令它们的出现位置为 a,b,c,da,b,c,da,b,c,d，令 A={a,b},B={c,d}A=\{a,b\},B=\{c,d\}A={a,b},B={c,d}。 否则，一定有 n≤3n\leq 3n≤3。暴力枚举子集检查是否有解即可。 再看 ...