plussai
- 浏览: 88324 次
- 性别:
- 来自: 杭州
-
最新评论
-
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= ...
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 ...
全排列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自动机（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 ...