- 浏览: 90679 次
- 性别:
- 来自: 杭州
最新评论
-
zhyawshhz:
顶上!我就是算缺少代码能力型的 !
百度面试归~~我还是太年轻了。。。。 -
lanjf635241:
...
递归组合算法
文章列表
图的割点tarjan---zoj_1119
- 博客分类:
- 数据结构算法
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1119
如果将连通图G中的某个点及和这个点相关的边删除后,将使原图不再连通,那么这个点就称为图G的割点或是接合点。如果一个无向图没有割点,则这样的图被称为双连通图。
算法用到了一下两个数组。
dfn:这个点在dfs序列中的位置
low:经过这个点及这个点的所有儿子能追溯到的dfn最小点的dfn值~~
这样我们发现,如果发现low(儿子)>=dfn(父亲),那么这个父亲就是一个割点。 ...
大数计算模板---zoj_3447
- 博客分类:
- c++基础
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4190
很多DP,贪心会涉及高精度,苦于不会JAVA和PY等,只能找了个大数计算的模板,先膜拜在学习。这个代码请参考:
http://www.cppblog.com/patriking/archive/2011/01/09/138137.html
这道题贪心。结果最大的策略就是:不断最小的两个数,计算后放回数集之中;相反的,结果最小的策略就是:不断取出K个(如果不足则取出全部)最大的数,计算后 ...
DP还是搜索?DP的最高境界---zoj_3469
- 博客分类:
- dp
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469
终于然我摸到了一点点DP的最高境界。。。
题目大意:餐馆送外卖,分布在一条直线上,给出N,V,X表示订单数,速度的倒数,餐馆的位置,然后给出叫外卖的位置Xi和Bi,Bi表示等待外卖的人的不满意指数的增长率(每分钟),求一条送外卖的路径,使得所有外卖送到后,所有人的不满意指数之和的最小。
很显然,送货员的路径肯定是左右来回的,DP[i][j][k]表示从位置i到j全部送到并且送货员在最左边k= ...
BFS与双向BFS---zoj_1505
- 博客分类:
- 数据结构算法
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=505
题目大意,跳棋,8*8的棋盘,上有4个棋子,给你一个初始状态给你一个结束状态,问能不能在8步之内从初始状态走到结束状态。
一般的想法,直接暴力DFS,使用状态压缩,状态表偷懒使用set,用时2S
如果使用双向BFS,从开始节点和结束节点同时开始BFS,需要考虑一个细节问题。就是如果控制两端搜索的步数。即要求一个循环内,两个搜索的步数是相同的。
其实很简单,设定一个计数n,BFS每一层搜索 ...
基本树形DP---zoj_3201
- 博客分类:
- dp
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201
树形DP,理解了其实很简单,一气呵成!!对于某个节点u,这个节点对于每个子节点都要更新一次,而且在更新时,子节点的信息已经递归的更新完成了。在更新完某一个子节点之后,此时的dp[u]就包含了之前更新的子节点的信息了。(如果之前不知道肯定不知道我在说什么TAT)还要注意的一点就是,针对某个子节点v更新的时候,我们需要的dp[u]是更新v之前的dp值,因此需要逆序更新。。这其实也很好理解。最后分析一下效率,没个子节点更新一 ...
静态treap+线段树---zoj_2112
- 博客分类:
- 数据结构算法
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112
终于A了这惊天地泣鬼神的一题,练习了线段树和treap。。。此题要求对于N个正整数,给定M个操作,操作有两种1)输入 i j k,要求输出a[i]到a[j]中第k大的数.2)i q ...
Nim游戏是两个人进行的游戏有如下规则:
1)桌子上有 N 堆石子,游戏者轮流取石子。
2)每次只能从一堆中取出任意数目的石子,但不能不取。
3)取走最后一个石子者胜。
为了求解这一类问题,我们通常要引出SG函数和游戏和的概念
SG函数:对于单一游戏的某一个状态u,sg(u)=mex(sg(v)|从状态u通过游戏的一步到大状态v), 其中,mex(minimal excludant)是定义在整数集合上的操作。它的自变量是任意整数集合,函数值是不属于该集合的最小自然数。 通常来说,当游戏者无法作出 ...
对struct数据对齐与#pragma pack(n)的理解一直存在误区,这里做一个总结,便于以后记忆。
规则主要有两条:
1.结构,联合或者类的数据成员,第一个放在偏移为0的地方,以后每一个数据成员的对齐,按照#pragma pack指定的数值和这个数据成员的自身长度来定,取较小的那个。
2.对于整体结构的对齐,则按照结构体中最大数据成员和#pragma pack的大小来定,去较小的那个。
以下是测试代码:
#include<iostream>
using namespace std;
struct test
...
多重背包--zoj_2156
- 博客分类:
- 数据结构算法
首先介绍经典的三种背包问题,0-1背包,完全背包,多重背包。0-1背包是背包问题的最简形式,其他的很多背包问题都可以转化为0-1背包来解决,而0-1背包问题也有非常简单的解法,时间效率为O(V*N),空间消耗为O(V),这里不要小看空间消耗,在数据量很大时,大量的取地址操作也会占用不少的时间消耗。
0-1背包问题可以这样描述:给出N个背包,每个背包的重量为c[i],价值为v[i],在N个背包中选取k个,每个最多选1次,使得总的重量小于V而,总的价值最大。
用DP,以dp[i][j]表述更新第i个背包,总重量为j时的最大价值。显然可以有以下状态 ...
经典双塔dp---zoj_2059
- 博客分类:
- dp
题目地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2059
题目大意是:给定n个立方体,去组成2个塔高度相同的塔,求能组成的双塔的最大高度是多少,立方体不必用完。
状态dp[i][j]为读取第i个立方体,双塔高度差为j时的,较高塔的高度的最大值。
显然dp[i][j]读取第i个立方体时有3中情况:
1)即不放在较高的塔上,也不放在较低的塔上
2)放在较高的塔上
3)放在较低的塔上,分两中情况,1.低塔的高度超过高塔,2.低塔的高度还 ...
模式串匹配---KMP
- 博客分类:
- 数据结构算法
朴素的的模式串匹配算法通常要在向前移动文本指针之后,回溯模式串指针,其效率为O(m*n),而KMP算法则挖掘了一些模式串中的一些信息,来加快匹配的效率。
KMP算法的紧随便是覆盖函数next。当模式串p[j]和文本串s[i]失配时,j指针不是简单的回溯,而是指向next[j]。
覆盖函数next如何定义呢,它本质上是找到即是模式串p的前缀,又是它的后缀的最长字符串,即找到最大的k使得p[0]p[1]....p[k-1]=p[j-k]p[j-k+1]..p[j-1],然后将next[j]赋值为k。当然,这样的赋值并非最优化,注意到如果p[j]=p ...
全排列DP计数---zoj_1217
- 博客分类:
- dp
题目中需要对0-8九个数的全排列计数(字典序),来完成一张对于的HASH表,显然状态空间中共有9!个状态,可以看成一颗树,第一层9个子节点,第二层每个节点8个子节点,第三层每个节点7个子节点,以此类推。
那么对于某中特定的排列,要求它的字典计数,只需求出每一层在该点之后的节点个数乘以该层对应的DP项。。。
int dp[10]={1,1,2,6,24,120,720,5040,40320,362880};
int getHash(int code[9])
{
int sum=0;
bool flag[9];
int k;
mems ...
题目地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=217
首先说一下八数码问题的可解性。
1.互换2个非零位置,状态的逆序奇偶性将保持不变。
2.互换0和另一个非零位置,状态的逆序奇偶性将发生颠倒。
3.因此,如果目标状态和起始状态的逆序奇偶性相同,问题可解,否则不可解。所以对于八数码问题的一个目标状态有9!/2种可解状态
逆序奇偶性可以这样来求,将状态转化了数列,然后去掉X位,然后对于每一位,计算在它之前小于它的个数,每一位对应的值之和就是 ...
ac自动机以及它上面的DFA
- 博客分类:
- 数据结构算法
AC自动机(Aho-Corasick)主要用于多模式串的匹配问题,是前缀匹配搜索的一种方法,和KMP算法的思想类似。
总所周至,KMP算法中的关键next指针利用了模式串本身的性质,在失配时给出了重新匹配的位置。AC自动机中的fail指针也是一样,fail指针的构造关键是找到即是当点匹配串的后缀,又是trie中一个模式串的前缀的最长的字符串。
DFA是确定性有穷自动机,用于正则表达式的匹配,AC自动机可以用来构造DFA,将trie树中的节点看成是DFA中的状态,字符的匹配看成DFA的转化关系,再做一定的处理即可完成
AC自动 ...
状态压缩dp---zoj_3502
- 博客分类:
- dp
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3502
题目大意就是要做n道题目,顺序不定,每一题的AC概率和之前做过的题目有关,给出一张概率表。最后要求给出一个字典排序最小的
题目序列使得AC题目的数量的期望最大。
n道题一共有2^n种状态,dp[i]表示第i中状态下的最大期望。假设i=10111那么dp[i]如何更新呢,显然dp[i]和dp[j]有关,其中
j=00111,10011,10101,10110,dp[j]的状态分别加上第5,3,2,1道题所对应的期望值就是dp ...