Misaka16172's Blog

Preface 这是一篇英文题解。This is an English solution. Solution Consider the necessary and sufficient condition for P(T)=vP(T)=vP(T)=v: Edge (v,n)(v,n)(v,n) exists in TTT; Let nnn be the root of TTT. Then, n−1n-1n−1 is in the subtree of vvv. This is because every vertex u(u<n−1,u is not an ancestor of n−1)u(u< n-1,u\ \text{is not an ancestor of}\ n-1)u(u<n−1,u is not an ancestor of n−1) is removed before n−1n-1n−1. If n−1n-1n−1 and nnn are in the same tree, when vvv is both an ancestor of n− ...

Preface 这是一篇英文题解。This is an English solution. Solution Build an undirected graph with the given mmm constraints, connecting vertices xxx and yyy with an edge weighted zzz. After that, consider every connected component independently. Case 1: The connected component has at least ∣V∣|V|∣V∣ edges, i.e. it’s not a tree. In this case, there is a fixed solution if and only if there is an odd cycle in the graph. Conversely, every even cycle has a redundant edge. For example: {a+b=k1b+c=k2c+d=k3a+d=k4\ ...

前言 简单的做法，不需要动脑子。 思路 O(nq)\mathcal{O}(nq)O(nq) 的暴力算法是从左往右顺序枚举，如果有塔顶与当前积木异色的塔就放上去，否则单开一座。设当前有 aaa 座塔顶颜色为红色，bbb 座为蓝色，当前遇到的是红色的积木，那么这个过程等价于 a←a+1,b←max⁡(b−1,0)a\leftarrow a+1,b\leftarrow \max(b-1,0)a←a+1,b←max(b−1,0)。这可以表示成一个 (max⁡,+)(\max,+)(max,+) 矩乘的形式（相当于给 [ab0]\begin{bmatrix} a\\ b\\ 0 \end{bmatrix}⎣⎢⎡​ab0​⎦⎥⎤​ 左乘一个东西），线段树或猫树维护静态区间矩乘即可优化至 O(ω⋅nlog⁡n)\mathcal{O}(\omega\cdot n\log n)O(ω⋅nlogn)。

14(2) 下部分的体积为 VB−AEFD,VB−CDFGV_{B-AEFD},V_{B-CDFG}VB−AEFD​,VB−CDFG​ 两个四棱锥的体积之和，直接算出来，上面的体积是总体积减去下面的体积。 15(4) 设数列极限为 LLL，an+1=an+an−1  ⟺  an+1an=1+an−1an  ⟹  L=1+1La_{n+1}=a_n+a_{n-1}\iff \frac{a_{n+1}}{a_n}=1+\frac{a_{n-1}}{a_n}\implies L=1+\frac{1}{L}an+1​=an​+an−1​⟺an​an+1​​=1+an​an−1​​⟹L=1+L1​，由于 L>0L>0L>0，解得 L=1+52L=\frac{1+\sqrt 5}{2}L=21+5​​。 17 看错字母，只剩 3 分。 (1) 作 CPCPCP 中点 FFF，连接 EF,DFEF,DFEF,DF。 ∵E,F\because E,F∵E,F 为 BP,CPBP,CPBP,CP 中点 ∴EF∥BC,EF=12BC\therefore EF \parallel ...

器材： 只需要刻度尺和打点计时器。 电磁打点计时器电压小（4∼6V4\sim 6V4∼6V），电火花打点计时器电压大（220V220V220V），二者都使用交流电源。 作图：描点时尽量让最多的点被直线连接，直线左端需要延伸至 t=0t=0t=0。 计算瞬时速度要用尽量多的点，假如打了 A∼EA\sim EA∼E 五个点，则 vC=∣AE∣4tv_C=\frac{|AE|}{4t}vC​=4t∣AE∣​。 时间间隔：有 444 个点未画出 ⇒\Rightarrow⇒ 时间间隔为 0.02×(4+1)=0.1s0.02\times (4+1)=0.1s0.02×(4+1)=0.1s。 刻度尺要估读一位，保留 xxx 位有效数字 = 从第一个非零位置开始数 xxx 位。 逐差法计算加速度：尽量利用更多的数据，减小误差。设有 2n2n2n 段（2n2n2n 为偶数，若给了奇数段的话，直接舍弃中间的那一段），第 1≤i≤n1\leq i\leq n1≤i≤n 段长度为 xix_ixi​，则将第 i≤ni\leq ni≤n 段与第 i+ni+ni+n 段匹配，用这两段计算出的加速度是 a ...

前言 唉， 思路 设询问串为 (s,t)(s,t)(s,t)，给定的串为 (a,b)(a,b)(a,b)。 证明一个 (a,b)(a,b)(a,b) 对一个 (s,t)(s,t)(s,t) 的贡献最多为 111 是平凡的，询问即对 (s,t)(s,t)(s,t) 计算有多少个满足条件的 (a,b)(a,b)(a,b)。 设 l=min⁡si≠ti{i},r=max⁡si≠ti{i}l=\min_{s_i≠t_i}\{i\},r=\max_{s_i≠t_i}\{i\}l=minsi​​=ti​​{i},r=maxsi​​=ti​​{i}，记 f(x,y)=(x[l⋯r],y[l⋯r])f(x,y)=(x[l\cdots r],y[l\cdots r])f(x,y)=(x[l⋯r],y[l⋯r])，L(x,y)L(x,y)L(x,y) 为 xxx 和 yyy 扣掉 f(x,y)f(x,y)f(x,y) 之后剩下的左边的子串（由定义，这两个串是同一个串），R(x,y)R(x,y)R(x,y) 为右边的（同理）。则 (a,b)(a,b)(a,b) 对 (s,t)(s,t)(s,t) 的贡 ...

晚上十点，某商业街僻静的一角，昏黄的路灯下。 我再次于此遇见了名字已被忘记的少女。是否要向她打个招呼，我心想着，那就暂且先叫她 L 吧？ 出乎意料地，首先开口的却是对方。她似乎并未对我的出现感到惊奇，“是你啊。” 我甚至无法辨认她是否抬起了头，又是否在用她清澈却具有洞察力的双眼审视着我。 “其实我更希望你把我忘掉才好，小 L。” 紧张的心情从心脏传递到手指尖，但很快就消失了。“或者直接无视我，像忽略旧礼服上缺失的那颗纽扣一样。” “没有忘记的余地，这是不争的事实。如果我表现得像是遗忘了你这个人，恐怕你也知道，我的内心一定是已经朝着相反的方向疾驰而去了。” 听到这番回答，我一时间竟弄不清自己是该感到欣喜还是沮丧，但那份紧张的确已经蒸发在夏夜温热的空气中了。 这时我才将目光从远处打烊的店铺上移开，转而与少女对视。她的眼神早已停驻多时，等候着我。“怎么…有些透明，你的身体？” 我揉了揉眼睛，疑惑道。 “这就像我们在此相遇一样平常，不是吗？” 她打了个哈欠，说出的话带着慵懒且戏谑的语气。“我在你的记忆中、你在我的记忆中，又何尝不是如此呢？” 我低下头来隐藏自己的面部表情，佯装对她的话无动于衷 ...

前言 唉 思路 题面不太会说人话，先把题面的操作转化成人话。 如果把整个 01 串划分成值相同的连续段，由于经过一次变换后 sis_isi​ 只可能变成自己或 si−1s_{i-1}si−1​，所以只有每个连续段的左端点可能发生变化。设 i(i≥3)i(i\geq 3)i(i≥3) 为某个连续段的左端点，分类讨论 si−2,si−1,si(si−1≠si)s_{i-2},s_{i-1},s_i(s_{i-1}≠s_i)si−2​,si−1​,si​(si−1​​=si​) 的取值，发现只有 101,110101,110101,110 两种情况会导致 sis_isi​ 在一次变换后被翻转。 发现这个规律实际分别等价于，对于每个单个的 000，在一次变换后会变成两个 000；对于每段非单个（≥2\geq 2≥2）的 111，在一次变换后会往右扩展一位。 得到人话后我们考虑整个扩展过程需要的最小时间（即题面里的 kkk）怎么求。模拟一下前面的过程，考虑最左边的一段长度 ≥2\geq 2≥2 的 111，它往右扩展一段时间后会覆盖右边那段 000 产生一个单个的 000，剩下的过程就是它推 ...

今天花了一上午看了《海上钢琴师》(The Legend of 1900)，感觉相当精彩啊，音乐也很牛，不写点东西记录一下实在是说不过去。 看完这部片子我一直在思考一个没有人看完之后不会好奇的问题：为什么 1900 宁愿与弗吉尼亚号一起葬身于爆炸中，也始终不肯回到陆地上生活？ 剧中 1900 本人在轮船爆炸之际给麦克斯的回答是，城市实在是太无限了，甚至看不见一个尽头，就像一台有着无数个琴键的钢琴。并且在这之前有一次麦克斯也问过他为什么不下船，他还说“你们这些陆地上的人总是纠结于为什么”，“他们总是不厌倦旅行，总是在追寻四季如春的远方”。 这些话的共同点在于，陆地上凡人的生活实在是太复杂、太疲于奔命了，尽管陆地上有无数的可能，但这些可能性反而成为了禁锢人们的枷锁。1900 从小就是一个离经叛道的人，领养他的丹尼说 fuck laws，船长发现他弹琴的时候他说 fuck regulations，和那个忘了叫啥的黑人钢琴师决斗之后又说 fuck jazz，船上乐队的领头人让他好好弹琴他一次也没有听过，总是即兴发挥埃及把弹什么弹什么。到陆地上一方面要受规矩束缚，要被形形色色的人和事纷扰，一方面 ...

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