UOJ Logo root的博客

博客

#剑锋OI#Ⅱ期#任务单#线段树(一)#最近更新20171102

2017-10-29 08:23:48 By root

题目名称 Legacy

题目地址:http://codeforces.com/contest/786/problem/B

三种操作: 1 a b c,在建立权值为c的a->b的单向边 2 a b c d,建立a->[b,c]权值为d的单向边 3 a b c d,建立[b,c]->a权值为d的单向边。 给你一个起点,问你起点到其他点的最短路长度。

题目名称 Preparing for the Contest

题目地址:http://codeforces.com/contest/377/problem/B

有一个学校,有m个bug,有n个大学生,每个大学生的能力值是b[i],bug的能力值是a[i],如果b[i]>=a[j],那么第i个人能够修复j bug现在每个大学生你需要支付c[i]元,支付给他之后,他可以每天修复一个能力值小于等于他能力值的bug你需要尽量少的天数,以及在花费小于s的情况下,修复这些bug问你怎么去做?

题目名称 Day at the Beach

题目地址:http://codeforces.com/contest/599/problem/C

给你n个数,问你最多分成多少块,使得在块内单独排序之后,然后再组合起来的结果和最后排序的结果一样

题目名称 Babaei and Birthday Cake

题目地址:http://www.codeforces.com/contest/629/problem/D

有n个蛋糕,然后第i个蛋糕只能放在地上或者放在体积和编号都比他小的上面 然后问你体积最多能堆多大?

题目名称 敌兵布阵

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1166

题目名称 Just a Hook

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1698

题意:一段线段由n条小线段组成,每次操作把一个区间的小线段变成金银铜之一(金的价值为3,银为2,铜为1),最初可当做全为铜;最后求这条线段的总价值。

评论

yangxiao
##&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;B. Preparing for the Contest &emsp;&emsp;这里马上就会举办世界上最大的程序设计大赛,但是测试系统仍有 **m** 个漏洞。比赛组织者,一所知名的大学,别无选择,只能请学生修复所有的漏洞。大学有 **n** 个能够执行这样工作的学生。学生们意识到自己是组织者的唯一希望,所以他们不想义务劳动:第 **i** 个学生想在他的任务中获得 **c<sub>i</sub>** 个"passes"(不管他的作品的难度)。<br>
root
@yangxiao ####B. Preparing for the Contest   测试系统仍有 m 个漏洞。比赛组织者只能请学生修复所有的漏洞。大学有 n 个能够执行这样工作的学生。第 i 个学生想在他的任务中获得 ci 个"passes"(不管他的作品的难度)。  每一个漏洞具有aj的困难度,每一个学生都有他的能力bi 。学生只可以修复复杂度不高于他的能力的漏洞 (bi ≥ aj) ,一天做完。否则,该漏洞将由另一名学生修复。当然,没有一个学生可以在一天中修复多个漏洞。所有漏洞都是独立的,因此可以按任何顺序进行修复,学生们可以同时工作。   该大学希望尽快解决所有错误,但只给了不多于 s 的费用。请给出工作时间表,说明哪个学生应该修复哪个漏洞。
root
输入:第一行包含三个空格隔开的整数:n , m , s(1≤n,m≤10^5,0≤s≤10^9) 分别代表学生的数量,漏洞的数量和最大的费用。 接下来 m 行包含 a1,a1,...,am(1≤ ai ≤10^9 ) 代表漏洞的复杂度。 接下来 n 行b1,b1,...,bm(1≤ bi ≤10^9 ) 代表学生的能力值。 接下来 n 行c1,c1,...,cm(0≤ ci ≤10^9 ) 代表第 i 个学生所需的费用。 输出:如果无法完成任务输出 "NO". 否则,在第一行输出 "YES",下一行输出 m 个空格分隔的整数,第 i 个整数代表解决第 i 个问题学生的编号。要求应尽可能快地修复所有漏洞,且总费用不超过 s。如果有多个答案,可输出任何一个。
root
C. Day at the Beach n 个城堡,编号从1到n,第 i 个城堡的高度为 hi 。城堡并没有按照高度排列,朋友们要重新排序城堡以达到 hi ≤ hi+1 (1 ≤ i ≤ n-1)。   以下方式来给城堡排序:   • 城堡被划分成块——连续的城堡组。因此,从i到j的块将包括城堡 i , i+1 , ... , j 。一块可能只由一座城堡组成。   • 分区选择需满足:每一个城堡只属于一块。  • 每个块与其他块独立排序,即序列 hi , hi+1, ... , hj 排序。   • 分区应满足,每个块排序后,序列 hi 也已被排序。也就是说整个序列的排序是通过块的排序来实现的。   派大星知道,增加块数将简化排序的过程。现在他们请您求出计算满足上述所有要求的分区中,最大可能的块数。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。