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

前言 这个乌克兰 OI 的题感觉都挺套路的。 思路 固定区间一端，随着区间另一端的扩展，gcd⁡\gcdgcd 每次变化至少减半，最多变化 log⁡V\log VlogV 次。因为求的是 [l,r][l,r][l,r] 内所有子区间的答案，考虑扫描线，钦定 lll 维护 rrr。具体地，倒序枚举到 lll 时每次用 st 表倍增跳到以 lll 为左端点的区间 gcd⁡\gcdgcd 变化的交界处 xxx，然后对于 r>xr>xr>x，ansr←max⁡(ansr,w∑i=lxai)ans_r\leftarrow \max(ans_r,w\sum\limits_{i=l}^xa_i)ansr​←max(ansr​,wi=l∑x​ai​)，其中 w=gcd⁡i=lxaiw=\gcd\limits_{i=l}^xa_iw=i=lgcdx​ai​，ansrans_ransr​ 是区间 [l,r][l,r][l,r] 的答案。需要支持后缀取 max⁡\maxmax 单点查询，树状数组即可。但是这样做会漏掉 rrr 所在段的 gcd⁡\gcdgcd 的贡献，因为这个时候我们虽然 ...

考虑 vvv 是 prufer 点的充要条件：vvv 和 nnn 直接相连；vvv 是 n−1n-1n−1 的祖先，因为不是 n−1n-1n−1 祖先的点总先于 n−1n-1n−1 被删除。然后分讨： n−1n-1n−1 和 nnn 连通：只有同时是 nnn 的儿子和是 n−1n-1n−1 的祖先的那个点的答案不是 000，此时所有 nk−2∏i=1ksin^{k-2}\prod\limits^k_{i=1}s_ink−2i=1∏k​si​ 种方案都合法。 否则对每个点 vvv 考虑。下面默认 vvv 和 nnn 已经有边（没有边的话直接连上再处理即可），这时限制只剩 n−1n-1n−1 所在的树要接到 vvv 的子树里。答案是总方案数乘 vvv 子树的大小 svs_vsv​ 除 nnn 所在的这棵树总共的大小 SSS，即 svSnk−2∏i=1ksi\frac{s_v}{S}n^{k-2}\prod\limits^k_{i=1}s_iSsv​​nk−2i=1∏k​si​。这是关键的一步，因为所有方案是对称的，任意抽取一个方案，把 n−1n-1n−1 所在的子树接到 vvv 那一侧 ...

Preface 这是一篇英文题解。This is an English solution. Solution Consider the necessary and sufficient condition for P(T)=vP(T)=vP(T)=v: Edge (v,n)(v,n)(v,n) exists in TTT; Let nnn be the root of TTT. Then, n−1n-1n−1 is in the subtree of vvv. This is because every vertex u(u<n−1,u is not an ancestor of n−1)u(u< n-1,u\ \text{is not an ancestor of}\ n-1)u(u<n−1,u is not an ancestor of n−1) is removed before n−1n-1n−1. If n−1n-1n−1 and nnn are in the same tree, when vvv is both an ancestor of n− ...

Preface 这是一篇英文题解。This is an English solution. Solution Build an undirected graph with the given mmm constraints, connecting vertices xxx and yyy with an edge weighted zzz. After that, consider every connected component independently. Case 1: The connected component has at least ∣V∣|V|∣V∣ edges, i.e. it’s not a tree. In this case, there is a fixed solution if and only if there is an odd cycle in the graph. Conversely, every even cycle has a redundant edge. For example: {a+b=k1b+c=k2c+d=k3a+d=k4\ ...

前言 简单的做法，不需要动脑子。 思路 O(nq)\mathcal{O}(nq)O(nq) 的暴力算法是从左往右顺序枚举，如果有塔顶与当前积木异色的塔就放上去，否则单开一座。设当前有 aaa 座塔顶颜色为红色，bbb 座为蓝色，当前遇到的是红色的积木，那么这个过程等价于 a←a+1,b←max⁡(b−1,0)a\leftarrow a+1,b\leftarrow \max(b-1,0)a←a+1,b←max(b−1,0)。这可以表示成一个 (max⁡,+)(\max,+)(max,+) 矩乘的形式（相当于给 [ab0]\begin{bmatrix} a\\ b\\ 0 \end{bmatrix}⎣⎢⎡​ab0​⎦⎥⎤​ 左乘一个东西），线段树或猫树维护静态区间矩乘即可优化至 O(ω⋅nlog⁡n)\mathcal{O}(\omega\cdot n\log n)O(ω⋅nlogn)。

14(2) 下部分的体积为 VB−AEFD,VB−CDFGV_{B-AEFD},V_{B-CDFG}VB−AEFD​,VB−CDFG​ 两个四棱锥的体积之和，直接算出来，上面的体积是总体积减去下面的体积。 15(4) 设数列极限为 LLL，an+1=an+an−1  ⟺  an+1an=1+an−1an  ⟹  L=1+1La_{n+1}=a_n+a_{n-1}\iff \frac{a_{n+1}}{a_n}=1+\frac{a_{n-1}}{a_n}\implies L=1+\frac{1}{L}an+1​=an​+an−1​⟺an​an+1​​=1+an​an−1​​⟹L=1+L1​，由于 L>0L>0L>0，解得 L=1+52L=\frac{1+\sqrt 5}{2}L=21+5​​。 17 看错字母，只剩 3 分。 (1) 作 CPCPCP 中点 FFF，连接 EF,DFEF,DFEF,DF。 ∵E,F\because E,F∵E,F 为 BP,CPBP,CPBP,CP 中点 ∴EF∥BC,EF=12BC\therefore EF \parallel ...