立体防御
To Misaka16172:\text{To Misaka16172:}To Misaka16172:
如果你飘了:
至少就目前阶段来说,你的水平离你的目标还有非常大的差距。
不要妄想能用短时间的努力追上他人长时间的积累,只有脚踏实地、坚持训练才是正道。
在打上那个分段之前,永远不要觉得自己有某个分段的实力,“场数不够” “之前没发挥好掉分了” 都不能作为借口。
做题数量甚至 rating 都并不与赛场表现成正比。
多找找你和周围其他人的差距。
如果你颓了:
世界上没有好打的逆风局,阶段性的挫折几乎是必然的。
无论上限如何,先相信自己的下限。
向前看,不要老是羡慕年龄比自己小的选手。
其他选手的水平都是动态的,在“找找与周围人的差距”之前不妨先与自己对比。
一场比赛并不能给你下定义,即使是正式比赛也是如此。
最后,在 whk 上多花点时间,有时间的话可以给自己找点别的事干。同时,注意身体状况和心理状况也是极为必要的。
省选联考 2025 退役记
前言
感觉比 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 写完,拍出了几个错,调 ...
溪流
一条溪流出现在我眼前。
溪水清澈,波光粼粼。水底的鹅卵石在阳光的照射下格外璀璨夺目。抬头望去,水源似乎是远处的云雾缭绕之地。那里树木葱郁,开着几丛无名花。
感性使我扑向水面,调整泳姿,溯源而上。理性告诉我现在是冬季,是否会冻毙于其中尚不可知。我并未理会,放空头脑,享受着水流拂过身体时的阵阵凉意。
我愈发向上游动,河床与我的距离愈远,到了脚底无法触及的程度。询问周围的鱼群,他们说这才是开始。我轻轻划动双臂,流畅地伴随着。
时光流转,原先溪中的几片落叶和花瓣此刻已消失于无形,溪水的颜色由蓝绿色渐变至近乎透明的蓝。我逐渐意识到那并非危言耸听,水中实在是有些冰冷刺骨。鱼群没有发现我的异状,只是一味地迁徙。
鱼群带着我游至一处瀑布。我暂时停下,像是意识到什么似的。可到了现在,已容不得再去耽搁。我一跃而下。与预期不同,不是溪水,而是石板的触感。
伤情不大不小,所幸还没到能够阻止我前进的程度。环顾四周,身旁有几位搁浅的同伴,我向他们致意,不舍地离去。
水帘后是一处湖泊。这里的湖水比起水,却更像玻璃。鱼群的速度加快了,跟上他们逐渐变得吃力起来。负伤的那部分身体似乎也变得透明了,这实在不是什么好征兆。 ...
P11432 [COCI 2024/2025 #2] 流明 / Blistavost 题解
前言
这题真难吧,机房一车人没一个会做??
思路
首先你如果不对这个题进行什么深入挖掘,八成是想不出任何多项式做法的啊,然后注意到这个数据范围,在不存在可行的贪心策略的情况下,基本就是让你去设计一个 O(n2)\mathcal{O(n^2)}O(n2) 的 dp 没跑了。
但他这个关灯的轨迹看起来非常的神秘,无规律可循,怎么才能把它转化成一个便于 dp 的形式呢?
发现一个事情:我们的起点是最左边,如果从一开始没有一路关到底的话,中间没有被关的灯迟早还是需要再折返回来关一次。
然后看到题目里给的限制是必须在 ≥t\geq t≥t 的时刻关掉区间里的灯,因此拖到折返的时候再关被空出来的地方后面的灯就是更划算的。那么你现在已经关掉了前缀的一段灯,如果从某个位置开始停止关闭前缀的灯,还需要向右走吗?那必然是需要的,否则直接从头关到尾不就好了吗(感觉像废话文学 T T)。那么此时向右走的目标就很明确了,即走到最右边去关闭后缀的一串灯,后面的过程与刚开始的时候类似。
由此我们便描绘出了本题的重要结论:任意时刻场上未被关闭的灯一定构成一段连续区间。到这里设计 dp 就变得不那么无从下手了。
设 ...
P11431 [COCI 2024/2025 #2] 差异 / Različitost 题解
前言
来点不带脑子的做法,但有点卡常,在 COCI 的土豆评测机上过不去。
思路
不妨设 n≤mn\leq mn≤m,且下文的所有下标均从 000 开始。
看见异或还要求和可以先拆位。
拆位后考虑对于每个 aia_iai 求出其贡献,设 fi,jf_{i,j}fi,j 为第 iii 个数在第 jjj 次出现时会与谁异或,则有 fi,j=(fi,j−1+n)mod mf_{i,j}=(f_{i,j-1}+n)\mod mfi,j=(fi,j−1+n)modm,初始状态为 fi,0=if_{i,0}=ifi,0=i。看到这种东西可以直接倍增,设 sumi,jsum_{i,j}sumi,j 代表 aia_iai 第 jjj 次出现时当前位已经累计遇到了多少个 111(那么 000 的个数就是 2j2^j2j 减去 111 的个数),则有 sumi,j=sumi,j−1+sumfi,j−1,j−1sum_{i,j}=sum_{i,j-1}+sum_{f_{i,j-1},j-1}sumi,j=sumi,j−1+sumfi,j−1,j−1。
于是对于 aia_iai,其 ...
P11695 [JRKSJ ExR] 昼寝 题解
前言
忙里偷闲做 ds!
思路
参考了 @Rainbow_qwq 的题解,orz。
题意简述:支持加 / 删区间和查询当前所有被 [l,r][l,r][l,r] 包含的区间的并是否等于 [l,r][l,r][l,r]。
数据范围不小,很难在线维护,考虑离线分治。
设当前分治区间为 [sl,sr][sl,sr][sl,sr],中点为 midmidmid,在这一层分治内部处理所有被 [sl,sr][sl,sr][sl,sr] 完全包含并跨过 midmidmid 的询问,其余询问递归处理。考虑两类区间对询问的贡献:跨过 midmidmid 或被 [l,mid][l,mid][l,mid] 和 (mid,r](mid,r](mid,r] 完全包含。
跨过 midmidmid 的操作区间
对于这类区间,当前的目标是对每个询问 [ql,qr][ql,qr][ql,qr] 找到所有被 [ql,qr][ql,qr][ql,qr] 包含的区间中,极左的能贡献的位置 tltltl 与极右的能贡献的位置 trtrtr。下面以求解 tltltl 为例,trtrtr 与 tltltl 本质相同:
首先对时间轴 ...
点分治
前言
做题遇到这个不会,来学一下,应该还不算晚。
和序列分治挺像的,只是搬到树上而已。
用途
常用于树上路径统计问题。
算法过程
如果学过序列分治可以更容易地理解树上点分治。与序列分治干的事情差不多:在序列分治中,我们把要统计的区间按当前分治区间 [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),一共 logn\log nlogn 层,总复杂度 O(nlogn)\mathcal{O}(n\log n)O(nlogn)。
然而在点分治中,我们要统计的东西从区间变成了路径,每次同样可以找到一个划分点 rtrtrt,则需要被统计的路径也可以分为经过 rtrtrt 的路径与不经过 rtrtrt 的路径,当前只需要以 rtrtrt 为根处理经过 rtrtrt 的路径,处理完之后将 rtrtrt ...
Kruskal 重构树
前言
做题,遇到这个东西不会,来学一下
构建过程
现在有一个 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 ...
P6258 [ICPC 2019 WF] Hobson's Trains 题解
前言
来个绝世唐诗做法,喜提题解区复杂度倒一。
思路
题意即对每个点求内向基环树森林里有多少个点走 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(nnlogn)\mathcal{O}(n\sqrt n\log n)O(nnlogn)。然而这样做只能计算 ...