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向上取整数,每个颜色都得小于这个数,不然肯定会有相邻相同的颜色。... 继续阅读 »
ACM

HDU - 1520 Anniversary party(树形dp)

HDU - 1520 Anniversary party(树形dp)
题目的意思是举办一个聚会,给出n个人,每个人有一定的幸福值,给出每个人的上级关系,对于直接的上下级关系,如果下级参加了上级不能参加,如果上级参加了下级不能参加。求举办这次聚会总幸福值最大数。上下级很容易想到树型,所以我们需要找到根节点,设dp[i][0]代表第i个人不去,dp[i][1]代表第i个人去,递推式如下:dp[u][0]+=max(dp[v][0], dp[v][1]);  ... 继续阅读 »
ACM

HDU - 1513 J - Palindrome(LCS,滚动数组优化)

HDU - 1513 J - Palindrome(LCS,滚动数组优化)
题目的意思是给你一个字符串,求插入最少的字符数量使得这个字符串变成回文串。把原字符串和原字符串的反转字符串求个LCS就可以求出保留的字符串,然后用总的减去即可。注意,因为数据比较多,数组会爆ME,所以要用到滚动数组优化。因为LCS只与当前行与上一行数组有关,所以我们需要保留两行的数组即可。代码:StatusAcceptedTime405msMemory1772kBLength665LangC++#... 继续阅读 »
ACM

HDU - 1502 Regular Words(大数dp)

HDU - 1502 Regular Words(大数dp)
题目的意思是给你一个数n,然后有n个A,n个B,n个C,由这些组成一个长为3n的字符串,并且对于这个字符串的每个前缀,Num(A)>=Num(B)>=Num(C)。由于数很大,所以用java写了。递推式是:dp[i][j][[k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1]。dp[i][j][k]代表使用了i个A,j个B,k个C。代码:Statu... 继续阅读 »
ACM

HDU - 1501 Zipper(dp)

HDU - 1501 Zipper(dp)
题目的意思是给你三个字符串,第三个字符串要由前面两个字符串组成,并且前面两个字符串里面的字符顺序要和原来的一样。这个题dp方法有多种。代码1:StatusAcceptedTime46msMemory1892kBLength985LangC++#include <iostream> #include <cstdio> #include <... 继续阅读 »
ACM

HDU - 1466 计算直线的交点数(dp)

HDU - 1466 计算直线的交点数(dp)
题目都是中文的,好懂。一开始当作树形dp去做,wa了,发现有些情况还没考虑到。一下是摘自Even的题解n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,所以n=20的话,最大的交点数是190本题是求有多少种交点数:容易列举出N=1,2,3的情况:00,10,2,3如果已知<N的情况,我们来分析加入第N条直线的情况(这里N=4):1、第四条与其余直线全部... 继续阅读 »
ACM

ACdream - 1063 平衡树(字典树)

ACdream - 1063 平衡树(字典树)
比赛时一看就是字典树,但是当时脑子短路,想了一些莫名其妙的东西就没做了。事后补上~~~(求最大最小也就是把0变1,1变0,变成两个不同的编码而已。因为字典树用的指针版本,如果不在使用后delete就会报ME)代码:StatusAcceptedTime1064msMemory2856kBLength1796LangC++#include <iostream> #include... 继续阅读 »