Misaka16172's Blog

我是一个喜欢幻想、沉浸于梦中的人。 还在打 OI 的时候，我有时候会幻想自己成为一个胜利者。今天被无尽蓝这首歌激起了尘封许久的回忆：省选之前没有动力的时候，我经常会幻想，要是以那样万分之一的可能性翻盘进入省队，一定要在开着空调的卧室里循环这首《无尽蓝》。 而我终将抵达你梦境的所在 一如盛夏落下最后绚烂的剖白 与你恣意徜徉这天与海 目光所及无尽蓝 在这里我并不想再去重复那些老生常谈的“不要止步于幻想，要付诸行动”之类。实际上适当地做梦并不会有害，甚至能够起到一些激励作用。但是我同样相信一个人的潜意识对他所能达到的境界存在重要的影响：问题不在于自我有限，而在于自我设限。或许曾经的我潜意识里就在一遍又一遍的为自己画地为牢，最终将他人的唾弃转变成了现实。 最近在小红书上闲逛，无意中发现了很多人提及了“显化”这个词。查找了一番，虽说所谓“显化”无疑是唯心主义的呓语，但一个积极大胆的心理暗示的确存在不可忽视的反作用。现在的自己若是弱小到无法做出实质性贡献，那不妨先敢想敢梦、营造良好的心态，将以后的事业留给以后的自己。

离开了我喜欢的环境、事业和人之后，我再次陷入沉沦。 我的行为一步一步地试探着红线，逐渐地放纵着内心另一面那个不思进取、道德败坏、苟且偷安、狂妄自大的自己，有时我能意识到这件事，但却无法加以阻止，沉浸于他编织的廉价娱乐中无法自拔。 我是矛盾的，一面道貌岸然地痛斥着自己辜负自己又辜负他人的行径，一面又对自身抱有十二分的信心和高评价，以此麻痹自己、继续沉沦。尝试压制那些阴暗的想法，然而它们不受控制、源源不断地冒出来，就像蠹虫那样繁殖、感染，侵蚀着我。 有时候我会想，若是以前的自己或是【】了解了我的现状，该会抱有一份怎样的感情？是憎恶、惋惜还是嘲笑？我并不知道答案，因为过去的记忆随风消逝，过去的自己和他人究竟是什么样的人也无从想起。 与其他陷入沉沦的人不同，我对自己说“从此以后不能再这样下去了”这种话的频率并不高，而是在潜意识里将自己的沉沦标记为可接受的，心安理得地逃避。我不清楚哪种情况更为严重，也不知晓自己应去哪里、向谁、渴求什么样的解药。我深刻地明白自己应走上什么样的道路，以及将会因为自己的沉沦被导向什么样的道路，但却无法阻止，这种无力感与拿着马桶撅子面对电车难题的主角并无二致。

期中考试以后了解了不少升学相关的信息，有国内的学校，自然也包括国际路径。于是就报考了这个 SCIE，据说是国内 alevel 最牛的国际学校。 SCIE 招生考试有两轮，一轮笔试一轮面试，笔试线下，面试线上。如果考上了可能就真去读了。 Day -1 下午抵达深圳。 明天上午考试，筹划了一下明天下午去哪里玩，咨询了一下退群的群友。 有几位南科的群友非常热情啊，回了一大车，和其中一位加了好友聊了半天，聊的很开心。可惜中间朋友的爸爸说可以给我们预约参观腾讯大楼，已经约上了，不然真可以去南科转两圈顺便找群友面积来着。 晚上打车去学校旁边转了两圈，好像规模并没有想象中那么巨大，但是绿化非常不错，很有生态气息。 Day 0 考试日。 一共两科，英语俩小时多一点，数学一个小时多一点。八点开考英语。 考场里的妹子咋都这么好看！！ 先是听力，这个听力应该是最不诗人的一部分，前面一堆奶龙题目材料都放了两遍，结果最后两个有四小问的题就放了一遍，语速还跟 rapper 一样快，我半个字都没听见就结束了/jk/jk，要保龄了。 写作稍微好一点，唯一问题是要写的东西巨多，时间非常紧，最后一篇 180 词的作文潦 ...

https://music.163.com/song?id=2163968035 这一周零零散散的用摸鱼以外的时间思考了一点人生。 我从高一开始就不喜欢化学，但大学想读 cs 相关专业，所以才不得不选化学的。如果没有这条限制，化学肯定是不会考虑了，再排除掉同样不擅长的生物和玄学现象严重的地理，八成当时的选择会是物史政吧。 假期里看到期中考试成绩，政治意外地赋了 97，语文英语也还算过得去，于是我就思考自己是不是更适合选文科，发了个朋友圈感叹一下。过了一天竟然有同学发来私信，她选了历史，想给我一点帮助，提出周二带着我去找高一教我们的历史老师聊一聊。如果不是这番话，可能我也就只是停留在嘴上了，没有意识到自己其实是有选择的机会的。 说回来，高一的时候我就觉得这位老师很有趣，讲课讲的也很有水平。可惜当时一心打 OI，并且睡眠不足，不光没有好好听课，还经常在他课上睡觉。他的意见是现在修改还来得及，一轮复习刚刚开始，如果我真的喜欢历史的话并不晚。 其实我的顾虑无非两点，第一个是能不能学好（这点和老师的谈话已经回答过了），第二个是报不了 cs 专业该咋办。其实后者也并非什么大问题，考一个转专业政策 ...

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

前言 这题真难吧，机房一车人没一个会做？？ 思路 首先你如果不对这个题进行什么深入挖掘，八成是想不出任何多项式做法的啊，然后注意到这个数据范围，在不存在可行的贪心策略的情况下，基本就是让你去设计一个 O(n2)\mathcal{O(n^2)}O(n2) 的 dp 没跑了。 但他这个关灯的轨迹看起来非常的神秘，无规律可循，怎么才能把它转化成一个便于 dp 的形式呢？ 发现一个事情：我们的起点是最左边，如果从一开始没有一路关到底的话，中间没有被关的灯迟早还是需要再折返回来关一次。 然后看到题目里给的限制是必须在 ≥t\geq t≥t 的时刻关掉区间里的灯，因此拖到折返的时候再关被空出来的地方后面的灯就是更划算的。那么你现在已经关掉了前缀的一段灯，如果从某个位置开始停止关闭前缀的灯，还需要向右走吗？那必然是需要的，否则直接从头关到尾不就好了吗（感觉像废话文学 T T）。那么此时向右走的目标就很明确了，即走到最右边去关闭后缀的一串灯，后面的过程与刚开始的时候类似。 由此我们便描绘出了本题的重要结论：任意时刻场上未被关闭的灯一定构成一段连续区间。到这里设计 dp 就变得不那么无从下手了。 设 ...

前言 来点不带脑子的做法，但有点卡常，在 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​，其 ...

前言 忙里偷闲做 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)，一共 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 ...