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

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

https://constructor2026.contest.codeforces.com/group/XdjJUfzFUt/contest/668785 A ~ D 模拟即可。 E 切第 iii 刀时，会多出 ⌊i2⌋+1\lfloor\frac{i}{2}\rfloor+1⌊2i​⌋+1 块巧克力。答案即为 ∑i=0k⌊i2⌋+1=(⌊k2⌋+1)2+(⌊k2⌋+1)[kmod  2]\sum\limits_{i=0}^k \lfloor\frac{i}{2}\rfloor+1=(\lfloor\frac{k}{2}\rfloor+1)^2+(\lfloor\frac{k}{2}\rfloor+1)[k\mod 2]i=0∑k​⌊2i​⌋+1=(⌊2k​⌋+1)2+(⌊2k​⌋+1)[kmod2]。 F dp。设 fi,jf_{i,j}fi,j​ 为确定到十进制第 iii 位（从 000 开始），mod  2n\mod 2^nmod2n 目前为 jjj 时第 iii 位的取值。可以从 fi,(j−2×10i)mod  2nf_{i,(j-2\times 10^{i})\mod ...

A 贪心。每删除 k−1k-1k−1 个栅栏必须留下一个。答案为 ⌊nk⌋(k−1)+nmod  k\lfloor \frac{n}{k}\rfloor(k-1)+n\mod k⌊kn​⌋(k−1)+nmodk。 B 假设我们已经确定了最后把钱放在哪个银行，对于其余的银行 iii，除了 aimod  xa_i \mod xai​modx 余下的钱都是可以被转移到最后那个银行去的。枚举即可。 为什么 aimod  xa_i \mod xai​modx 的余数不能被转移？假设我们为了转移这个余数 kkk，将另外 c0c_0c0​ 笔钱移过来，凑好了一些钱，转移了 c1c_1c1​ 次到最后的目标银行里。那么这个过程中凑到这个银行里的钱数就是 c0⋅y+kc_0\cdot y+kc0​⋅y+k，转出的钱数是 c1⋅xc_1\cdot xc1​⋅x，最后对答案的贡献是 c1⋅yc_1\cdot yc1​⋅y。如果 c1<c0c_1<c_0c1​<c0​，那这个过程是劣的，不如直接把钱转到最后的银行里。而 c0≤c1,y≤x,k<xc_0\leq c_1,y\leq x ...

前言 这个乌克兰 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− ...