数据结构 - Page 26

「BZOJ1660」[Usaco2006 Nov] Bad Hair Day 乱发节
Description Input*Line1:牛的数量N。*Lines2..N+1:第i+1是一个整数，表示第i头牛的高度。Output*Line1:一个整数表示c[1]至c[N]的和。SampleInput610374122输入解释:六头牛排成一排，高度依次是10,3,7,4,12,2。SampleOutput53+0+1+0+1=5题解单调栈水题 [crayon-67435a1cc5d41009894564/] ...
02014年4月5日3,438单调栈

NOIP2012借教室
题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天...
42014年4月4日16,557二分法,线段树
「BZOJ1691」[Usaco2007 Dec] 挑剔的美食家
Description与很多奶牛一样，FarmerJohn那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，FarmerJohn不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1<=N<=100,000)头挑剔的奶牛。所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1<=A_i<=1,000,000,000)，并且鲜嫩程度不能低于B_i(1<=B_i<=1,000,000...
02014年4月3日4,920treap
[FJOI2014] 石子合并问题
问题描述有n堆石子，每堆1个，要合并成一堆，规定每次可以任意选两堆合并成新的一堆，两堆中较少的石子数记为该次合并的得分。输入n输出最大得分样例输入7样例输出9O（n）做法[crayon-67435a1cc6c68029701753/]O（nlogn）堆ndsf神犇秒杀[crayon-67435a1cc6c71351124474/] ...
22014年3月31日6,593递推与动规,堆
「BZOJ1572」[Usaco2009 Open] 工作安排Job
DescriptionFarmerJohn有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1~N的N(1<=N<=100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个...
02014年3月30日3,741堆,贪心
「BZOJ1699」[Usaco2007 Jan] Balanced Lineup排队
Description每天,农夫John的N(1<=N<=50,000)头牛总是按同一序列排队.有一天,John决定让一些牛们玩一场飞盘比赛.他准备找一群在对列中为置连续的牛来进行比赛.但是为了避免水平悬殊,牛的身高不应该相差太大.John准备了Q(1<=Q<=180,000)个可能的牛的选择和所有牛的身高(1<=身高<=1,000,000).他想知道每一组里面最高和最低的牛的身高差别.注意:在最大数据上,输入和输出将占用大部分运行时间.Input*第一行:...
12014年3月29日4,290ST表
最大最小差
题目描述现在有N个正整数，每一次去掉其中2个数a和b，然后加入一个数a*b+1，这样最后只剩下一个数p。要求求出最大的p记为maxp，最小的p记为minp，和他们的差K=maxp-minp。编程任务：对于给定的数列，编程计算出它的max,min和K。输入输入（标准输入）：第一行是数列的长度N（不超过2000），以下N行，每行一个正整数（不超过9位）。输出输出（标准输出）：输出一共三行，每行一个整数，依次为max,min,K。样例输入211样例输出22...
02014年3月29日4,009堆,贪心
「BZOJ1724」[Usaco2006 Nov] Fence Repair切割木板
DescriptionFarmerJohn想修理牧场栅栏的某些小段。为此，他需要N(1<=N<=20,000)块特定长度的木板，第i块木板的长度为Li(1<=Li<=50,000)。然后，FJ去买了一块很长的木板，它的长度正好等于所有需要的木板的长度和。接下来的工作，当然是把它锯成需要的长度。FJ忽略所有切割时的损失——你也应当忽略它。FJ郁闷地发现，他并没有锯子来把这块长木板锯开。于是他把这块长木板带到了FarmerDon的农场，想向F...
02014年3月28日5,042堆,贪心
「BZOJ1588」[HNOI2002] 营业额统计
Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理...
32014年3月28日8,524treap,splay,链表
「BZOJ1113」[POI2008] 海报PLA
DescriptionN个矩形,排成一排.现在希望用尽量少的矩形海报Cover住它们.Input第一行给出数字N,代表有N个矩形.N在[1,250000]下面N行,每行给出矩形的长与宽.其值在[1,1000000000]21/2PosteringOutput最少数量的海报数.SampleInput51213222514SampleOutput4题解[crayon-67435a1cc8b2f984515975/] ...
02014年3月27日4,597单调栈
「BZOJ1709」[Usaco2007 Oct] Super Paintball超级弹珠
Description奶牛们最近从著名的奶牛玩具制造商Tycow那里，买了一套仿真版彩弹游戏设备（类乎于真人版CS）。Bessie把她们玩游戏草坪划成了N*N(1<=N<=100)单位的矩阵，同时列出了她的K(1<=K<=100,000)个对手在草地上的位置。然后她拿着这张表来找你，希望你能帮她计算一个数据。在这个游戏中，奶牛可以用一把弹珠枪向8个方向中的任意一个射出子弹。8个方向分别是：正北，正南，正东，正西，以及夹在这4个正方向...
02014年3月26日3,041哈希表
「BZOJ1345」[Baltic2007] 序列问题Sequence
Description对于一个给定的序列a1,…,an，我们对它进行一个操作reduce(i)，该操作将数列中的元素ai和ai+1用一个元素max(ai，ai+1)替代，这样得到一个比原来序列短的新序列。这一操作的代价是max(ai，ai+1)。进行n-1次该操作后，可以得到一个长度为1的序列。我们的任务是计算代价最小的reduce操作步骤，将给定的序列变成长度为1的序列。Input第一行为一个整数n(1<=n<=1,000,000)，表示给定序列的长度。接下来的n行，每行一个...
22014年3月23日4,121单调栈