主页

题面 原题 题目描述 众所周知，灭霸希望借助宇宙魔方的力量完成他不可告人的计划。 为了能够释放出宇宙魔方的力量，灭霸制造了一个魔方模型进行练习。 魔方模型是一个 N 层，每层 N 行 N 列的立方体。魔方的每一格会储存一定的能量，一开始每格的能量都是0。 灭霸每次可以给魔方的任意一层的 N*N 个格子同时加上 X 点能量（ X 为任意整数），或者整体转动魔方（仅仅是把魔方的底面换成另一面）。若干次操作之后，魔方的一个格子意外损坏了。灭霸希望你计算出损坏的格子原本储存了多少能量。 输入格式 第一行输入一个整数 N 代表魔方的边长。 接下来有 N 块数据，第 i 块代表魔方的第 i 层。 每一块数据有 N 行，每行 N 个整数，第 x 行第 y 个整数代表这一层的第 x 行第 y...

题面 【题目描述】 还记得 NOIP 2012 提高组 Day2 中的借教室吗？时光飞逝，光阴荏苒，两年过去了，曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。 在接受借教室请求的 n 天中，第 i 天剩余的教室为 ai 个。作为大学借教室服务的负责人，你需要完成如下三种操作共 m 次: • 第 l 天到第 r 天，每天被归还 d 个教室 • 询问第 l 天到第 r 天教室个数的平均数 • 询问第 l 天到第 r 天教室个数的方差 【输入格式】 第一行包括两个正整数 n 和 m，其中 n 为借教室的天数，m 为操作次数。 接下来一行，共包含 n 个整数，第 i 个整数表示第i 天剩余教室数目为 ai 个。 接下来 m 行，每行的第一个...

原题 【问题描述】 我仿佛忆起了自己的故乡，因为这些回忆的色彩总是有点朦胧。但我也许只是想到了些其他东西。 这也许不是我那实实在在的故乡，也许是别人的故乡，也许只是我内心的臆想。 但我越过记忆里的水洼，水洼边的城镇，学校，寺庙，我终于到达了故乡的背面。 那里只有一棵老树。 这棵老树是一棵极其特殊的树。 它有n个节点，节点之间是光滑的树枝连接的，树枝一共有n-1条。因为这是一棵树，所以每一对节点之间都是可以通过树枝直接或者间接到达的。 我们给这些节点从1到n标号，一号节点就是根。对于每一根树枝链接的两个节点，我们称到1号节点距离更远的那个节点是另一个节点的孩子（因为孩子节点是从另一个上面长出来 的）。 我们称从一个节点直接或者间接长出来的所有节点（包括其本身）组成了以这个...

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\le m\le n\le {10}^6$。每种字符在字符串 $t$ 中至多出现 $1$ 次。 题解 1.从暴力出发 这题的暴力非常简单，直接枚举左端点 $l$ 然后向右匹配就可以。 这样的复杂度很显然是 $O(n^2)$，可以在这道题拿到 $20...

题面（简化） 不用简化了，这题题面本来就很简短 给定 $k$ 个有 $n$ 个节点的树，对于每个点对 $(i,j),i,j\in [1,n]$ ，请输出在每棵树上的路径经过的点（含端点）的交集大小。 即 $\mathrm{\forall }i,j\in [1,n],pleaseprint:[k\in [1,n],k\in \mathrm{\forall }i\to j]$ 范围：$n,k\le 500,n,k\in N^{\ast };1\le u,v\le 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)$： $\mathrm{\forall }{a}_i\equiv y_j(mod{x}_i),a_i\to a_i+z_j$ 限制：$z_j\in [-1,1],\mathrm{\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$ 个课题组参与其中。在此期间，一共开发了十几条不同...