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

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[... 继续阅读 »
ACM

HDU - 5115 Dire Wolf (区间dp)

HDU - 5115 Dire Wolf (区间dp)
题目的意思是给你n头狼,然后他们自己有a点攻击,附带b点攻击。在每次攻击一头狼时,旁边两条狼会将附带伤害值加到当前狼上。意味着你会受到ai+bi-1+bi+1点攻击伤害。求杀死所有的狼你受到的伤害最小值。比赛的时候觉得dp不好做,因为以前没有接触过区间dp,所以一直拿着贪心在乱搞。区间dp,对区间长度从1到n,进行dp。随着区间长度的增加,所以遍历的次数可以为:n-len+1每次遍历的区间最大值应... 继续阅读 »
ACM

HDU - 5120 Intersection(数学,两圆相交面积)

HDU - 5120 Intersection(数学,两圆相交面积)
题目的意思是给你一个大圆一个小圆,这两个圆组成一个环,然后有两个环处在不同的坐标位置,求这两个环相交的面积。相交面积=S大环∩大环-S大环∩小环*2+S小环∩小环,如下图所示:那么两个环之间相交的面积怎么求呢?如上图,两个圆相交的面积=S扇形OrAB-S三角形OrAB+S扇形ORAB-S三角形ORAB扇形面积怎么求?我们知道两个圆心之间的距离是可以求出来的,R、r都知道,三边都知道那么用余弦定理可... 继续阅读 »
ACM

HDU 5113 Black And White(dfs+剪枝)

HDU 5113 Black And White(dfs+剪枝)
题目意思很好懂,给你一个矩阵,然后给你刚好矩阵这么大小的颜色,颜色有很多种,加起来肯定等于矩阵大小。问能否放置颜色使得相邻颜色之间没有相同的颜色。明显的dfs题,但是直接dfs铁定超时,所以就得剪枝,比赛的时候想到了剪一半数量,但是觉得不够就没试,然后发现剪一半能过。。。剪一半,每次dfs之前循环一遍所有颜色数目,剩下的格子数量除以2向上取整数,每个颜色都得小于这个数,不然肯定会有相邻相同的颜色。... 继续阅读 »