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

传送带 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: 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)> ...

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 ...

Shik and Travel Time Limit: 50 Sec Memory Limit: 512 MB Description 给定一棵n个点的树，保证一个点出度为2/0。 遍历一遍，要求每条边被经过两次，第一次从根出发，最后一次到根结束，在叶子节点之间移动。 移动一次的费用为路径上的边权之和，第一次和最后一次免费，移动的最大费用 最小可以是多少。 Input 第一行一个n，表示点数。 之后两个数x, y，若在第 i 行，表示 i+1 -> x 有一条权值为 y 的边。 Output 输出一个数表示答案。 Sample Input 7 　　1 1 　　1 1 　　2 1 　　2 1 　　3 1 　　3 1 Sample Output 4 HINT 2 < n < 131,072 　　0 ≤ y ≤ 131,072 Solution 问题的本质就是：求一个叶子节点排列，按照排列顺序走，使得两两距离<=K。 　　因为第一天和最后一天不花费，可以第一天从根走到一个叶子，最后一天从某一叶子走回根。 　　我们首先二分答案。 对于子树u维护二元组(a, b)，表示存 ...

粟粟的书架 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 ...

灵魂宝石 Time Limit: 5 Sec Memory Limit: 128 MB Description “作为你们本体的灵魂，为了能够更好的运用魔法，被赋予了既小巧又安全的外形” 　　我们知道，魔法少女的生命被存放于一个称为灵魂宝石（Soul Gem）的装置内。 　　而有时，当灵魂宝石与躯体的距离较远时，魔法少女就无法控制自己的躯体了。 　　在传说中，魔法少女 Abel仅通过推理就得到了这个现象的一般法则，被称为Abel定理： 　　存在宇宙常量 R（是一个非负实数，或正无穷） ，被称为灵魂宝石常量，量纲为空间度量（即：长度）。 　　如果某个魔法少女的灵魂宝石与她的躯体的距离严格超过 R，则她一定无法控制自己的躯体；如果这个距离严格小于 R，则她一定可以控制自己的躯体。 （这里的距离指平面的 Euclid距离。） 　　注意：该定理不能预言距离刚好为 R 的情形。 　　可能存在魔法少女 A 和 B，她们离自己的灵魂宝石的距离都恰好为 R，但是 A可以控制自己的躯体，而 B 不可以。 　　现在这个世界上再也没有魔法少女了，但是我们却对这个宇宙常量感兴趣。 　　我们只能通过之前的世界遗 ...