博文
常用查找算法(2009-10-23 13:04:00)
摘要：
//search.h包含了所有的常用查找算法
//使用顺序查找法的查找函数
//seqSearch(const int arr[],int first,int last,int target)
template <typename T>
int seqSearch(const T arr[],int first,int last,const T& target)
{
int i=first;
//扫描下标范围first<=i<last; 测试是否有匹配
//或下标超出范围
while (!(i==last)&&!(arr[i]==target))
i++;
return i; //i是匹配值的下标,或者,如果没有匹配,则i=last
}
//模板函数find_last_of()的实现
template <typename T>
int find_last_of(const T arr[],int first,int last,const T& target)
{
int i=last-1;
//描扫下标范围first<=i<last;测试是否有匹配
//或下标超出范围
while(i>=first&&target!=arr[i])
i--;
if (i<first) return last; //没找到,则返回last
return i;
}
//二分查找算法函数binSearch()的实现
template <typename T>
int binSearch(const T arr[],int first,int last,const T& target)
{
int mid; &......
acm之pku题目分类(2009-10-22 23:59:00)
摘要：
对ACM有兴趣的同学们可以看看
DP:
1011 NTA 简单题
1013 Great Equipment 简单题
1024 Calendar Game 简单题
1027 Human Gene Functions 简单题
1037 Gridland 简单题
1052 Algernon s Noxious Emissions 简单题
1409 Communication System 简单题，但是很容易看错~~~
1425 Crossed Matchings 简单题
1438 Asteroids! 简单题
1459 String Distance and Transform Process 简单题
1462 Team Them Up! 简单题
1556 Heroes Of Might And Magic 简单题，不过背景蛮有意思的……
1520 Duty Free Shop 简单题
ACM 进阶之路（转）(2009-10-22 21:12:00)
摘要：
一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.ACM主要是考算法的,主要时间是花在思考算法上，不是花在写程序与debug上。
下面给个计划你练练：
第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打
出来。
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成树(先写个prim,kruscal要用并查集，不好写)
3.大数（高精度）加减乘除
4.二分查找. (代码可在五行以内)
5.叉乘、判线段相交、然后写个凸包.
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.
8. 调用系统的qsort, 技巧很多，慢慢掌握.
9. 任意进制间的转换
第二阶段：练习复杂一点，但也较常用的算法。
如：
1. 二分图匹配（匈牙利），最小路径覆盖
2. 网络流，最小费用流。
3. 线段树.
4. 并查集。
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp
6.博弈类算法。博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
9. 差分约束系统.
10. 双向广度搜索、A*算法，最小耗散优先.
===========================================================
ACMer必备知识（任重而道远......）
图论
路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
&nbs......
北大poj 1166 The Clocks解题报告源代码(2009-10-22 19:37:00)
摘要：
北大poj 1166 The Clocks解题报告源代码
作者：贾晔
The Clocks
9只钟表排成3*3的方阵，每只钟表只能指向上、下、左、右四个位置
9种作用方式，每种使一些钟表的指针右转90°
使用这9种作用，使得所有钟表都指向正上方 (记为状态0)
求使得总作用次数最少的策略
Sample
Input Data
3*3矩阵，元素为0，1，2或3，分别表示钟表指向上，右，下，左
钟表矩阵的有限性
由于矩阵结构及其元素取值范围相当有限，故可能出现的钟表矩阵也是很有限的，即4^9=262144种
由此有限性可以考虑搜索解法
广度优先搜索
从状态0开始搜索
搜索过程：标记可以通过一次作用达到此状态的所有状态为已搜索，然后搜索新标记的状态。搜索过程中保存使用的作用方式
每个状态用一个32位整数的低18位表示,可将结果存在长度为262144的数组中
启发
广度优先搜索的可行意味着作用次数的相当有限
注意到作用的结果与作用的顺序无关，则显然每种作用最多只需使用3次
于是，问题简化为求解同余方程组
同余方程组
把钟表和作用分别从1到9标号，则同余方程组可写为
[C(i) +∑E(i,j) * M (j)] mod 4= 0 (i=1..9)
其中C(i),M(j),E(i,j)分别表示第i个钟表的初始状态，第j种作用的次数，第j种作用是否拨动第i个钟表
写成矩阵的形式
( C + E M ) mod 4 = 0 (*)
我们所求为M的最小非负解M0=M mod 4
显然，当k足够大时，方程
C + E M’ = 4 * k
广度优先搜索(2009-10-22 18:44:00)
摘要：
广度优先搜索(Breadth-First Search, BFS, 台湾称“横向优先搜寻”)是最简单的图搜索算法之一。广度优先搜索的特点是总是沿已发现与未发现的边界，向外依次扩展。设起始节点为s，则广度优先搜索算法首先会发现与s距离为k的所有结点后，才会发现与s距离为k+1的结点。
广度优先搜索在运行过程中将结点标识为三种状态：
白色：未被发现的结点；
灰色：已被发现，但与其相连的结点尚未全部发现的结点（下一轮进行发现的结点，也是发现结点集的边界）；
黑色：已被发现，且与之相连的其他结点也已经发现。
广度优先搜索因为存在单一的起始结点s，因此整个发现过程可以看作是以s为根节点的一棵树，称为广度优先树，广度优先搜索的过程也是建立一棵以s为根的广度优先树的过程。
广度优先树中对每个结点u记录三种信息：
π[u]：广度优先树中u的父结点，意味着u第一次被发现时所通过的上一级结点；
d[u]：u与根节点s的距离，如果是无权图，也是s到u的最短距离；
color[u]：u结点的颜色。
设图G = (V, E)，V是顶点集，E是边集。s是起始节点。
则广度优先搜索(Breadth-First Search, BFS)算法如下：
view sourceprint?
01.// 初始化整个图（除去起始结点s）
02.foreach(Vertex u in V[G] - {s})
03.{
04. u.Color = BFSColor.WHITE;
05. u.D = int.MaxValue;
06. u.π = null;
07.}
08.
09.// 设置起始结点s
10.s.Color = BFSColor.GRAY;
11.s.D = 0;
12.s.π = null;
13.
14.// 初始化一个队列
15.Queue<Vertex> q = new Queue<Vertex>();
16.q.Enqueue......
PKU ACM 1128 ？？？(2009-09-27 20:29:00)
摘要：
1128这道题里面的第二行的帧：
EEEEEE.. ........ ........ ..BBBB.. .C.C....
组合之后为什么会是ECBCBB..这样啊？？？
不是要按照字母序列排序吗？不是ECBBBB.. 吗？？？
......
括号序列(2009-09-26 00:52:00)
摘要：括号序列
【问题描述】
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…， 和序列bl，b2，…， ，如果存在一组下标1≤i1<i2<…< ≤m，使得aj＝ 对一切1≤j≤n成立，那么a1，a2…， 就叫做b1，b2，…， 的子列。
【输入】
输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
【输出】
输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。
【样例】
bracket.in
([()
bracket.out
()[]() {最多的嵌套层数为1，如层数为2时的一种为()[()]}
【算法分析】
对于输入的括号序列字符串，从左向右进行查......