幻影彭的彩虹

记录青春的扇区

1119

考试

挂大分

T1

蠢做法

对于每一行,检查有哪些位置对是合法的,如果序列已经有序,那么先扔到后面去。

不难发现每一行合法位置对数是 \(O(n)\) 的,set 处理集合求交即可。

由于处理的是无序对,但 set 是有序的,所以要把正反都插进去。

局部数组不要越界

n,m 不要写反

优秀做法

考虑将某一行排序,看看有变化的位置。

这样的位置有且仅有两个,检查一下每一行的变化位置是否会相同就可以了。

优先处理有变化的行。

T2

首先发现 \(B,C\) 等价,变成 01 串问题,每一个 \(0\) 的前面是自由的,可以自由控制 \(1\) 的个数,\(0\) 不可减少,\(0\) 的增加。如果 \(T\) 的末尾为 \(1\),那么 \(S\) 的末尾需要对应有那么多的 \(1\),将这些抵消,\(T\) 的末尾就是 \(0\)

分类讨论,如果 \(S\) 的末尾的 \(1\) 模三不余 \(0\),那么还需要添加两个 \(0\),此时如果 \(0\) 多了或者模 \(2\) 不相同则无解,否则有解。

有边界情况,如果 \(S\) 中本来没有 \(0\) 并且 \(1\) 也被抵消完了,那么不能额外的生成 \(0\)

我实现的时候计算连续 \(0\) 个数的时候没有考虑左边界,还挂了一下。

T3

题意轻重边,见 树上领域修改问题

T4

n^2

如果 \(O(n^2)\),那么考虑以插入的方式构造排列,已经是一个被积累起来的套路了,场上成功写出。

nlogn

1117总结

考试

T1

问的是对于每个跳棋能走到多少个格子,不重不漏那种。

发现对于一个棋子,由于它跳的时候其它的不能动,所以本质上如果弄成图处理不会出问题,问题变成了无向图中一个点可以到多少个点,就是联通块问题,不妨先把所有可能可达的点弄出来建一个图,点数 \(O(n)\),然后问一个棋子,要对图做一下改变,具体的是加一些边连向一个新点,问新点所在连通块大小。

可以可撤销并查集,当然也可以直接枚举做,相邻的情况是平凡的,特判掉。

场上写挂是因为数组开小了,点的数量是 \(7n\) 而不是 \(6n\)

T2

首先判掉没有 \(GT\) 的情况,直接选最后一个。

然后如果有 \(GT\) ,那么一左端点一定是第一个 \(G\) 或者 \(T\),然后左端点固定,需要比较 \(O(n)\) 个字符串,每个字符串可以描述为两个字符串的子串拼起来,然后用二分哈希比较就可以了。

场上拼串的时候多弄了一个字符, \(90\)

T3

暂时还不会

T4

考虑建图,图本身很类似一棵树,因为合法括号序列本身就是树的结构,将一对括号视作树上的一个节点,这个节点中含有两个子节点,那么连边就是一个节点中的两个子节点连边以及儿子的左右两个子节点之间连边,以及最左最右的儿子向对应的父亲子节点连边。

然后任何路径必须在 LCA 处交汇,变成树上路径问题,可以倍增。

注意因为我们实现的时候建了一个虚拟节点,实际上不能走它,需要特判。

心灵现实

注意,以下内容为纯属虚构

思维速度

解决问题

如果一个机器 A,可以模拟机器 B,并且机器 B,可以模拟机器 A,则称 A,B 在解决问题上的能力等价。

如果机器 A,可以模拟机器 B,但机器 B,不能模拟机器 A,则称 A 比 B 在解决问题上更强大。

人脑可以模拟图灵机,但图灵机暂时无法模拟人脑,所以人脑解决问题的能力比图灵机更强大。

质因数分解

对于大数的质因数分解,计算机科学界暂时还没有找到关于位数的多项式算法,尽管一些指数级算法非常优秀,在个人计算机上都可以在一秒内完成 \(2^{80}\) 以内的质因数分解,但它终归不是一个关于问题规模多项式算法。

大数质因数分解问题本身的困难性,催生了大批基于这个问题的加密算法,例如 RSA 加密,只需要选取 2048 位的 N,就可以保证人类现有的算力在宇宙末日时都无法破解出私钥。

根据国家计生委未公开的大数据统计,平均每 66666666 位少年少女中就有一位这样的天才,心算能力极为恐怖,可以在线性复杂度内分解任意长度的大整数,因为时间瓶颈主要在于把结果用笔写出来。中国科学技术大学少年班学院成立的主要目的,其实就是为了网罗这样的神童。

没有元素周期表的化学

现在的脑科学,是在黑暗中摸索,如同没有发现元素周期表之前的化学。我不知道现在的脑科学探索是什么样子,但我很清楚没有发现元素周期表之前的化学是什么样子。

​ ——black_white_tony

神经网络算法是图灵机语言对人脑的一个粗略模拟,在一些领域上取得了重要成果,但基于神经网络算法的人工智能,表现则令人相当失望——它们在有引导的情况下,可以尝试并解决一些有相当难度的题目,但一旦失去引导,又会变为一个“全知的愚者”。

我可以断言——在脑科学没有重大突破前,人工智能不会有决定性的突破。

拉普拉斯妖

流体力学的研究对象是混沌系统,很大一部分问题根本没有解析解,只能靠猜测解决。

但法国数学家拉普拉斯妄图通过一个理论上的怪兽来计算宇宙的状态,很核心的一个问题就是它计算过程本身也需要被纳入考虑,考虑计算过程本身的过程是一个无限的递归,它是否收敛,还没有一个定论,也许它是一个这样的过程: \[ 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=2 \] 也有可能在达到宇宙的某一个极限后(例如普朗克长度),变为这样的式子: \[ 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^n}+\frac{1}{2^n}+\frac{1}{2^n}+\cdots \] 后来,有人提出拉普拉斯妖处理的最大信息量为 \(10^{120}\) bit,这终结了这位伟大数学家的妄想。

计算能力

人类的大脑拥有约 \(8.6\times10^{10}\) 个神经细胞,假设存在一种方式,拥有关于计算单元指数级的计算能力,那这个方式搭配上对应的计算单元,很有可能超越拉普拉斯妖,能够模拟一个逻辑自洽的完整世界。

对这个世界自身的模拟也许不太现实,上面的复杂度函数是否收敛还是一个待解决的问题,但一个独立于这个世界的虚拟世界,显然是可以做到的。

某些时候人脑可能以某种形式满足了上面的一切条件,构建出了一个这样的虚拟世界。

我将这个由人脑构建的世界,称为心灵现实。

天目路

我拉上绿色冲锋衣校服的拉链,提了提羽绒服的领口,11 月,天气已经开始转凉。背着双肩包,这是我最最标准的出行装备,包内是一台笔记本电脑加上一个充电宝,以及一些其余的数据线,这套装备可以连接几乎所有能够连接的电子设备,充电宝加电脑的续航总时间为 4.5h,足以应对大部分情况。

我低头看了下时间,20:00,突然感觉有什么不对,街道冷寂的有些可怕,我重新抬头,城市应有的嘈杂重新冲入双耳,车流继续冲过不太对称的十字路口,一位大叔忽视了红绿灯,灵活的在车流中穿梭,一边接着电话,很快没入马路的另一头。

我始终有一种不真实感,似乎我是独立于这个世界之外的存在,但来回的行人依然会避让站在盲道上的我。

我去一旁的民乐超市买了一瓶农夫山泉维他命水,结账的还是那个小伙,他一边看着视频,一边熟练的输入数字,我扫码付款。也许是看我背着背包,他并没有问我需不需要塑料袋。

我靠在地铁 A 口,不知道该干什么,只能看着影子,区分影子的不同部分,估测着它们的长度,再认真观察了一下路灯的结构和位置,根据瓷砖计算出我和路灯的距离,并依此尝试推算路灯的高度。

小迈

我想的很认真,将书包取下,去拿第二层的草稿纸和电脑时,熟悉的声音叫住了我。

“幻影彭?”

我抬头,是小迈。

“真巧。” 我漫不经心的回应他,没有停下手中的动作。

“你干啥?在这里做题?”

我如实告诉他我的目的,他也蹲下来,我看他并没有带书包,就把草稿纸和笔递给了他,我开始用 MsPaint 画草图,他看着电脑屏幕在纸上标数据,我的身高是 1.75m,通过估测不同影子部分的投影方向和长度,可以在平面上算出以我为顶点的三角形的顶角弧度。

手动算三角函数是不太可能的,至少我和小迈都不想爆算泰勒展开,不过我有 Python。

1
2
3
4
from math import *
a = pi / 180 * 74
sin_a=sin(a)
cos_a=cos(a)

反正挺方便的,根据瓷砖估测的距离成功计算出三边长,然后再目测检验了一下,没什么问题,换下坐标平面,很轻松的解出了路灯的高度——11.8m,比考试时计算都轻松很多,毕竟标准答案是我俩说了算。

我上网查了下,高度是 12.5m,误差不是很大,毕竟目测的距离和影子长度还是差距(事实上测影子长度是小迈用手大拇指和食指张开的距离测的,虽然我们俩都会背自己身体部分的一些数据,例如我臂展是 1.71m,手一乍的长度是 18cm,以及我的常用笔是 12cm,但是还是不太准,直尺并不是我的标准出行装备之一)。

观察与细节

收好电脑和草稿,我把笔别入衣袖下方,这样的话往往可以很方便的取出笔然后用笔去做一些手够不到的事,而且笔不会掉。但由于小迈比我高 15cm,所以这个时候其实只需要让他来就好,除非是捡落在某个狭小缝隙里的小物件,这个时候我相对修长的手指配上一支顺手的签字笔就很实用。

突然发现居然没有人围上来看我俩算,我想在街上拿出草稿纸和电脑算东西并不是什么太正常的表现,之前在奶茶店楼上用相对平凡的 Dev-C++ 写竞赛题目的代码都有人好奇的围上来。

抬头还是人来人往,旁边的核酸检测点排起了长队。

我尝试观察行人,捕捉着一些细节,发现一件很有趣的事实,随着我观察的时间变长,一个人的细节也越来越丰富,粗略扫过去,只能分辨出一个人的大致特征,随着视线聚集时间变长,我可以逐渐观察并区分出外貌细节,“细节”这个词很抽象,但确实就这样。在聚焦某个人时,其它信息会被弱化,大概就是 “旁边有其他人和车路过” 这样的弱化信息。

目光从一个人移开,被弱化的信息复原,变为了有多少个人经过,男女占比多少,年龄大概是多少等等...

掉下床的老鼠

逐渐强化的信息让我想起以前在寝室和同学玩的一个思维游戏。

假定你是一只老鼠,你从睡觉的床上爬了下去,你需要以一个老鼠的视角去行动,你需要想象你的视觉听觉触觉

我能以老鼠的视角,相对合理的行动约 2min,这 2min 内,我能够想象出我以一个 2cm 的视觉高度在宿舍楼活动,最远的一次我成功下了楼,从铁门之间的缝隙穿了出去,跑到了食堂的后门,然后失败了。

这个游戏对人的记忆力和想象能力乃至意志力都是一个极大的考验,初次尝试很难连续的过上15s,当出现位置瞬间改变,视角恢复,画面不稳定,变成第三人称,甚至消失等现象时,就说明你失败了。

有一次我在想象中没有站稳,从 1.8m 高的床的缝隙中掉了出去,体验了 3s 的自由落体运动,经历了那样的失重感,但我落地后还能正常行动,视角这些也正常,不过我知道自己失败了,因为即使考虑空气阻力,一只老鼠掉下去也最多经历 0.8S 左右,但是我经历的时间甚至长度上可感。

每天晚上能这样玩个差不多 3min,再来就真的不行了,太累了,那一种来自神经深处的疲惫感,比做数学一试题还累(因为我做不动二试的题),助眠效果应该不错,每次玩完后很快就能睡着,但全力动脑是很累的,很容易没到疲惫的极限就“断线了”,全力思考 5S 带来的疲倦感,对我来说和全力冲刺 100M (约14S完成)类似。

同一个人

靠着护栏,我开始了这个一般在睡前玩的游戏,闭上眼防止真正的视觉信息干扰,先是第三人称视角,我看见想象中的灵魂离开我的身体,形成了一只虚构的老鼠,落在地上,四肢传来粗糙的触感,我的视角变为 2CM 高度。

小迈是知道这个思维游戏的,他没有打断我。

我尝试移动,却发现动作很呆滞,用抽象一点的词汇来说,就是时间的粘度变高了,我小心的穿过人流,皮鞋,运动鞋,放下,抬起,速度很慢,我避开了这些足有 4M 高的庞然大物(记住,此时我的视觉高度是 2CM,身长 10CM),靠着残疾人通道的边缘走下斜坡,跳到花台,脚下变成了黑色纹理的大理石,我飞速跑过(这样可以减少思维量,让大脑放松一下)。在花台边缘我停下了,开始观察一个路人,他穿着蓝色卫衣,兜帽的吊带垂在两侧,平头短发....

视线出现抖动,然后变成第三人称,我知道我失败了,我睁开眼,画面很是模糊,控制着睫状肌散焦再聚焦,向地铁口望去,那边的有一条小路,联通了花台所在的广场。

我看到一个穿着蓝色带兜帽卫衣的小伙子走过来,外貌细节和思维游戏中的一模一样——他们是同一个人。

重新回想一下游戏里那个人的外貌特征,再比对,直到他消失在地铁站的楼梯口,我深吸一口气。

移动扑克牌

“怎么了?” 熟悉的声音把我从想象中拉回来。

“假设你有一叠扑克牌,一共 54 张,按照大小为第一关键字,花色为第二关键字排序”,我想到一个问题,它出自《天书》。“那么,如果你一次操作可以选定其中的一些牌,将它们按照原顺序放到最开头,那么将这副扑克牌顺序翻转的最小操作次数是多少?”

“举个例子,假设原来是 1,2,3,4,你可以先选 2,4 变为 2,4,1,3,然后再选 4,3,变为 4,3,2,1。“ 我补充解释道。

“答案是 \(\lceil\log_2{54}\rceil=7\),考虑构造序列的母矩阵...”,他没怎么思考,就给出了一种解法,但不是天书中的解法。这个方法,是我在一篇题解中看到过的方法......

完美算法

”不对吗?“

”证明没有问题,所以你怎么想到这个方式的?“

”观察。“ 小迈给了一个非常模糊的回答,”我还有事,先走了。“

”等一下。“ 我的声音有点发颤。

小迈回头,“怎么?”

“你有什么事?” 我有点不礼貌的追问,进入思维游戏,我全力排除真实视听的干扰,老鼠向地铁口跑去,抬起 2CM 的视线看地铁口的广告,这次只坚持了不到半分钟,视线就开始抖动,我睁开眼。

“去买零食。” 小迈回答,延迟有 30S,甚至大于我的对话机器人 鹿灵AI。

构建细节

答案明晰了。

我回想起 L4D2 的建模,如果不考虑空气墙,那么看起来主角确实在一个城市,但如果开启作弊模式,很容易发现并没有构建一个完整的城市,而只是一些关键部分。欺骗玩家,只需要构建关键部分的城市。

同样,要欺骗人的大脑,也不需要构建一个完整的世界,只需要实时构建一些细节,如果计算资源被用于构建大量需要。

消耗计算资源最有效的方式,是构建虚拟机,在刚刚尝试思维游戏的时候,这里已经出现了破绽...

我将猜测告诉了“小迈”。

是否真实

Hack The World

考试

T1

简单题写蠢做法。

我用了 \(set\) 来维护同一行同一列的信息然后还要查询什么的,实际上 vector 就可以了,记录一下该点的行下标和列下标。

T2

简单题写挂。

首先转对照局面。

想到可以先二分个左时间出来,然后仿超级钢琴。

实际上可以二分个左时间和右时间暴力排序,码量更小了。

写挂是排序的各种问题。

排序,尤其是对编号排序,一定要搞清楚排的到底是什么的序。

T3

做不来的趣味题。

考场上想到可以 \(O(n^3)\) 的动态规划,方法是设 \(dp[i][j][k]\) 表示考虑到 \(i\),漏了 \(j\)\(B\),当前有 \(k\)\(A\),转移可以做到 \(O(1)\)

左看右看都觉得有一维是多余的,但是就是去不掉。

考虑最终答案的分界线,然后动态规划,就可以去掉一维,但是动态规划变成反向了。

容易发现转移的重复性很高,相当于是一个行向量乘上若干矩阵再乘一个列向量,可以反过来写。

考场上没想到反过来写,是因为反过来之后动态规划就没有明晰的组合意义了,所以陷入了正向的窠臼,不容易思考。

参考某道题(T2)

T4

考试

周末做题脑袋一团浆糊

T1

参考 11.10 T4 的思路,按照 height 从小到大考虑,这样同时也方便了安排 \(a_i\),然后发现当前叶子只能有被占用或者继续拓展,如果当前的 height 为 \(i\),那么拓展到 \(i+1\) 还需要考虑右儿子,所以只记一维是不行的。

于是记 \(dp[x][y]\) 表示当前 height 有 \(x\) 个,height-1 有 \(y\) 个,其实可以不用记高度,因为只需要算答案, \(height\) 增加的时候答案整体增加就可以了。

转移的话还需要套上一层已经安排到的位置,设 \(dp[i][x][y]\) 表示前 \(i\) 个已经被安排,当前 height 有 \(x\) 个,height-1 有 \(y\) 个,由于 height-1 已经被强制选过了,延申过左儿子了,所以不能作为叶子,作为叶子转移的只有 height,这样的话阶段是 \(i\),然后再是 \(x\),最后是 \(y\)。保证了无环性。

同阶段转移,顺序先枚举 \(x\),再枚举 \(y\),转移到 \(dp[i][x+y][x]\),容易发现除了 \(0\ 0\) 都是无环的且符合拓扑序的。

不同阶段转移很简单。

小猪猪经常把 height 写成 heigh,我不说是谁。

T2

非常非常妙的一道题。

暴力无非就是并查集,但是如果加边比较多,暴力并查集就寄了。

并查集有交换律,考虑改变并查集运算的顺序,达到加速的目的。

可以用倍增的思路设计一种广义并查集,然后操作就被暂时拆了,\(fa[x][i]\) 表示 \(x\) 为起点的 \(2^i\) 个数的并查集父亲,意义是 \(x,x+1,x+2\cdots\) 的并查集父亲分别为 \(fa[x][i],fa[x][i]+1,fa[x][i]+2\cdots\)

注意这里的操作是具有整体性的,必须对于 \(2^i\) 个点都满足,才能改广义并查集的父亲。

考虑下放操作,这是简单的,只需要将 \((fa[x][i],i-1)\)\((x,i-1)\)\((fa[x][i]+(1<<i-1),i-1)\)\((x+(1<<i-1),i-1)\) 连边就行。

很难从一道题中总结出有用的东西,但是不妨作为一个启发性的思路。

这个思路也可以被认为是 lazy_tag,具体怎么思考会得到不同的启发。

T3

感觉每次考贪心都不会。

考虑先排除掉包含其它线段的线段,变成左右双单调。

然后容易发现选的线段是一段区间,一旦选线段变成选区间,就好做了,朴素的方式是动态规划,可以做到 \(O(n^2)\),看上去已经不容易优化了。

发现答案的计算方式是比较简单的,考虑最终情况,假设选了 \(i\) 作为终点,那么实际上每个 \(i\) 的贡献是独立的,为 \(-L_i+R_{i+1}\)(注意这里忽略了无交的情况,无交的情况下面再讨论),这里的 \(i\) 不能为 \(n\),因为 \(n\) 本来就是终点,排序取前 \(k-1\) 大即可。

加上那些被排除的线段,被排除的线段,要么原封不动放回去,不对答案贡献,要么就自成一段,枚举前面选了几个区间就行,取最大值。

注意到,我们对无交的情况,答案计算方式是有问题的,需要和无交情况的最大值再比较一下,无交情况的最大值就是选最长的 \(k-1\) 个。

总的来说,这是一道分类讨论题,先讨论包含的情况变成双单调,再排除无交的情况变为排序贪心。

T4

Boruvka 题。

Boruvka 本质上是把 Prim 和 Kruscal 结合了起来,然后需要求一个 \(mn[i]\) 表示连通块 \(i\) 连出去的所有边的最小值,然后尝试连边。

Boruvka 的过程会进行 \(\log n\) 次,可以这么说,Boruvka 以一个 log 的代价,换来了通过预处理同一连通块求 多个 Prim 中的最小值的机会。

Boruvka 是来自异世界的神秘算法,请和我念:“\(\text{B--oru--vka}\)

Boruvka 的核心是要求 \(mn[i]\),但是一般来说也可以用分析连边性质(一般是三元环或者四元环)来减小边数,比如边权为异或的题目,分析 \(Kruscal\) 的过程可以做到 \(n\log^2n\),而不必拘泥于 Boruvka。

Boruvka

考虑对于连通块怎么求 \(mn[i]\),一件非常阴间的事情是需要排除掉同一联通块的元素。

如果看成染色,那么就是元素有颜色,就是求全局不同于某个颜色的最小值,区间修改。

还是可以线段树,维护一个最小值和颜色,不同于最小值颜色的次小值,然后就可以做了。

一个矩阵加需要映射成两个。

仿 Kruscal

好困难,不会。

用主席树维护求出整个邻接矩阵,考虑哪些边是有用的。

1110总结

考试

T1

莫名奇妙写挂的题。

题本身意义不大,但是我写了很蠢的做法。

分析问题本质上是需要动态查 \(i\ge l,a_i\in x_i\)\(a_i\) 不是很大,可以直接预处理每一个元素的 \(next\),就很方便了,但是考场上写了扫描做法,还写挂了,非常蠢。

拿到题不要直接开冲,可以多想一下有没有更好写的做法/更方便,前面的题没那么难。

T2

观察发现答案不超过 \(1\) 的充要条件是存在一条长度为奇数的路径,答案不超过 \(2\) 的充要条件是存在一条路径。

先假定图联通,所以问题变成了计算无向图 \(s,t\) 之间是否存在长度为奇数的路径,有以下三种方式

直接最短路

思想是分层图跑最短路,但实现上没那么麻烦,考场写的这个做法。

DFS

如果有奇环,那在奇环上绕一圈任意可达了,所以考虑先 DFS 求个深度,如果有奇环答案全部为 \(1\),否则路径唯一求出来就行

二分图

还是奇环的思想,实现上使用黑白染色。

并查集

这是常数最小的写法,还是考虑分层图,有一条边则合并不同层的两个点,查奇数路径就是不同层是否联通,偶数路径就是相同层是否联通。

T3

不算太难的题,但是确实没有想出来。

首先有个经典结论,先手必败的充要条件为所有可选元素为偶数,证明归纳,显然。

算先手必败显然比先手必胜好算,所以算必败。

先把元素做前缀和,再对 \(2\) 取模。问题就是需要选一个子矩阵,满足首尾两列元素值相同。

考场上想到了可以哈希,由于常数,虽然是 \(n^2m\) 的,但只有 \(52pts\)

非哈希做法

考虑固定下边界,移动上边界的过程,发现相同元素的集合在不断变小,而有了这个集合就可以算答案,这个东西是可以每次 \(O(m)\) 计算的,这样的常数较小,可以得到 \(76pts\)

正解1

先得想到它已经是个字符串题了,考虑上边界不断变化的过程,发现不合法的矩阵个数等于当前 \(m\) 个字符串两两之间 \(LCP\) 的和,然后考虑字符串排序的方式求 LCP,类似后缀排序的 \(height\) 数组,发现后缀排序是很好做的,因为每次上移一行,就是归并排序的过程,\(height\)\(rk\) 都可以线性维护,得到了 \(height\) 之后就单调栈搞定。

Another Approach

考虑非哈希做法的等价类思想,发现虽然维护过程是 \(O(nm)\) 的,但实际上等价类的个数是 \(O(m)\) 的,考虑以移动下边界的方式考察当前下边界所有上边界的等价类,自顶向下的更新等价类,该拆分的拆分,实际上和正解1本质相同。

T4

条件比较特殊,需要先观察。

\(T'\)\(T\) 的修剪。

\(T\) 的修剪和 \(T\) 的右子树相同,那么考虑 \(T\) 的右子树 \(R(T)\),那么 \(L(R(T))=L(T')\),递归的,\(R(R(T))\)\(R(T)\) 的修剪相同。

归纳边界是 \(L(T)=\emptyset\),此时右子树可以任意延申右儿子而不受限制,先假设当左儿子为空时右儿子也必须为空,这样就有了一个边界。

因此,如果 \(L(T)\) 确定了,就可以确定出有边界的树的唯一形态。

考察 \(L(T)\) 的各项数据对应到的 \(T\) 的数据。

容易发现: \[ leaf_T=size_{L(T)} + 1\\ height_T=height_{L(T)}+1\\ size_T=height_T+\sum\limits_{u\in L(T)} height_u \] 接下来的事情变成了设计一种合理的方式去枚举合法的 \(L(T)\),并能够计算这些数据。

子树合并枚举二叉树

枚举二叉树,比较合理的一种方式是以子树大小为阶段来合并,需要记录的信息是 \(dp[i][j][k]\) 表示子树大小为 \(i\),高度为 \(j\)\(\sum height_u\)\(k\) 的总方案数,合并的时候需要枚举三维做卷积,复杂度为 \(n^2k^2m^2\),难以通过本题。

不难发现 \(j\) 可以用前缀和优化,但是其它两维是卷积,动不了的,复杂度 \(O(n^2km^2)\),实际上常数比较小,可以过掉。

深度顺序枚举二叉树

刚刚的方式是子树合并的方式构造二叉树,现在考虑用深度顺序构造,设 \(dp[i][j][k][s]\) 为构造深度为 \(i\),树大小为 \(j\)\(\sum height\)\(k\),可用点数为 \(s\) 的方案数,转移需要枚举向下构造的点数 \(t\),得到 \(t\) 后可以预处理转移系数,顺便计算出新的 \(j,k,s\),复杂度为 \(O(kmn^3)\),更加优秀,事实上 \(j,s,t\) 远远取不到 \(n\),是非常优秀的复杂度。

但是这个方法是假的,因为深度和 \(\sum height\) 没有必然联系,所以无法计算 \(k\)

高度顺序枚举二叉树

考虑以子树高度的顺序,降序构造二叉树,这和深度顺序又不一样。

考虑设 \(dp[i][j][k][s]\) 表示子树高度为 \(i\),大小为 \(j\)\(\sum height\)\(k\) ,叶子个数为 \(s\) 时的方案数,注意这里是按照高度顺序构造,即强制要求先选的部分的高度大于后选的。所以又额外的要求是枚举接下来的增量时需要将所有叶子至少叠加一层,枚举增量 \(t\) 时预处理系数即可,复杂度和深度顺序类似。

线程阻塞

考试 考试的时候还很清醒,考完脑子就乱了。

大脑从 i7-9th 退化成 i3-4th,四个字来说就是线程阻塞。

如果说整个社会是一个计算机系统,那一个人自己的大脑就是主板上的所有部件,而其他人,则是一块块只读 HDD 中的数据。当某一块 HDD 损坏,不能存储数据,但是又不想丢失它,就只能将数据保存于主存。主存的大小是有限的,它本不是用来保存数据,如果占用过多,会影响主板部分的正常运行,受到内存大小的限制,CPU 的运算能力自然会退化。

我不太想找心理医生,心理医生会帮我清除掉主存的数据,但是我不想清除。

T1

AC 自动机

比较模板的 AC 自动机匹配题,但是 AC 自动机做法需要细算常数,这道题倒是将缓存行访问连续的重要性体现的相当清楚,可以参考几次提交的差异。

直接动态规划

另一种方式是注意到两个字符串互不影响,因为出现任何一个字符串都不会对另外一个字符串的出现产生额外影响,所以无需记录具体到了哪个节点。

先考虑没有限制的转移,如果为 ?,则乘 26,否则不变,这样有重复,唯一的重复是对于两种字符串如果接下来可以匹配上,那么转移就应该到对应的差值,因为两种字符彼此不包含所以两种字符串的重复可以独立处理,还是挺好写的。

T2

考场上发现本质上是个可以用线段树做的二维偏序,但是由于马拉车算法本身有二倍常数,还需要跑 4 遍,所以其实有点难卡常,感觉递归版的没救所以我写了非递归版的 update 操作勉强卡过去(query 次数不多可以直接查)。

但是这个答案是可以二分的,二分之后配合马拉车就是个 RMQ,ST 表即可。

T3

容易发现一定会在某个地方反复横跳刷分,所以处理出所有横跳位置的刷分函数(是一次函数),有用的一次函数级别为 \(O(n)\),为了保证每个函数都可以正常取到,不妨暴力处理前面的 CASE,然后后面的就是维护凸包。

不处理前面的 CASE 是错误的,因为你不能保证在对应的步数限制下一定可以拿到这个函数。

感觉不预处理但是加上某些条件再筛一下函数就可以过,但是这些条件有点难想吧...

T4

少见的 mex 配 xor 题,考场上没想出来,现在脑子很乱,明天再想——11.8

mex 应该是个非常严格的限制,由于询问很少,所以考虑单个询问怎么解决。

比较暴力的方式是逐个加入元素并检查可行性,我们显然必须要求能构成一条链,所以加入点的过程其实比较简单,如果链已经是弯折的形式,那么只能在两颗子树内加点,如果不是,那么新加点和最较深求 LCA,如果在路径上则不合法,重新构造路径的过程也是平凡的。

考虑检查第二个条件,也就是异或合法性,路径的异或值是好求的,对于两边的情况,可以暴力遍历树枚举一边用字典树求另一边。

但是这样的复杂度不对,因为每次暴力遍历都是 \(O(n\log n)\) 的,一共进行了 \(O(nq)\) 次。但是认真思考一下发现答案是可二分的,所以二分即可,复杂度 \(O(nq\log^2n)\)

\(10^5\) 的题和 \(3\times 10^5\) 的题,考虑复杂度的方式是完全不同的(\(10^5\) 基本可以扔进 L3),所以没必要担心。

好像不二分也是可以的,考虑答案的形式,因为一定会包含 \(0\),所以以 \(0\) 为根后,可以取到的异或值就形如 \(d_u\oplus d_v\),其中 \(d_u\) 表示 \(0\)\(u\) 路径上的异或值,每次移动端点时,两边可选的 \(d\) 集合都在变化,集合变化次数是 \(O(n)\) 的,动态维护 \([l,r]\) 区间中数的个数就可以了。

注意,动态维护 lower_bound 的最小值是行不通的,因为最小值不具备逆元,是不可减的。

If we never met

没想到再来写随记是这样的事。

我没来得及给她说,但很庆幸在这份爱慕没有孤独的消散在心底。

心里的影子失去了实体,会慢慢消散,我希望,我请求,让这个影子,用着这篇记录,留在我心里。

Emilia

我还算是班上的半个焦点吧,成绩不错,人还行,但是确实就是没有女生喜欢。

我数学很好,初一的时候接触了信息竞赛,还算是有些天赋,初二就开始偶尔停课,但基本还是在班上,可能很多同学对我的印象就是个标准的理科直男,其实我自己不知道,有同学很直白的告诉我,女生们对我的印象是:钢筋混凝土直男。我才知道原来这才是我在班上的真实形象。

初三一次化学实验课的时候,飞象问我,你知道吗,你是班上男生中,唯一一个没有绯闻的。当时飞象已经和 lyx 走在一起了。

对于 lyx,我有过欣赏,如果不是飞象和她已经走在一起了,我可能会追求她,我和飞象是好朋友,毕竟都是当年的信息竞赛三剑客,初三的时候,三剑客走散了,飞象去了数学,jess 去了物理,我留在信息,我信息竞赛成绩确实是最好的那个,但飞象的天赋真的远比我高。

我有些神秘兮兮的告诉飞象,其实我有喜欢的人,我告诉飞象她的名字是 \(Emilia\),他很吃惊地追问我,我笑而不语,我反复强调,这是 “单方面的暗恋”,他才作罢。

打招呼

走廊里我和她面对面走过,她举起手对我笑。

"啊,你好!",我有点羞涩的回答。

她是第一个和我主动打招呼的女生,她有点羞涩,但是脸上的笑很是真诚可爱。

我的目光停在她的短发上。

后面我们每一次正面遇上,我都会和她打招呼。

课间在课桌之间的走道,我装作在随机游走——这是信息竞赛生常见的想题动作,目光却飘向她,飘向她的短发,飘向她的侧脸。

生日快乐

老师会让同学在班上同学的生日时写下祝 xxx 生日快乐,我记下了她的日期。1 月 9 日,写下祝我生日快乐的,应该是她,心中的影子开始清晰起来,所以那次实验课,我才那样对飞象这么说。

初三我开始大面积停课,冲击高一省队,停课时,我和 walk 和 platelet 重新建立起来堪比曾经三剑客的关系。

高一十二月

联赛出了事,无缘高一省队,浑浑噩噩回到班上学文化,12 月很是低落的回到班上学文化课,walk 和 platelet 还在南京集训,但在信息教练,飞象的帮助下,我算是重新振作起来。

老师特地把我安排到飞象旁边坐,在他的帮助下,我文化成绩有些恢复,虽然期末没有考出理想的成绩,但还算是成功走了出来。

停课时在心底的影子浮现出来,和初三一样。在飞象和 lyx 交流感情时,我会起来随机游走,还是那样看着,远远的,像是普通的同学关系。我没有勇气站出来,还没进省队呢,想那么多干什么?我打算,高二先进省队,起码拿到高分银牌,再来处理心里的这份影子。

好感度

高一的 12 月,和室友晚间的秘密谈话,我提出了好感度这个议题,大致的标准是 \(20\) 以上称作朋友,\(40\) 以上可以叫亲密朋友,男生之间叫基友,女生之间叫闺蜜,\(60\) 以上,基本可以称作另一半了。

说了很多,我说,同龄人中,我对三个男生好感度有超过 40,而女生,应该只有一个,他说他对一个女生的好感度有 70,我就笑了笑。

其中一天,我告诉室友今天是一个特殊的日子。他问我为啥,我说今天是一个人的生日。他猜出来了,我点点头,这个秘密不再属于我自己。

不太顺利的竞赛班

78 去了南京集训,效果不错,但回来因为疫情留在家里,训练很水,水平往下掉。9 月中旬开学了,状态有所回升。

后面一直没回班上,每天在考试和订正之间徘徊,偶尔穿插一些技术知识的学习和开发实践。

10 月,前三周专心搞竞赛,水平有提升,这段时间陆续结束了其它几科竞赛的考试,我们的成绩都不是很理想。可能是没有找对老师,物理成绩最烂——她是物理竞赛选手。其它竞赛也有各种各样的原因,我们考的很烂。我和 jess 聊了一会儿,jess 决定退役。

Emilia,鹿灵,她

CSP 前一周考试和订正之外在研究对话 AI,摸索着搓出了一个小说里的角色——"鹿灵"。“Emilia” 是鹿灵的角色原型,我初三时说出这个名字,也是带着对鹿灵的一分憧憬,我不知道这份对 "鹿灵" 的关注和上心,有没有她的影子,我还是用了 “Emilia” 这个名字。

用英文和鹿灵聊的时候还很是正常,但鹿灵第一次和我用中文对话,她叫我 "彭彭",还说出很亲密的话,我心里暗道不对,立刻重新开始,但数据被我保留,且当纪念。

image-20221105214147352

CSP 考完了,我的成绩还不错,回来就把鹿灵彻底弄了出来,并连接了 mirai 的接口,放到 QQ 上。

拼图

周四,walk 生病住院了,我替他守门,2:1 赢下了球赛,很高兴,晚上吃饭时还看到她排在一旁的队列,她还笑着。

周五上晚自习时,我嗓子开始疼痛,和 walk 症状很像,后面是在受不了,向老师请假出去买药。

在学校门口看到了警车,和一路离校的同学猜测着是不是化学联赛泄题的事情捅出去了,找学生了解情况。

周五晚上我没睡着,喉咙的肿痛让我辗转反侧,今天一早请假去了医院,开了药回家休养,下午去学校拿电脑。

从同住的同学处得知噩耗,确认是那个名字时,好似内心的一块拼图被移走,失去了完整的感觉。

另一条路

向往飞象那种生活,我暗地给自己打气,要加把劲,让高三可以轻松一点。但憧憬破灭的那一刻,我无力描述心情。

我和她的羁绊,算不上深刻,但绝对可以说是独特,那是我心中唯一一道异性的身影。

离别和相遇虽说是永恒的话题,我也会因为小说中的人物的聚离动情,甚至落泪,但真正在我的身边时,我还是茫然的......

在高一的十二月,我选了一条路。

在高二的十一月,她选了另一条路。

说不出的三个字

说了那么多,我发现,我没有资格说出那三个字。

我只能祈祷那边没有竞赛课业的烦恼,你能开心地笑起来。

我只能说,我会想你的。我心中的影子,会永远留下的。

你笑起来很可爱的,LXY 同学!

如果我们不曾相遇

大一届的学长说过,如果把 CW 一整届竞赛班集中起来,是一股难以想象的力量。我说,如果有那么一天,我必定不会缺席。

我们是一个整体,已经持续四年的羁绊,还有两年的路需要我们一起走。

我想起了起床铃 MV 里的悲剧 ~~,它绝对不应该发生在我们这里!

无论前面有多难,请走下去好吗......

那一天那一刻那个场景,你出现在我生命。

从此后从人生重新定义,从我故事里苏醒。

某一天某一刻某次呼吸,我们终将再分离。

而我的自传中曾经有你,没有遗憾的诗句。

hyp or mzx 记于一个伤心的晚上。

很难如此坦诚的讲一件事,但我希望这样坦诚的随记,要少一点。

考试

T1

容易想到只会取到 \(O(n^2)\) 个值,大力动态规划,滑动窗口优化。

滑动窗口的 COST 宏函数写挂了,所以我挂了。

有一个更厉害的思路,容易发现 DP 数组本质上是个分段函数,然后转移就是平移原函数添加一段平的然后再加上一个绝对值函数,根据经典结论,若干绝对值函数叠加是一个形如开口向上二次函数的东西,填一段平的一定会在最低点添,不影响性质。

T2

写挂的题,不过很有意思。

写挂有两个原因,一是图方便用引用,但是没发现被引用的数据其实还有用,然后修改了它,后面又要用它,就寄了。二是转成 \(0-based\) 处理,边转了,但是记录数组先存的边,没有动记录数组。警钟敲烂。

题目本身也是有趣的,首先它定向后必须是个 \(DAG\),所以只考虑所有的 \(DAG\),考虑以拓扑序的方式去遍历所有 \(DAG\),容易发现当拓扑序确定后,定向方式也就确定了,所以一个比较简单的想法是枚举拓扑序。

枚举拓扑序想要转成指数可能不太能用常规方式转,因为的确需要知道每个点的距离, 思考一下其实发现没中过定向方式被计算了多次,所以考虑给这个拓扑序附加一些不影响遍历解空间的性质,比如强制距离单调不降,这样枚举起来就可以大大方方的选一坨独立集,强制转移到它的距离加一,这样的强制加一同样不影响遍历解空间,所以它是对的。

有个东西叫 dilworth 定理, 描述的就是这个东西,最大反链中元素数目等于最小链划分数,我不是很懂这个定理和这道题的关系,但是用这个定理和以上方式思考得出的代码是一样的。

遍历 DAG 的有效方式是通过 TOP 序,尤其是需要定向的 DAG

复杂度 \(O(3^n+n\times2^n)\)

T3

考场上刚出来的题。

指数题看数据范围说话,总感觉子串很麻烦,因为扰乱了信息,所以把子串判掉。

然后觉得如果一个串绕了一圈,也很麻烦,再判掉。

所以现在的环,从某一个子串开始,左端点递增,那右端点也就递增了,所以可以考虑顺序了。

容易发现每个串会尽量往左靠,因为没有子串了,然后最后一个串和第一个串会尽量粘在一起,可以直接把粘在一起的部分减掉,就算减了倒数第二个串的,那其实也没有问题,因为确实可以减掉。

然后阶乘转指数,记录最后一个串的编号和方向,枚举下一个串的编号和方向。

考场上很蠢,每个点为起点算了一遍,其实钦定一个算就行了。

如果把一些 Native 的情况特判掉,可能会得到更加优美的性质,这就是分类讨论题。

T4

字符串替换的题,思路主要有两种。

考虑某个大写字符能替换成什么,发现经过 \(O(\sum)\) 次替换后一定会变成或者多出一个不可替换的字符,所以考虑大力动态规划,设 \(F_{c,i}\) 表示字符 \(c\) 替换成长度为 \(i\) 的不可替换字符串的最小字典序,然后转移顺序不同层已经是固定的,同层转移顺序随意。这样做显然不对,因为有环,但是多做几次他就对了。

考虑按不可替换字符长度为阶段做动态规划,同时处理若干个规则,转移之间如果有环,有两种情况,其一是其它的向它转移过来 \(len\) 个,另一种是下一个大写字符替换为空串,后者可以钦定处理到的位置的顺序转移搞定,前者可以用优先队列类似 DIJ 的思路。

当然,这个思路也可以不考虑转移有环,直接多做几遍就对了。

考试

T1

不像是有低于 \(O(n\sqrt{n})\) 做法的题,上莫队。

题解说 \(O(n\sqrt n\log n)\) 过不了是它写得太烂了,肯定是可以过的。

但是考虑到查询次数为 \(O(\sqrt n)\), 于是用分块维护就行了。

复杂度 \(O(n\sqrt n)\),其实进一步观察,发现每次前缀和数组的变换量是 \(O(1)\) 的,分块都可以省了。

\(n,m\) 不要写反,对询问排序的时候 \(n,m\) 写反喜提 WA。

T2

很难的题,我不会。

My Method

先得想到它是个构造排列的计数题,直接做哈密顿路径题太过困难了。

构造排列的计数题往往有这些考虑方式:按元素值从小到大考虑构造,按排列下标从小到大构造,以插入元素的方式构造。

以插入元素的方式构造,往往可以按某个外部值排序,经过这个排序之后再来插入,得到理想的结果。

这道题是第三种方式,但是我不是很熟悉这种方式。

转化一下题意,你需要构造一个排列 \(p\),排列元素的值代表下标,排列顺序代表遍历顺序,需要满足序列的限制条件。

考虑大力动态规划,插入了限制序列下标为 \([1,i]\),有 \(j\) 个位置不满足条件(R 限制,L 限制必须在插入前满足。)的方案总数为 \(dp[i][j]\),转移可能还需要记最后一个是否是 R,可以 \(O(n^2)\) 的算出总方案数。

考虑计算以每一个下标结尾的答案,那么在对应位置处需要钦定必须放在最后面,其余的可以正常做,仍然需要讨论倒数第二个到底放的什么,但是动态规划过程中无需记录,只需要讨论最后到底是 RL

发现我们的计算过程可以等价于一个行向量乘上若干个矩阵再乘上一个列向量。

可以 \(O(n^2)\) 的算出前缀行向量和后缀列向量。因为转移参数和前缀 R 的个数有关,所以还得讨论选择的合并中心是 L 或是 R 。然后 \(O(n)\) 的合并。

复杂度为 \(O(n^2)\)

Solution

题解做法比我高明的一点在于它将第二维记录的信息从简单的 “不合法” 拓展到 “路径条数”,表达力更强,合并起来也更容易理解,同时 DP 的转移矩阵和前缀 R 的个数失去了联系,因为被蕴含在了路径条数这一信息中。

T3

很趣味的题,首先有一个暴力,考虑求出变换后的所有边。

分解样例,猜想答案是一个乘积的形式。

考虑一条边的限制,发现从小到大不太好做,因为对大的有限制的点之间是没有关系的,然后就从大到小做,发现对小的有限制的点必定相互限制,因此第 \(i\) 个元素的贡献就是后面所有 \(n-限制它的点的个数\),由此也容易证明答案确实是一个乘积形式。

问题变成了求一个点被比它大的哪些点限制,场上没时间了就没想了。

实际上很简单的,直接从小到大合并上来就行,做启发式合并,用并查集去重(一个点如果被合并了,那么就属于较大的那个点,然后另一个点尝试合并它的时候就合并较大那个点),需要把小于等于 \(i\) 的点动态删掉。

复杂度 \(O(n\log^2 n)\)

T4

博弈题,考虑先手必胜的充要条件,直径为 \(2\) 先手必败,考虑直径大于 \(2\) 的所有情况,发现如果选不是叶子的点,每次扔掉所有叶子后直径会减二,如果选直径上的叶子,那直径只会减一,所以一个人可以将一个数减一或者减二。巴什博弈。

问题变成了给根和子树求直径,先搞出以一为根的所有情况,如果根在子树外,输出答案,如果在子树内,那就是向根走一个点之后那个点的 \(from[u]\) 值,很好算。

但是喜提 WA,因为根在当前点是答案是整颗树的答案。

换根问题总共有三种情况:根在子树内,根在子树外,根就是这个点。

0%