基础数据结构 - Page 9

「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-662d6de8095d0601739373/] ...
02014年4月5日3,277单调栈

[FJOI2014] 石子合并问题
问题描述有n堆石子，每堆1个，要合并成一堆，规定每次可以任意选两堆合并成新的一堆，两堆中较少的石子数记为该次合并的得分。输入n输出最大得分样例输入7样例输出9O（n）做法[crayon-662d6de8099a0380948306/]O（nlogn）堆ndsf神犇秒杀[crayon-662d6de8099aa150328043/] ...
22014年3月31日6,118递推与动规,堆
「BZOJ1572」[Usaco2009 Open] 工作安排Job
DescriptionFarmerJohn有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1~N的N(1<=N<=100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个...
02014年3月30日3,560堆,贪心
最大最小差
题目描述现在有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日3,796堆,贪心
「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日4,798堆,贪心
「BZOJ1588」[HNOI2002] 营业额统计
Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理...
32014年3月28日8,080treap,splay,链表
「BZOJ1113」[POI2008] 海报PLA
DescriptionN个矩形,排成一排.现在希望用尽量少的矩形海报Cover住它们.Input第一行给出数字N,代表有N个矩形.N在[1,250000]下面N行,每行给出矩形的长与宽.其值在[1,1000000000]21/2PosteringOutput最少数量的海报数.SampleInput51213222514SampleOutput4题解[crayon-662d6de80b298912799561/] ...
02014年3月27日4,419单调栈
「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日2,887哈希表
「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日3,958单调栈
「CODEVS3013」单词背诵
题目描述 Description灵梦有n个单词想要背，但她想通过一篇文章中的一段来记住这些单词。文章由m个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。输入描述 InputDescription第1行一个数n，接下来n行每行是一个长度不超过10的字符串，表示一个要背的单词。接着是一...
02014年3月22日3,188哈希表
「BZOJ3098」Hash Killer II
这天天气不错，hzhwcmhf神犇给VFleaKing出了一道题：给你一个长度为N的字符串S，求有多少个不同的长度为L的子串。子串的定义是S[l]、S[l+1]、...S[r]这样连续的一段。两个字符串被认为是不同的当且仅当某个位置上的字符不同。VFleaKing一看觉得这不是Hash的裸题么！于是果断写了哈希+排序。而hzhwcmhf神犇心里自然知道，这题就是后缀数组的height中<L的个数+1，就是后缀自动机上代表的长度区间包含L的结点个数，...
02014年3月6日6,013哈希表
「JoyOI1463」智商问题
背景Background各种数据结构帝~各种小姊妹帝~各种一遍AC帝~ 来吧！描述Description某个同学又有很多小姊妹了他喜欢聪明的小姊妹所以经常用神奇的函数来估算小姊妹的智商他得出了自己所有小姊妹的智商小姊妹的智商都是非负整数但是这个同学看到别的同学的小姊妹也喜欢用神奇的函数估算一下然后看看这个小姊妹在自己的小姊妹群体中排在第几位...(这么邪恶的兴趣...)输入格式InputFormat第一行一个整数N 代表小姊妹的个数第...
32014年3月4日4,194分块