ACM

CDOJ - 251 导弹拦截(nlogn的LIS)

CDOJ - 251 导弹拦截(nlogn的LIS)
一看就是lis,但是普通的lis是行不通的,而且这里要记录lis路径,可以使用nlogn的lis算法。nlogn的lis算法可以看这里最长上升子序列nlogn在nlogn的算法中得出标记最小结尾数的数组f后,从后面往前面扫一遍即可。题目地址:http://acm.uestc.edu.cn/#/problem/show/251代码:StatusAcceptedTime29msMemory1800kB... 继续阅读 »
ACM

UVALive - 5881 Unique Encryption Keys(思维、暴力、map)

UVALive - 5881 Unique Encryption Keys(思维、暴力、map)
题目的意思是给你从1-M区间的数值,接下来有m次询问,每次询问l、r区间,问个区间是否有相同的数,若没有,则输出OK、否则输出任意一个相同的数。这个题目有点坑。明明说了是any,但是却没有特判,只能找区间内最左边的那个相同的数。还有就是一个空行的问题,坑!但是这题非常有意思,本来我是记录离当前值最近的那个数的位置,但是却WA了,可能是TLE但是显示了WA。然后发现有更好的思维。可以从最右边开始循环... 继续阅读 »
ACM

CDOJ - 1134 男神的约会(状态压缩dp)

CDOJ - 1134 男神的约会(状态压缩dp)
状态压缩dp,利用2进制位数以及或运算保存获得的优惠券的张数。可知当前格子[i,j]只与格子[i-1, j]、格子[i, j-1]有关,所以得状态方程如下:状态方程:dp[i][j][k|1<<data[i][j]]=min(dp[i][j][k], min(dp[i][j-1][k], dp[i-1][j][k])+data[i][j]);题目地址:http://acm.uestc.... 继续阅读 »
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+... 继续阅读 »
ACM

HDU - 5119 Happy Matt Friends(dp,滚动数组)

HDU - 5119 Happy Matt Friends(dp,滚动数组)
题目的意思是从n个数里面选取任意个数进行异或,请问他们组合异或的值大于m的情况有多少种?定义dp[i][j]为前i个人异或得到j的情况,则dp方程为:dp[i%2][j]+=dp[(i-1)%2][j];            //当前这个人不进行异或dp[i%2][j^res[... 继续阅读 »