[综合] HDU Bone Collector II 背包的K优解

算法比较容易想到，每次做背包操作都会产生值的。记录下排序就好了。不过关于排序的问题我倒是wa了很久，本来开个3维数组把所有的解都记录下来，然后排序取出K大的就好了。但是却wa了==没办法，看网上的题解吧。大家的方法和我想的差不多，也是对每个背包维护k个最优值。解法还是网上的，我就不废话了。 就是记录...

[综合] HDU ACboy needs your help 隐藏的分组背包水题

前几天对这题编了码。自己本地都跑不过。罢了，谁叫我不会做呢==。今天被树形DP虐了，没想法了==。回头准备切切这题。分析了一下特点： 总共要学习N天，每门课程学习的天数都有不同的价值。在每门课程中只能选择一个指定的天数来学。 Wait!!!怎么感觉好像分组背包的描述！背包容量为要学习的N天，每门课程...

[综合] HDU 1992 递推= =

这题好玩！对这种图形递推题终于攻破了！哇哈哈哈！ 就是递推找规律！好玩啊~ #include<cstdio> intmain() {intN;__int64f[1001];f[0]=f[1]=1;f[2]=5;for(inti=3;i<=1000;i++){f[i]=f[i-1]...

[综合] POJ 2002 Square 计算几何

一道水题，关键是要敢做.... 枚举两个点，做直线，作为正方形的一条边，然后由一条边可以确定另外的两个点。可以形成两个正方形，再用二分查找找出这两个点是否存在，若存在则方形个数++。最后答案除以4就可以了。时间不怎么好2844ms...等会儿多用几种方法优化一下.... #include<i...

[综合] HDU 2141 二分

下午练习一下二分吧，感觉写得很挫....用A和B两个数组的和作为一个附加数组，求Ai+Bj+Ck=X只需要去搜索A+B的和为X-Ck即可.... #include<iostream> #include<string.h> #include<cstdio> #in...

[综合] POJ 2785 4 Values whose Sum is 0 二分

简单的二分..不过写挫了...4000*4000我算成了16W...丢死人了...交题果断RE,还百思不得其解....后来改掉之后果断TLE了，自认算法没错，难道是函数调用的关系？对比了一下AC程序发现在二分查找的过程中有一个break条件没加...改掉之后ac了。另外发现sort的cmp调用十分的...

[综合] POJ 3122 Pie 二分

没想到上次做这个题恰巧是一年前啊....当年被这题虐了，不知道怎么做，记得自己还佷傻逼的画了个矩阵...还是没有想到做法，上网看了下思路，说是二分，但是码畜还是不会这题啊！！！ 今天做了一下，发现很水==。当年我是有多傻逼啊！！！直接二分半径，找到输出就可以了。果然浮点型的二分和整型的二分还是有不同...

[综合] HDU 2446 Shell Pyramid 二分查找

今天上午终于把最后一题D题水掉了。我的二分也算是ＡＫ了了吧。这题可以说我还是有版权的，嘿嘿~~越来越有意思了！说一下怎么做吧。听说有公式就试着自己推了一下，感觉不错呢。首先我们可以看出 a1=1,a2=3,a3=6.很显而易见的an=(1+n)*n/2;那么Sn怎么求呢？？？Sn=∑an=(1/2)...

[综合] POJ 3974 最长回文 Manacher算法

容斥刷不动啊！！今天十分的邪恶加猥琐的注册了一个小号和大一的孩子们一起做题；也没有要和他们比赛的意思，只是我对算法有很多不熟悉的，所以呢....哎我的号交几个题，小号交几个题。做都做了，不管了。晚上花了一个半小时才看懂的一个算法Manacher,专门用来做回文的....网上其他的人写得佷详细了，我还...

[综合] POJ 1961 HDU 1358 KMP的性质

题目大意：求给出串的每个前缀串的重复次数。例如aabaabaabaab;1.aa中前缀a出现2次。2.aabaab中前缀aab出现2次3.aabaabaab中前缀aab出现3次4.aabaabaabaab中前缀aab出现4次.大概就是这么个意思。这里利用了kmp中的next标记的性质。看看这个字符串...

[综合] POJ 3461 HDU 1686 赤果果的KMP

果断吃果果.... 不解释... #include<iostream> usingnamespacestd;chars[1111111],t[11111]; intnext[11111],lenS,lenT; intcnt; voidsetNext() {intj=0,k=-1;nex...

[综合] HDU 1711 裸KMP

终于会KMP了...哇哈哈哈~ #include<iostream> usingnamespacestd;intT,N,M; intnext[11111]; ints[1111111],t[11111];voidsetNext() {intj=1,k=0;while(j<=M)...

[综合] HDU 3336 KMP+DP

匹配用的KMP，另外+DP存储状态； DP数组f[i]代表当前前缀可以匹配的次数。 f[i]=f[next[i]]+1;为next[i]--i的的前缀的数量。计算总和即可。 #include<iostream> usingnamespacestd;chart[222222]; int...

[综合] HDU 3746 Cyclic Nacklace KMP的性质应用

前面做过类似的题了，所以切出这个来也很简单。 关于KMP的小应用，KMP的next数组的作用就是用来记录前面的串的状态的。 可以用Len-next[Len]得出当前点的循环节。。。 这个还是很好理解的。 好了KMP在切掉POJ的就在此告一段落了。。。。 #include<iostream&g...

[综合] HDU 1251 字典树裸模板

以前也写过字典树，觉得自己写得很不好，很水很弱，虽然也ac了。 网上看了下别人的模板，果断学习之....... #include<iostream> #include<string.h> #include<cstdio> #defineMAX26 usingna...

[综合] HDU 1671 轻轻松松字典树

这题的难度和前一篇的裸模版差不多。题目大意就是看字符串是否是其他字符串的前缀，其实就是在字典树中查看最后一个节点的count数是否为1.若为1，则代表该字符串唯一。若不唯一，则代表该字符串被其他字符串完全包含，不就是前缀么！水过。。。 #include<iostream> #inclu...

[综合] HDU 3065 AC自动机模板题

最后一道模板题。 下面把AC自动机小结一下。请看新文章..... 这题如果只开26的next的数组的话。 在查询大串时，要注意的if(s[i])当不符合条件时，不能浅显的continue,而要把p=root; 不然.....那些在A-Z之外的字符会直接略去，相当于大串中没有A-Z之外的字符，结果可想...

[综合] POJ 2778 AC自动机+矩阵乘法

这题要写的东西很多，以至于我不知道从哪里开始写了==。 总之要正确理解AC自动机中的状态转移。时间比较晚了，早点回去... 我要注意的地方就是正确理解fail指针的作用。在失配时，fail指针如果走向的是一个病毒节点那么改节点的转移也是病毒节点。不能转移！ 另外要注意的就是mod十分的耗时间啊！两次...

[综合] POJ 3233 等比矩阵的前N项和

第二次做这个题了，犹豫再三还是交了，果断秒A，嘿嘿~感觉不错啊~ 下面说一下思路： 对原矩阵A构造一个2n*2n的方阵。E为单位矩阵，0为0矩阵。 |AE| |0E| 这个矩阵的平方为： |A^2A+E| |0E| 右上角的Ａ＋Ｅ就是Ａ^1+A^0就是前两项的和。 通过这个构造矩阵的K次方，右上角的...

[综合] POJ 3735 构造矩阵乘法

看来还是要吧这个矩阵乘法理解透啊！ 我的题解大体和网上的一样吧。没有什么可取性。 对于矩阵，我们熟悉的操作有两种，交换与置零。 我们有初始的矩阵T[A,B,C,D]; 交换矩阵为 |1000| [A,B,C,D]X|0010|=>[ACBD] |0100| |0001| 置零矩阵为 |100...