BearChild · Blog

工艺 Time Limit: 10 Sec Memory Limit: 128 MB Description 小敏和小燕是一对好朋友。 　　他们正在玩一种神奇的游戏，叫Minecraft。 　　他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。 　　他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。 　　两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。 Input 第一行两个整数n，代表方块的数目。 　　第二行n个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。 Output 一行n个整数，代表最美观工艺品从左到右瑕疵度的值。 Sample Input 10 　10 9 8 7 6 5 4 3 2 1 Sample Output 1 10 9 8 7 6 5 4 3 2 HINT 对于100%的数据，n<=300000 Main idea 给定一个环，问从哪一位往后走开始 ...

弦论 Time Limit: 10 Sec Memory Limit: 256 MB Description 对于一个给定长度为N的字符串，求它的第K小子串是什么。 Input 第一行是一个仅由小写英文字母构成的字符串S。 　　第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。 　　T=1则表示不同位置的相同子串算作多个。K的意义如题所述。 Output 输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1 Sample Input aabc 　0 3 Sample Output aab HINT N<=5*10^5, T<2, K<=10^9 Solution 首先我们先构造一个后缀自动机，然后分类讨论： 1. 如果T=0，点权为1。为什么呢？一个点有一个Right集合，一个Right集合可以表达多个子串 ，然后我们一个点 -> 另外一个点 其实不止一条边，我们每条边涵盖了一个信息，意味着 这个点->(走这条边)->到达了下一个点 通过这条边得到的那个新子串，而这多个新子串构成了一个 新的点。所以一条合法的路径， ...

负环 Time Limit: 100 Sec Memory Limit: 256 MB Description 在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得环上的边权和为负数。保证图中不包含重边和自环。 Input 第1两个整数n, m,表示图的点数和边数。 接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。 Output 仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出0。 Sample Input 3 6 　1 2 -2 　2 1 1 　2 3 -10 　3 2 10 　3 1 -10 　1 3 10 Sample Output 2 HINT 2 <= n <= 300 0 <= m <= n^2 1 <= ui, vi <= n |wi| <= 10^4 Main idea 给定若干单向边，找出点数最小的负环。 Solution 显然直接二分答案，用DfsSPFA限制深搜层数判断是否存在可行负环即可。 ...

骑士游戏 Time Limit: 30 Sec Memory Limit: 256 MB Description 在这个游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻击。 两种攻击方式都会消耗JYY一些体力。 采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽； 而采用法术攻击则可以彻底将一个怪兽杀死。 当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统bug，并不保证这一点）。 游戏世界中一共有N种不同的怪兽，分别由1到N编号，现在1号怪兽入侵村庄了，JYY想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？ Input 第一行包含一个整数N。 接下来N行，每行描述一个怪兽的信息； 其中第i行包含若干个整数，前三个整数为Si，Ki和Ri，表示对于i号怪兽， 普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。 Output 输出一行一个整数，表示最少需要 ...

神秘物质 Time Limit: 10 Sec Memory Limit: 256 MB Description 21ZZ 年，冬。 小诚退休以后， 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器，整天研究各种微观粒子。这 一天， 小诚刚从研究所得到了一块奇异的陨石样本， 便迫不及待地开始观测。 在精密仪器的视野下，构成陨石 的每个原子都无比清晰。 小诚发现， 这些原子排成若干列， 每一列的结构具有高度相似性。于是，他决定对单 独一列原子进行测量和测试。被选中的这列共有 N 个顺序排列的原子。 最初， 第 i 个原子具有能量 Ei。 随着 时间推移和人为测试， 这列原子在观测上会产生两种变化： merge x e 当前第 x 个原子和第 x+1 个原子合并，得到能量为 e 的新原子； insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子。 对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值， 称为区间极差。 因此， 除了观测变化外，小诚还要经常统计这列原子的两类数据： max x y 当前第 x 到第 y ...

PATULJCI Time Limit: 10 Sec Memory Limit: 259 MB Description Input 第一行两个整数n,INF，表示序列长度和ai的上限； 　　第二行有n个数，表示ai； 　　然后有一个整数m，表示询问个数； 　　接下来每行两个l,r，表示询问区间[l,r]中的答案。 Output 输出m行，表示对于每个询问的答案。如果有这个数，则输出“yes”，然后输出数的值；否则输出“no”。 Sample Input 10 3 　　1 2 1 2 1 2 3 2 3 3 　　8 　　1 2 　　1 3 　　1 4 　　1 5 　　2 5 　　2 6 　　6 9 　　7 10 Sample Output no 　　yes 1 　　no 　　yes 1 　　no 　　yes 2 　　no 　　yes 3 HINT 1<=n<=300000 , 1<=m<=10000 , 1<=ai<=10000。 Solution 显然是一个主席树，我们建立一棵主席树然后查询是否存在个数>(l+r-1)/2的即可。 Code ...

传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间 Input 输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By 第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy 第三行是3个整数，分别是P，Q，R Output 输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位 Sample Input 0 0 0 100 　100 0 100 100 　2 2 1 Sample Output 136.60 HINT 对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000 　　1<=P，Q，R<=10 Main idea 给定平面上的两条线段AB,CD，在AB,CD上移动会有一个特别的速 ...

期末考试 Time Limit: 20 Sec Memory Limit: 512 MB Description 有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天 或之前得知所有课程的成绩。 如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生C不愉快度 对于第i门课程，按照原本的计划，会在第bi天公布成绩 有如下两种 操作可以调整公布成绩的时间 1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天 ，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。 2.增加一部分老师负责学科Z，这将导致学科Z的出成绩时间提前一天；每次操作产生B不愉快度。 上面两种操作中的参数X,Y,Z均可任意指定，每种操作均可以执行多次 ，每次执行时都可以重新指定参数。 现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可 Input 第一行三个非负整数A,B,C，描述三种不愉快度，详见【问题描述】； 第二行两个正整数n,m(1≤n,m≤105)，分 ...

画方框 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output 输出一行一个整数，表示 CD 最多可能画了几个方框。 Sample Input 3 　　1 1 1 　　1 0 1 　　1 1 1 Sample Output 9 HINT Main idea 给定一个01矩阵，1表示有标记，询问正方形方框的个数。 Solution 首先，我们先从 维护对角线上的点 这一层面来考虑。 我们先把一个点 能向左向上拓展的最大长度 以及 能向右向下的最长长度 预处理出来。 那么这时候，我们考虑 对于一条对角线上的点 怎么 在O(nlogn)以内 统计出答案。必然要用到某些数据结构。 举个例子，比如这个数据： 　　　　　　1 1 1 1 　　　　　　1 0 0 0 　　　　　　1 0 0 1 　　　　　　1 0 1 1 　　　　我们现在统计中间对角线的答案。 　　　　现在查询第一个点(1,1)，他向右向下拓展长度为 4 。 　　　　就是查询，后面三个点中 可以向左上拓展的长度 (2,2)>=1 (3,3)> ...

粟粟的书架 Time Limit: 30 Sec Memory Limit: 552 MB Description 幸福幼儿园 B29 班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢 Thomas H. Cormen 的文章。 粟粟家中有一个 R行C列 的巨型书架，书架的每一个位置都摆有一本书，上数第 i 行、左数第 j 列摆放的书有Pi,j页厚。 粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。 粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。 不过她发现， 如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第 i 天指定的那个苹果，只要她脚下放置书的总页数之和不低于Hi，就一定能够摘到。 由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。 这个区域是一个矩形，第 i 天给定区域的左上角是上数第 x1i 行的左数第 y1i 本书，右下角是上数第 x2i 行的左数第 y2i 本书。 换句话说，粟粟在这一天，只能在这﹙x2i－x1i＋1 ...