主页

Away From OI(AFO) ，本以为远在天边，却忽然近在眼前 PS：不要关注这个帖子的时间，因为博客搭建得比较晚，所以这篇是后来誊抄过来的 赛前 中午 $12$ 点多出校门时，我还是满怀着热血与激情的。 心想着，这几天这么努力地打模板，背代码，复习原来的程序，应该会在赛场上考出个不错的成绩。 还记得上一次打 $CSP-J$ 复赛，学了不到一年的我拿到了 $80$ 分 的好成绩 。因此这次我定下了一个底线目标：这次打 $S$ 组，成绩必须比上一次打 $J$ 组高。我认为经过一个暑假再加两个月的集训，达成这个小目标应该不难。 事实证明，确实不难。（哭 T1 开考后，$T1(lock)$ 这道大水题的题面我竟然看了整整 $20$ 多分钟。是的，我无法相信这道题有看上去的那么简...

题面（简化） 给定一个长度为 $n$ 的字符串 $s$，要求选择一个长度尽可能短的子串，使得字符串 $t$ （长为 $m$）是它的子序列。输出该子串的左右端点 $l,r$。 在长度最短的前提下使得 $l$ 尽可能小。 字符串 $s$ 与 $t$ 用两个序列表示。 简化后的题面可能难以理解，防一组样例来进一步说明： s : 5 3 5 3 6 6 t : 3 5 6 符合题目要求的子串为 3 5 3 6，输出为：2 4 题目有多组测试，数据范围：$1≤m≤n≤10^6$。每种字符在字符串 $t$ 中至多出现 $1$ 次。 题解 1.从暴力出发 这题的暴力非常简单，直接枚举左端点 $l$ 然后向右匹配就可以。 这样的复杂度很显然是 $O(n^2)$，可以在这道题拿到 $20...

题面（简化） 不用简化了，这题题面本来就很简短 给定 $k$ 个有 $n$ 个节点的树，对于每个点对 $(i,j),i,j\in[1,n]$ ，请输出在每棵树上的路径经过的点（含端点）的交集大小。 即 $\forall i,j\in [1,n],please~print:[k\in [1,n],k\in \forall i\to j]$ 范围：$n,k≤500,n,k\in N^*;1≤u,v≤n$ 题解 在做这题时，想到了11月7号做的题目（Link）。虽然这两道题看似风马牛不相及，但是却使用了一个相同的结论： $x$ 在 $i$ 到 $j$ 的最短路径上的充要条件是：$dis(x,i)+dis(x,j)=dis(i,j)$（结论1）； 这个结论非常显然，但却是下面一切的开...

题面（简化） 给出 $a$ 数组 $(1\sim n)$，$y,x,z$ 数组 $(1\sim t)$，以及两个正整数 $l,r$。要求进行 $t$ 次变换，具体的，对于 $j\in (1,t)$： $\forall a_i\equiv y_j (\bmod~x_i),a_i\to a_i+z_j$ 限制：$z_j\in[-1,1],\forall j\in [1,k]$ 要求输出 $t$ 次变换结束后有多少个 $a_i$ 满足 $a_i\in[l,r]$ ，并从小到大输出符合上述条件的 $a_i$ 的编号 $i$ 题解 1.暴力算法 这道题暴力可以拿整整 $40pts$ ，而且这个暴力没有一点难度，所以是考场上的一个好选择。 直接模拟即可，复杂度 $O(tn)$，19行代码就...

1.背景 紫杉醇（$Taxol$）是从红豆杉属植物中提取得到的天然抗肿瘤药物，其作用机制为促进微管聚合以抑制肿瘤细胞的有丝分裂。它是医药市场上最优秀的天然抗肿瘤药物之一，其国际医药市场需求巨大。$^{[1]}$ 上图是紫杉醇的结构。可以看到，紫杉醇具有高度氧化的 $[6-8-6-4]$ 核心骨架，同时具有 $11$ 个手性中心（其中 $3$ 个为季碳中心）和 $1$ 个桥头双键，其高张力的双环 $[5.3.1]$ 十一烯骨架以及高度的氧化态预示着其合成具有极大的挑战性。$^{[1]}$ 但是，这难不倒人类。 有机合成化学家们从上个世纪八十年代开始探索紫杉醇的全合成。从 $1980$ 年至今，已有 $40$ 余年，超过 $60$ 个课题组参与其中。在此期间，一共开发了十几条不同...

平衡树：YYDS 以下是常见的平衡树/要用平衡树实现的算法： Treap（有旋/无旋） Splay树 WBLT（Weight Balanced Leafy Tree，重量平衡线段树） SBT（Size Balanced Tree，陈启峰树） AVL树 B树 、B+树 笛卡尔树 红黑树 、左偏红黑树 、AA树 替罪羊树 $\to$ K-D Tree（k-Dimension Tree） LT（Leafy Tree，平衡线段树） 2-3树 、2-3-4树 ······ （平衡树能整出的花活真TM多）可见，平衡树在计算机科学中是一种非常重要的数据结构。 其中，在 $NOIP$ 考试范围内的有： Treap（有旋/无旋） Sp...

rope rope 是 C++ STL 中 pb_ds（Policy-Based Data Structures）库 的一个分支，内部构造是一个 块状链表。 实际中，它经常被用于一些需要可持久化数据结构的题目中，用于代替实现繁琐的可持久化平衡树、可持久化线段树（主席树）、可持久化并查集等等，可见它功能之强大。所以，今天我们就来详细探讨一下这个东西，去看看它的实现 、应用以及优劣。（主要是因为没有时间学可持久化数据结构了） 注意：rope 在 c++11 之后开始被支持，因此可以放心在 NOIP 等竞赛中使用。 rope 的引用 引用 rope 需要调用它所在的 <ext/rope> 库： #include <ext/rope> <ext/r...

1. 复役之曙光 2023.11.3 退役纪元第一天 我得知了我的 CSP-S 复赛分数。不出所料，文操打挂的 T1 没有出现奇迹，后面两题也是平淡如清汤，没有给我任何惊喜。 $35$ 分，或许是我的 $OI$ 生涯中最不堪入目的成绩。 我以为我的 $OI$ 之路就要像这次的成绩一样无声地凋零，碾碎在繁忙人生的车辙之下，道路旁的尘埃里。没想到，机会已经悄然来临。 就在那天下午，我的指导老师（cgj）来找了我。然后，我拿到了我们学校唯一一个复活币（教师推荐名额），并将以一个 $C$ 类的身份参加 $NOIP$ 比赛。 但此时，我却犹豫了——$NOIP$ 的比赛日期与期中考试高度重合，二者显然不可兼得。当然，我并没有对期中考试留恋，只是在已经准备好出圈之后对重新入圈的不适。当然...