立体防御
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 写完,拍出了几个错,调 ...
溪流
一条溪流出现在我眼前。
溪水清澈,波光粼粼。水底的鹅卵石在阳光的照射下格外璀璨夺目。抬头望去,水源似乎是远处的云雾缭绕之地。那里树木葱郁,开着几丛无名花。
感性使我扑向水面,调整泳姿,溯源而上。理性告诉我现在是冬季,是否会冻毙于其中尚不可知。我并未理会,放空头脑,享受着水流拂过身体时的阵阵凉意。
我愈发向上游动,河床与我的距离愈远,到了脚底无法触及的程度。询问周围的鱼群,他们说这才是开始。我轻轻划动双臂,流畅地伴随着。
时光流转,原先溪中的几片落叶和花瓣此刻已消失于无形,溪水的颜色由蓝绿色渐变至近乎透明的蓝。我逐渐意识到那并非危言耸听,水中实在是有些冰冷刺骨。鱼群没有发现我的异状,只是一味地迁徙。
鱼群带着我游至一处瀑布。我暂时停下,像是意识到什么似的。可到了现在,已容不得再去耽搁。我一跃而下。与预期不同,不是溪水,而是石板的触感。
伤情不大不小,所幸还没到能够阻止我前进的程度。环顾四周,身旁有几位搁浅的同伴,我向他们致意,不舍地离去。
水帘后是一处湖泊。这里的湖水比起水,却更像玻璃。鱼群的速度加快了,跟上他们逐渐变得吃力起来。负伤的那部分身体似乎也变得透明了,这实在不是什么好征兆。 ...
点分治
前言
做题遇到这个不会,来学一下,应该还不算晚。
和序列分治挺像的,只是搬到树上而已。
用途
常用于树上路径统计问题。
算法过程
如果学过序列分治可以更容易地理解树上点分治。与序列分治干的事情差不多:在序列分治中,我们把要统计的区间按当前分治区间 [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)。然而这样做只能计算 ...
P3590 [POI2015] TRZ 神秘做法
前言
神秘新颖好玩的题,有个不知道是啥的做法,感觉讲不太明白。。
思路
第一步转化应该比较简单,先前缀和,然后 [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_ ...
情绪垃圾 #1
嗯哦唉批告一段落,随之而来的是从零开始的文化课生活。
刚考完的时候真的好难受好难受啊,前两天出分数线的时候又好难受啊,努力了这么久换来的只是这种水平吗?
高二整整一届除了我以外都被送退役了。傻逼 ccf,用一道题(edit)或者一纸公告就能让选手的努力付诸东流。很幸运这俩都没影响到我(不幸中的万幸吧。差点连个 1= 都没了。本来以为 1= 是下限中的下限来着。)
为啥老是尝试去骗自己。如果你想起来了 t4 2log 是你做过的会怎么样,如果你仔细看了 t3 的部分分、稍稍思考一下高档一点的部分分会怎么样。
但事实就摆在那里。无论怎么欺骗自己,你其实是有水平的,就是没发挥好之类的。全都是借口啊。把 whk 扔掉彻底疯狂训了一年,只有一个擦线 1= 的实力。
这个 whk 也是彻底司马了。目前没见过任何一个选手能让 whk 成为 oi 生涯里最大的绊脚石的。我真是奇异搞笑。家长也是奇异搞笑,闹这么大对我有任何好处没有???还觉得自己很牛逼很有爱心很为我着想???蓝的盆。
还有两周期末考,我能苟出一个好分的成绩的概率有多大?之前我信誓旦旦地觉得能够轻取三倍队线,付出了全部努力、且有足够精神 ...
NOIP 2024 (不出意外的话是)退役记
いつもひとりで歩(ある)いてた
一路走来形单影只
行(い)く先(さき)には崖(がけ)が待(ま)ってた
路途前方险峻波折
それでもあたしは歩(ある)いた
即使如此我依然前行
強(つよ)さの証明(しょうめい)のため
只为证明这份坚强
省流: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
结果脑子特别不清楚,看一题不会一题,一下午就做了三道。。
放学之后赶往酒店,经典环节之在旁边的 ...