ACM

AtCoder 074 D - 3N Numbers(STL,优先队列)

AtCoder 074 D - 3N Numbers(STL,优先队列)
题目的意思是,给你一个长为3N的序列,从中删除N个序列,将剩下的2N个序列平分后用前面的区间和减去后面的区间和,求最大的区间差。竟然考的是优先队列,真的是尴尬,还有输出要是%lld或者是cout。我的想法就是至少要在n-2n后面切开这段序列,然后前面一段排序后删除最小数,后面一段排序后删除最大数,一直排序肯定不行,所以用优先队列优化,开始还打算手写链表来着。。。代码:#include &... 继续阅读 »
ACM

2017湘大邀请赛 Partial Sum(贪心)

2017湘大邀请赛 Partial Sum(贪心)
题目的意思是,给你n个连续的序列,有m次操作,每次操作是求某个区间和然后减去c,求能获得的最大值。比赛的时候真的是脑子短路,这么简单的贪心竟然看不出来,每次看到区间就想到dp,然后就不想做了,心痛啊。不过还是有个坑点,就是长整型,湘大的OJ是要用%I64d输出的。代码:#include <iostream> #include <cstdio> #in... 继续阅读 »
ACM

HDU - 3507 Print Article(斜率优化dp)

HDU - 3507 Print Article(斜率优化dp)
题目的意思是有个打印机很老了,现在要打印单词,每个单词打印都有耗费价值,每次打印几个单词都符合题目给出的式子:问,最少的耗费价值。第一次接触概率dp,介绍几篇题解吧,结合起来看更好理解。http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html(针对这个题讲的很容易懂,但是中间有些错误,还请不要纠结,下面评论区有指正。)http:... 继续阅读 »
ACM

HDU - 4734 F(x)(数位dp)

HDU - 4734 F(x)(数位dp)
题目的意思是给你一个数,定义他的重量为:F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + ... + A 2 * 2 + A 1 * 1.(A1-An依次为这个数从低到高的各位数字)现在给出你A,B。求0-B区间内重量不超过A的有多少个。数位dp,很难啊。... 继续阅读 »
ACM

HDU - 6024 Building Shops(背包dp)

HDU - 6024 Building Shops(背包dp)
题目的意思就是给出你n个教室的位置和在这个教室建造糖果屋的价值,这个糖果屋的右边直到下一个糖果屋之前,所有没有建造糖果屋的教室与当前糖果屋的距离也要算在花费之类。也就是说,当前糖果屋的售卖范围要延伸到下一个右边的糖果屋。所以当前糖果屋就有两种情况,建造或者不建造。比赛的时候dp方程是写出来了,但是很尴尬,一直把上一个糖果屋选择为当前最小的那个糖果屋,没考虑到可能上一个糖果屋不建造会有更优的结果。设... 继续阅读 »
ACM

HDU - 6032 Automatic Judge(模拟)

HDU - 6032 Automatic Judge(模拟)
题目倒是很长,给出了一大篇篇幅讲述。大意就是我们平时做题目的时候会有ac、pe、wa、ce、mle之类的提示,然后每次错误都会罚时20分钟,当题目ac之后会把当前时间加上罚时一起计算。给出m个提交记录,请输出这个队ac的题目数量和用时。就是简单模拟,只不过要注意ac过的题再ac是要忽略的,并且这个队伍不会ce。代码:StatusAcceptedMemory1728kBLength911LangC+... 继续阅读 »