主页

题面 原题 【题目描述】 西域商人石染典赶着他的十头驴儿，载着葡萄酒、金银器物往来玉门关外，经年累月经营着他的商队生意。从长安到吐鲁番，绵绵五千里，不说坐飞机，乘火车也是相当熬人的旅程，可石染典得靠他的11路公交车完成 （真的抽象啊） 。因此他必须得考虑他携带商品价值的时令性。 石染典有 n 个商品，每个商品有两个属性 ki 和 bi，表示它在时刻 x 的价值为 ki*x + bi，i 是商品序号。 石染典可以选择不超过 m 个商品，使得存在某个整数时刻 t ≥ 0 时，所有物品的总价值大于等于 S。 假设开始时刻是0，给出 S，求 t 的最小值。 【输入格式】 第一行三个整数n, m, S。 接下来n 行，第i 行两个整数ki、bi，表示每件商品的两个属性。 【输出格...

题面 题目描述（就挺抽象的） $feluamn$ 所在的世界陷入了永恒之夜。本属于光明的他们，如今只能在黑暗中苟且为生。 精灵一族信任与她的善良、勇敢与坚韧，$feluamn$ 得知了划破这黑暗的唯一方法。那就是登上光明之巅！只有 $feluamn$ 这么可爱又善良的女孩子，才有可能成功。 为了拯救这即将凋零的世界，$feluamn$ 整理行囊，准备踏上行程。 $feluamn$ 需要一些魔力晶板来驱散路途的黑暗。现在 $feluamn$ 有 $n$ 块魔力晶板，每块晶板上有 $m$ 个魔力槽，从 $1$ 到 $m$ 标号。一些魔力槽中可能有魔力水晶。$feluamn$ 需要第 $a1,a2,⋯,ak$ 个位置上有魔力水晶，而其他位置没有水晶的魔力晶板。所以她需要取下一些魔力水晶...

题面 原题 题目描述 众所周知，灭霸希望借助宇宙魔方的力量完成他不可告人的计划。 为了能够释放出宇宙魔方的力量，灭霸制造了一个魔方模型进行练习。 魔方模型是一个 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≤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）； 这个结论非常显然，但却是下面一切的开...