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

前言 很小清新的一道题。 思路 考虑什么样的数对会产生贡献。不妨设 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< ...

带阻力的运动学方程推导 问题：假如某个物体从高空由静止释放，受到重力 mgmgmg 和空气阻力。 前提条件：低速状态下，空气阻力一般与速度成正比，即 f=kvf=kvf=kv。 规定竖直向下为正方向，试分析物体在任意时刻的速度。 进行受力分析，有 mg−kv=mamg-kv=mamg−kv=ma，即： mg−kv=mdvdtmg-kv=m\frac{dv}{dt} mg−kv=mdtdv​ 分离参数 v,tv,tv,t： dvmg−kv=dtm\frac{dv}{mg-kv}=\frac{dt}{m} mg−kvdv​=mdt​ 对两边积分： ∫1mg−kv dv=∫1m dt\int \frac{1}{mg-kv}\ dv=\int \frac{1}{m}\ dt ∫mg−kv1​ dv=∫m1​ dt 转成定积分形式，左边从 000 积到任意时刻的速度 vvv，右边从 000 积到该时刻 ttt： ∫0v1mg−kv dv=∫0t1m dt\int^v_0 \frac{1}{mg-kv}\ dv=\int^t_0 \frac{1}{m}\ dt ∫0v​mg−kv1​ dv ...

前言 好想哭啊 思路 定义 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)>p_u ...

前言 最近突然想起来了，写给自己看的。 更可爱的阅读体验 思路 性质 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}+[ ...