SCIE A1 招生考试游记
期中考试以后了解了不少升学相关的信息,有国内的学校,自然也包括国际路径。于是就报考了这个 SCIE,据说是国内 alevel 最牛的国际学校。
SCIE 招生考试有两轮,一轮笔试一轮面试,笔试线下,面试线上。如果考上了可能就真去读了。
Day -1
下午抵达深圳。
明天上午考试,筹划了一下明天下午去哪里玩,咨询了一下退群的群友。
有几位南科的群友非常热情啊,回了一大车,和其中一位加了好友聊了半天,聊的很开心。可惜中间朋友的爸爸说可以给我们预约参观腾讯大楼,已经约上了,不然真可以去南科转两圈顺便找群友面积来着。
晚上打车去学校旁边转了两圈,好像规模并没有想象中那么巨大,但是绿化非常不错,很有生态气息。
Day 0
考试日。
一共两科,英语俩小时多一点,数学一个小时多一点。八点开考英语。
考场里的妹子咋都这么好看!!
先是听力,这个听力应该是最不诗人的一部分,前面一堆奶龙题目材料都放了两遍,结果最后两个有四小问的题就放了一遍,语速还跟 rapper 一样快,我半个字都没听见就结束了/jk/jk,要保龄了。
写作稍微好一点,唯一问题是要写的东西巨多,时间非常紧,最后一篇 180 词的作文潦 ...
Future Notes
https://music.163.com/song?id=2163968035
这一周零零散散的用摸鱼以外的时间思考了一点人生。
我从高一开始就不喜欢化学,但大学想读 cs 相关专业,所以才不得不选化学的。如果没有这条限制,化学肯定是不会考虑了,再排除掉同样不擅长的生物和玄学现象严重的地理,八成当时的选择会是物史政吧。
假期里看到期中考试成绩,政治意外地赋了 97,语文英语也还算过得去,于是我就思考自己是不是更适合选文科,发了个朋友圈感叹一下。过了一天竟然有同学发来私信,她选了历史,想给我一点帮助,提出周二带着我去找高一教我们的历史老师聊一聊。如果不是这番话,可能我也就只是停留在嘴上了,没有意识到自己其实是有选择的机会的。
说回来,高一的时候我就觉得这位老师很有趣,讲课讲的也很有水平。可惜当时一心打 OI,并且睡眠不足,不光没有好好听课,还经常在他课上睡觉。他的意见是现在修改还来得及,一轮复习刚刚开始,如果我真的喜欢历史的话并不晚。
其实我的顾虑无非两点,第一个是能不能学好(这点和老师的谈话已经回答过了),第二个是报不了 cs 专业该咋办。其实后者也并非什么大问题,考一个转专业政策 ...
溪流
一条溪流出现在我眼前。
溪水清澈,波光粼粼。水底的鹅卵石在阳光的照射下格外璀璨夺目。抬头望去,水源似乎是远处的云雾缭绕之地。那里树木葱郁,开着几丛无名花。
感性使我扑向水面,调整泳姿,溯源而上。理性告诉我现在是冬季,是否会冻毙于其中尚不可知。我并未理会,放空头脑,享受着水流拂过身体时的阵阵凉意。
我愈发向上游动,河床与我的距离愈远,到了脚底无法触及的程度。询问周围的鱼群,他们说这才是开始。我轻轻划动双臂,流畅地伴随着。
时光流转,原先溪中的几片落叶和花瓣此刻已消失于无形,溪水的颜色由蓝绿色渐变至近乎透明的蓝。我逐渐意识到那并非危言耸听,水中实在是有些冰冷刺骨。鱼群没有发现我的异状,只是一味地迁徙。
鱼群带着我游至一处瀑布。我暂时停下,像是意识到什么似的。可到了现在,已容不得再去耽搁。我一跃而下。与预期不同,不是溪水,而是石板的触感。
伤情不大不小,所幸还没到能够阻止我前进的程度。环顾四周,身旁有几位搁浅的同伴,我向他们致意,不舍地离去。
水帘后是一处湖泊。这里的湖水比起水,却更像玻璃。鱼群的速度加快了,跟上他们逐渐变得吃力起来。负伤的那部分身体似乎也变得透明了,这实在不是什么好征兆。 ...
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)。然而这样做只能计算 ...
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_ ...