Misaka16172's Blog

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 写完，拍出了几个错，调 ...

一条溪流出现在我眼前。 溪水清澈，波光粼粼。水底的鹅卵石在阳光的照射下格外璀璨夺目。抬头望去，水源似乎是远处的云雾缭绕之地。那里树木葱郁，开着几丛无名花。 感性使我扑向水面，调整泳姿，溯源而上。理性告诉我现在是冬季，是否会冻毙于其中尚不可知。我并未理会，放空头脑，享受着水流拂过身体时的阵阵凉意。 我愈发向上游动，河床与我的距离愈远，到了脚底无法触及的程度。询问周围的鱼群，他们说这才是开始。我轻轻划动双臂，流畅地伴随着。 时光流转，原先溪中的几片落叶和花瓣此刻已消失于无形，溪水的颜色由蓝绿色渐变至近乎透明的蓝。我逐渐意识到那并非危言耸听，水中实在是有些冰冷刺骨。鱼群没有发现我的异状，只是一味地迁徙。 鱼群带着我游至一处瀑布。我暂时停下，像是意识到什么似的。可到了现在，已容不得再去耽搁。我一跃而下。与预期不同，不是溪水，而是石板的触感。 伤情不大不小，所幸还没到能够阻止我前进的程度。环顾四周，身旁有几位搁浅的同伴，我向他们致意，不舍地离去。 水帘后是一处湖泊。这里的湖水比起水，却更像玻璃。鱼群的速度加快了，跟上他们逐渐变得吃力起来。负伤的那部分身体似乎也变得透明了，这实在不是什么好征兆。 ...

前言 做题遇到这个不会，来学一下，应该还不算晚。 和序列分治挺像的，只是搬到树上而已。 用途 常用于树上路径统计问题。 算法过程 如果学过序列分治可以更容易地理解树上点分治。与序列分治干的事情差不多：在序列分治中，我们把要统计的区间按当前分治区间 [l,r][l,r][l,r] 分为三部分，被 [l,mid)[l,mid)[l,mid) 包含 / 被 (mid,r](mid,r](mid,r] 包含 / 跨过中点 midmidmid 的区间。前两类继续递归分治，只计算最后一种的贡献。由于每次区间长度减半，区间数量翻倍，故分治每层遍历的总复杂度均为 O(n)\mathcal{O}(n)O(n)，一共 log⁡n\log nlogn 层，总复杂度 O(nlog⁡n)\mathcal{O}(n\log n)O(nlogn)。 然而在点分治中，我们要统计的东西从区间变成了路径，每次同样可以找到一个划分点 rtrtrt，则需要被统计的路径也可以分为经过 rtrtrt 的路径与不经过 rtrtrt 的路径，当前只需要以 rtrtrt 为根处理经过 rtrtrt 的路径，处理完之后将 rtrtrt ...

前言 做题，遇到这个东西不会，来学一下 构建过程 现在有一个 nnn 个点的无向图，求出它的最大生成树（也可以是最小生成树，若是最小生成树，则将后文的所有大小关系反转，性质依然成立）后，可以用如下方式得到它的 Kruskal 重构树： 从大到小枚举树边； 维护一个并查集，设这条树边为 (u,v,w)(u,v,w)(u,v,w)，u,vu,vu,v 在并查集中的祖先分别为 u′,v′u',v'u′,v′，则新建一个点 xxx，连接 (u,x)(u,x)(u,x) 和 (v,x)(v,x)(v,x) 两条边，并使 xxx 的点权为 www，在并查集中将 u,vu,vu,v 的祖先设为 xxx。 性质 / 用途 性质 1：建出的重构树符合二叉小根堆的性质，即每个点的点权均小于等于其儿子的点权。 性质 2：点对 (u,v)(u,v)(u,v) 在原图中所有路径中，边权最小值最大的路径上的最小值 === 最大生成树上，(u,v)(u,v)(u,v) 两点路径上最小的边权 === Kruskal 重构树上 lca⁡(u,v)\operatorname{lca}(u ...

前言 来个绝世唐诗做法，喜提题解区复杂度倒一。 思路 题意即对每个点求内向基环树森林里有多少个点走 kkk 步以内能到达自己。 树上的点答案是好求的，对于环上的点，首先用 vector 记录其子树内每个深度的点各有多少个，然后考虑对其子树内最大深度进行根号分治（称最大深度 ≥n\geq \sqrt n≥n​ 的点为大点，≤n\leq \sqrt n≤n​ 的点为小点），来计算环上不同点之间的贡献： 大点个数不超过 n\sqrt nn​ 个，故大点与其他点之间的贡献可以直接暴力枚举计算，复杂度 O(nn)\mathcal{O}(n\sqrt n)O(nn​)； 之后只需要计算小点与小点之间的贡献，考虑断环成链，顺序枚举所有点，每枚举到一个点会使之前的点与当前点距离加上 i−lsti-lsti−lst（lstlstlst 为上次枚举到的点的下标），于是相当于维护一个支持全局下标加 xxx、查询下标在 kkk 之前的前缀和的数据结构，可以使用优先队列进行懒删除，复杂度 O(nnlog⁡n)\mathcal{O}(n\sqrt n\log n)O(nn​logn)。然而这样做只能计算 ...

前言 神秘新颖好玩的题，有个不知道是啥的做法，感觉讲不太明白。。 思路 第一步转化应该比较简单，先前缀和，然后 [l,r][l,r][l,r] 合法相当于 ∀x,y∈{B,C,S},prer,x−prel−1,x≠prer,y−prel−1,y\forall x,y\in \{B,C,S\},pre_{r,x}-pre_{l-1,x}≠pre_{r,y}-pre_{l-1,y}∀x,y∈{B,C,S},prer,x​−prel−1,x​​=prer,y​−prel−1,y​，即 prer,x−prer,y≠prel−1,x−prel−1,ypre_{r,x}-pre_{r,y}≠pre_{l-1,x}-pre_{l-1,y}prer,x​−prer,y​​=prel−1,x​−prel−1,y​，相当于得到三个数组 ai,0=prei,B−prei,C,ai,1=prei,B−prei,S,ai,2=prei,C−prei,Sa_{i,0}=pre_{i,B}-pre_{i,C},a_{i,1}=pre_{i,B}-pre_{i,S},a_{i,2}=pre_{i,C}-pre_ ...

嗯哦唉批告一段落，随之而来的是从零开始的文化课生活。 刚考完的时候真的好难受好难受啊，前两天出分数线的时候又好难受啊，努力了这么久换来的只是这种水平吗？ 高二整整一届除了我以外都被送退役了。傻逼 ccf，用一道题（edit）或者一纸公告就能让选手的努力付诸东流。很幸运这俩都没影响到我（不幸中的万幸吧。差点连个 1= 都没了。本来以为 1= 是下限中的下限来着。） 为啥老是尝试去骗自己。如果你想起来了 t4 2log 是你做过的会怎么样，如果你仔细看了 t3 的部分分、稍稍思考一下高档一点的部分分会怎么样。 但事实就摆在那里。无论怎么欺骗自己，你其实是有水平的，就是没发挥好之类的。全都是借口啊。把 whk 扔掉彻底疯狂训了一年，只有一个擦线 1= 的实力。 这个 whk 也是彻底司马了。目前没见过任何一个选手能让 whk 成为 oi 生涯里最大的绊脚石的。我真是奇异搞笑。家长也是奇异搞笑，闹这么大对我有任何好处没有？？？还觉得自己很牛逼很有爱心很为我着想？？？蓝的盆。 还有两周期末考，我能苟出一个好分的成绩的概率有多大？之前我信誓旦旦地觉得能够轻取三倍队线，付出了全部努力、且有足够精神 ...

いつもひとりで歩(ある)いてた 一路走来形单影只 行(い)く先(さき)には崖(がけ)が待(ま)ってた 路途前方险峻波折 それでもあたしは歩(ある)いた 即使如此我依然前行 強(つよ)さの証明(しょうめい)のため 只为证明这份坚强 省流：gg，100+100+[4,16]+[20,32]=[224,248]100+100+[4,16]+[20,32]=[224,248]100+100+[4,16]+[20,32]=[224,248]。 Day -2 吧唧到货了。 Day -1 最后一天，教练说不给我们布置模拟赛，想回家休息的甚至可以直接请假。 于是在机房打摆。 上午先和 hyf zzj cyx 随机打 gen，他们说玩 gen 可以在考场上化身 gen 王/tiao 然后跟 sch duel potpvp，太牛，拼尽全力无法战胜，换了十几个模式都是被薄纱/oh/oh 中午花了 120 七个人点了六个披萨，赤爽了！！ 下午发现我的 agc 还有一半没做，我草这咋办，赶紧滚回来做 agc 结果脑子特别不清楚，看一题不会一题，一下午就做了三道。。 放学之后赶往酒店，经典环节之在旁边的 ...