plussai的博客
plussai · 共 65 篇文章
图的割点tarjan---zoj_1119
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1119 如果将连通图G中的某个点及和这个点相关的边删除后,将使原图不再连通,那么这个点就称为图G的割点或是接合点。如果一个无向图没有割点,则这样的图被称为双连通图。 算法用到了一下两个数组。 dfn:这个点在dfs序列中的位置 low:经过这个点及这个点的所有儿子能追溯到的dfn最小点的dfn值~~ 这样我们发现,如果发现low(儿子)>=dfn(父亲),那么这个父亲就是一个割点。(他的儿子向下找没法重新找到自己的父亲~) 当然这还是不够的,我们发现对于我们搜索的第一个…
2011-10-24 23:00 · 数据结构算法 · 评论(0)
大数计算模板---zoj_3447
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个(如果不足则取出全部)最大的数,计算后放回数集之中。题目结果很大,需要高精度。 #include<stdio.h> #i…
2011-10-24 16:47 · c++基础 · 评论(0)
DP还是搜索?DP的最高境界---zoj_3469
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469 终于然我摸到了一点点DP的最高境界。。。 题目大意:餐馆送外卖,分布在一条直线上,给出N,V,X表示订单数,速度的倒数,餐馆的位置,然后给出叫外卖的位置Xi和Bi,Bi表示等待外卖的人的不满意指数的增长率(每分钟),求一条送外卖的路径,使得所有外卖送到后,所有人的不满意指数之和的最小。 很显然,送货员的路径肯定是左右来回的,DP[i][j][k]表示从位置i到j全部送到并且送货员在最左边k=0或者最右边k=1的代价。那么DP[i][j][0]的子结构很显然是DP…
2011-10-13 23:11 · dp · 评论(0)
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每一层搜索时,如果有需要push到队列中的装态,就给计数器加1,然后下一层搜索时,pop出n…
2011-10-09 17:14 · 数据结构算法 · 评论(0)
基本树形DP---zoj_3201
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201 树形DP,理解了其实很简单,一气呵成!!对于某个节点u,这个节点对于每个子节点都要更新一次,而且在更新时,子节点的信息已经递归的更新完成了。在更新完某一个子节点之后,此时的dp[u]就包含了之前更新的子节点的信息了。(如果之前不知道肯定不知道我在说什么TAT)还要注意的一点就是,针对某个子节点v更新的时候,我们需要的dp[u]是更新v之前的dp值,因此需要逆序更新。。这其实也很好理解。最后分析一下效率,没个子节点更新一次,与边数对应,因此共更新n-1次,没次更新…
2011-09-30 22:03 · dp · 评论(0)
静态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,将 a[i]修改为q. 这题的特点是数据量很大,N<=50000,M<=10000,时限为10S。。。。,一般的思路,查询求第k大,有topk算法,基于排序的是O(NlogN),不排序的随机划分可以达到O(N),对于修改操作O(1),如果操作中大多数为查询操作的话,算法的上届为O(M…
2011-09-29 23:06 · 数据结构算法 · 评论(0)
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
Nim游戏是两个人进行的游戏有如下规则: 1)桌子上有 N 堆石子,游戏者轮流取石子。 2)每次只能从一堆中取出任意数目的石子,但不能不取。 3)取走最后一个石子者胜。 为了求解这一类问题,我们通常要引出SG函数和游戏和的概念 SG函数:对于单一游戏的某一个状态u,sg(u)=mex(sg(v)|从状态u通过游戏的一步到大状态v), 其中,mex(minimal excludant)是定义在整数集合上的操作。它的自变量是任意整数集合,函数值是不属于该集合的最小自然数。 通常来说,当游戏者无法作出行动的时候(无路可走),该状态的sg值为0;sg值为0的状态是必败状态 下面给出SG函数的性质: …
2011-09-23 23:00 · 数据结构算法 · 评论(0)
struct数据对齐与#pragma pack(n)
对struct数据对齐与#pragma pack(n)的理解一直存在误区,这里做一个总结,便于以后记忆。 规则主要有两条: 1.结构,联合或者类的数据成员,第一个放在偏移为0的地方,以后每一个数据成员的对齐,按照#pragma pack指定的数值和这个数据成员的自身长度来定,取较小的那个。 2.对于整体结构的对齐,则按照结构体中最大数据成员和#pragma pack的大小来定,去较小的那个。 以下是测试代码: #include<iostream> using namespace std; struct test { short a; short b; int c; char d; }; #p…
2011-09-14 16:38 · c++基础 · 评论(0)
多重背包--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[i][j]=max(dp[i-1][…
2011-09-14 11:10 · 数据结构算法 · 评论(0)
经典双塔dp---zoj_2059
题目地址: 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.低塔的高度还是低于高塔 对应上述三中情况对应的状态转换是 1)dp[i][j]=max(d…
2011-08-31 22:48 · dp · 评论(0)
模式串匹配---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[k],那next[j]和s[i]也必然失配,因…
2011-08-31 20:49 · 数据结构算法 · 评论(0)
全排列DP计数---zoj_1217
题目中需要对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; memset(flag,false,sizeof(flag)); fo…
2011-08-30 22:21 · dp · 评论(0)
八数码问题(A*&&双向BFS)---zoj_1217
题目地址: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=217 首先说一下八数码问题的可解性。 1.互换2个非零位置,状态的逆序奇偶性将保持不变。 2.互换0和另一个非零位置,状态的逆序奇偶性将发生颠倒。 3.因此,如果目标状态和起始状态的逆序奇偶性相同,问题可解,否则不可解。所以对于八数码问题的一个目标状态有9!/2种可解状态 逆序奇偶性可以这样来求,将状态转化了数列,然后去掉X位,然后对于每一位,计算在它之前小于它的个数,每一位对应的值之和就是逆序奇偶数。 A*算法具体不多说了,它的精髓在于f(n)=g(n)+h(…
2011-08-30 22:13 · 数据结构算法 · 评论(0)
ac自动机以及它上面的DFA
AC自动机(Aho-Corasick)主要用于多模式串的匹配问题,是前缀匹配搜索的一种方法,和KMP算法的思想类似。 总所周至,KMP算法中的关键next指针利用了模式串本身的性质,在失配时给出了重新匹配的位置。AC自动机中的fail指针也是一样,fail指针的构造关键是找到即是当点匹配串的后缀,又是trie中一个模式串的前缀的最长的字符串。 DFA是确定性有穷自动机,用于正则表达式的匹配,AC自动机可以用来构造DFA,将trie树中的节点看成是DFA中的状态,字符的匹配看成DFA的转化关系,再做一定的处理即可完成 AC自动机本质上来说是一种基于trie树的kmp算法。下面是AC自动机和DF…
2011-08-08 23:04 · 数据结构算法 · 评论(0)
状态压缩dp---zoj_3502
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[i]所对应的所有状态,取最大的一种更新…
2011-08-02 18:09 · dp · 评论(0)