`
plussai
  • 浏览: 90679 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论
文章列表
       http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1119        如果将连通图G中的某个点及和这个点相关的边删除后,将使原图不再连通,那么这个点就称为图G的割点或是接合点。如果一个无向图没有割点,则这样的图被称为双连通图。       算法用到了一下两个数组。       dfn:这个点在dfs序列中的位置       low:经过这个点及这个点的所有儿子能追溯到的dfn最小点的dfn值~~      这样我们发现,如果发现low(儿子)>=dfn(父亲),那么这个父亲就是一个割点。 ...
        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个(如果不足则取出全部)最大的数,计算后 ...
       http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469              终于然我摸到了一点点DP的最高境界。。。        题目大意:餐馆送外卖,分布在一条直线上,给出N,V,X表示订单数,速度的倒数,餐馆的位置,然后给出叫外卖的位置Xi和Bi,Bi表示等待外卖的人的不满意指数的增长率(每分钟),求一条送外卖的路径,使得所有外卖送到后,所有人的不满意指数之和的最小。        很显然,送货员的路径肯定是左右来回的,DP[i][j][k]表示从位置i到j全部送到并且送货员在最左边k= ...
           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值,因此需要逆序更新。。这其实也很好理解。最后分析一下效率,没个子节点更新一 ...
       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 ...
         首先介绍经典的三种背包问题,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.低塔的高度还 ...
        朴素的的模式串匹配算法通常要在向前移动文本指针之后,回溯模式串指针,其效率为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 ...
       题目中需要对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自动机(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 ...
Global site tag (gtag.js) - Google Analytics