plussai
- 浏览: 88426 次
- 性别:
- 来自: 杭州
-
最新评论
-
zhyawshhz：
顶上！我就是算缺少代码能力型的 ！
百度面试归~~我还是太年轻了。。。。 -
lanjf635241：
...
递归组合算法
文章列表
树形DP--zoj_3506
- 博客分类：
- dp
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3506
题目大意为给定一颗节点带权值的树，和整数k，要求给出一个策略，对这棵树切k刀（对边切，切完保留一部分，丢弃一部分），最后得到的部分的权值和为最大/最小。
f[i][j]为以第i个节点为根，切k刀所得到的最小值。普通dp的想法就是对于某一个节点，如果它为根并保留到最后，那么就在所有的边N中选取k条边，共有C(N,k)种情况，遍历每种情况更新f[i][k].显然这种方法效率是指数级的，会TLE。
那么 ...
二分图G（E,V）将点集合V分成两个部分L,R，使得，图G中所有属于E的边相关联的两个点分别在L和R中。
二分图的一个匹配，即是图G中的边集合，其中，任意两条边都不共用一个顶点，或者说，每个顶点都之多只有一条边和它相关联。
二分图中的最大匹配M，就是求边数最大的边集合。
求二分图匹配有很多算法，这里介绍两种，效率都是O(EV)。
一、将最大匹配问题规约为最大流问题。
构造一个s源点，构造s到左边顶点集合中，每一个顶点的边。构造一个t汇点，构造右边顶点集合中，每一个顶点到t的边。把图中所有的边容量 ...
网络最大流(EK)---zoj_1734
- 博客分类：
- 数据结构算法
网络最大流是图论中的一个典型问题，为了精确的定义最大流问题，先给出下面几个定义。
一、流网络:G（E,V）是一个有向图，对于G中的每一对顶点(u,v)均有一非负的容量c(u,v),如果(u,v)属于E，那么c(u,v)>0,否则c(u,v)=0.
二、流：设G(E,V)是一个流网络，那么G的流是定义在V*V上的一个实值函数f,并且满足一下三个性质:
1)容量限制：f(u,v)<=c(u,v)
2)反对称性：f(u,v)=-f(v,u)
3)流守恒性：简单点说就 ...
trie和前缀检查---zoj_2876
- 博客分类：
- 数据结构算法
trie树是一种多叉树，广泛用于字典检索。如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。额，有点晚了，具体不写了。看代码吧。。
zoj_2876
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
bool res=false;
bool f=false;
class treeNode
{
public:
bool flag;//标志这个节点形成一个词
const static int maxi=10; ...
bitmap是一种广泛使用的数据结构，主要用在数据压缩，索引等方面，它最小单位为位，即01结构。通常情况下逻辑状态为是非二值状态时，bitmap比较常用。
如：腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
显然可以发现，需要判断给出的整数是否存在，是一个二值逻辑，可以用bitmap来解决。我们可以用bitmap来建立一个hashmap，消耗O(N)的预处理时间，去实现O(1)的查询。我们发现40亿刚好可以用unsigned来表示.
如何构造 ...
LAC和RMQ的转化---zoj_3195
- 博客分类：
- 数据结构算法
我擦。。纠结了好久啊,从SF到TLE，先总结2个错误1：(int)(log(1.0*(b-a+1))/log(2.0));注意括号。2：i+(1<<(j-1))位移操作符加上括号，以后一定要记住，不然就是(1+i)<<j-1，这我去。解决掉越界，然后使用c输入输出，使用++i,最后终于AC了
这题其实LCA的tarjan也可以搞，但是tarjan的一个不爽的地方就是Q个查询必须对每一个节点做成类似邻接表的形式，才能保证对于每个查询都是O(1)的消耗，而这题更加恶心的地方就是求3个点的LCA。。。。，所以考虑转化为在线的方法去求解。
...
LCA就不解释了，这里主要再次复习一下LCA的tarjan的离线算法，所谓离线算法，就是把Q个查询先预存储起来，然后等预处理完成后，一次性处理Q个查询。相反所谓在线算法，即使输入一个查询就处理一个查询。今后会补上LCA的ST在线算法。
tarjan我非常崇拜，他解决了图论中很多问题，基本上都是基于DFS的，比如SCC,LCA等，那么tarjan离线如何运行呢，其中要配合并查集来实现。算法从根结点开始DFS，党遍历到某个节点时，为该节点创建一个集合，集合的先祖为该节点，当该节点的子节点被标记为黑时（即该节点的所有子节点都完成处理），子节点所对应的集合和该节点对应的 ...
zoj_2243笛卡尔树的构造，开始被topcoder上的教程吸引去看这题。题目中说这种数据结构叫treap然后就按照treap的insert加上左旋右旋去做了，结果果断TLE。然后网上找了一下关于笛卡尔树的资料，发现了一些问题的端倪。
...
在我们的日常生活中，中缀表达式是最常用的计算表达方式3*（-2+4），这种表达方式的优点就是表达的意义容易理解，一目了然。然而，这种表达方式在计算机识别方面缺十分不方便，其原因主要是，括号对于优先级的限制给编写识别程序造成了不便。
然而后缀表达式对于计算机的解析有这很大的遍历，它不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：21+3*,即(2 + 1) * 3。
那么，如何将中缀表达式转化为后缀表达式呢，从本质上来说，中缀表达式是对于一颗计算树的中序遍历，同理，后缀表达式则是对它的后顺序遍 ...
priority_queue顾名思意是优先队列的意思，在STL内部的实现形式是堆。使用priority_queue的关键就是重载比较函数，去实现不同要求的堆。另外，值得注意的是，二叉堆实现的优先队列是不稳定的，这点要特别注意
在重载优先队列比较函数的时候注意是重载一个类，在类中重写一个（）操作符。
class problem
{
public:
int a,b;
};//定义prblem类型
struct cmp
{
bool operator()(const problem x,const problem y)
{
ret ...
引用：http://blog.csdn.net/rattles/archive/2010/04/21/5510919.aspx
STL 中 sort 函数用法简介
做 ACM 题的时候，排序是一种经常要用到的操作。如果每次都自己写个冒泡之类的
染色问题：在一维坐标轴上（最右端为M），有N个(a,b,c)的染色操作，即把在坐标(a,b)之间的线段染成颜色c.最后来求解一系列问题。如：最长的颜色为C的区间，每种颜色的总长度，每种颜色的区间段数等等。
矩形切割问题：在二维坐标轴上，给出N个矩形，这N个矩形可能相互包含，交叉，分离。最后求解一系列问题。如N个矩形所覆盖的面积，相交的面积等。
先来看染色问题,如果考虑坐标轴的长度为10^9数量级，而染色的操作数为1^3。那么这类问题往往需要先将连续的长度为M的区间离散化为P个染色区间.P往往是N级的。这样就将计算量大大缩短。
...
float,double范围和精度
- 博客分类：
- c++基础
今天遇到一题zoj_1128，数据范围是(0<=x1<x2<=100000;0<=y1<y2<=100000),所有的数不一定是整数，并且最后输出的结果保留2位小数。用float死活wa,最后double过了，痛过之后来总结一下float和double的范围精度。
下面引用：http://www.cnblogs.com/BradMiller/archive/2010/11/25/1887945.html
1. 范围 float和double的范围是由指数的位数来决定的。 float的指数位有8位，而double的指数位有11位，分布如 ...
线段树是一种二叉树的拓展，在线段树每个节点中，存储的是一个区间范围。对于每个节点，它的数据结构一般有，left,right,*lch,*rch，分别描述的是区间的左端点，区间的右端点，指向左子树的指针，指向右子树的指针。对于一个节点的左子树，它的区间范围是[left,(left+right)/2],对于一个节点的右子树，它的区间范围是[(left+right)/2,right]。
利用线段树可以解决很多问题，染色问题就是其中一类，zoj_1610
#include<iostream>
#include<cstdio ...
快速排序是一种高效的非稳定排序，它的基本思路是分支法，在一个序列a[]中找到一个数a[mid]，然后将序列a[]分为3部分a[start]---a[i-1],a[i],a[i+1]---a[end],第一部分的序列中，所有的数都小于a[i],第二部分的序列中，所有的数都大于a[i]。然后递归的对前后两部分进行处理，直到序列完成排序。
那么快速排序的关键步骤就是对序列进行重排。有两种思路1）单向扫描。2）双向扫描。
单向扫描：根据算法导论第二版他的算法流程为：
PARTITION(A, p, r)
1 x ← A[r] // ...