博文
读入字符串的一个小技巧(2006-08-02 16:04:00)
摘要：以前读入行的时候总用gets或是cin.getline，其实scanf也可达到相同的效果。
scanf("%[^\n]",s); 表示读到\n为止和gets同效
也可以scanf("%[^c]",s);表读到c结束，呵呵，一个小Tip ^_^......
Floyd算法应用(2006-07-27 20:48:00)
摘要：Floyd算法的变化应用：
大家应该都知道Floyd在图中的任意两点最短路径的算法中的应用吧。现在我们来看一个Floyd在其它方面的应用……
题目：
Sorting It All Out（zju1060）
问题描述：
若变量 A, B, C, D已排好序,意味着: A < B, B < C,C < D. 本问题中,将给出一组变量间的小于关系，请你判断它们是否能确定一个排好的序列。
输入：
4 6 //变量有４个(大写字母Ａ—xx)，下面紧跟６种关系
A<B
A<C
B<C
C<D
B<D
A<B
3 2 //又一ＴＥＳＴ
A<B
B<A
26 1
A<Z
0 0 //00结束
输出：
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
说明：
第一组：前4个关系式就能确定序列
第二组：前两个关系式中出现矛盾
第三组：不能确定
问题分析：
★ n个元素要是能确定一个全序，任意两个元素间必能比较大小，这样关系总数应该有n-1 + n-2 + n-3 + …+1 = n*(n-1)/2 个。
★ 当关系式能产生n*(n-1)/2 个关系时，序列可确定。(直接排序)
★ 由于关系只有小于，我们可以用邻接矩阵来表示元素之间的小于关系。
★ &......
深度优先搜索(DFS)基础(2006-07-27 20:43:00)
摘要：深度优先搜索(DFS)基础
深度优先搜索(Deep First Search)主要用在回溯，搜索剪枝等类的问题上。
DFS的基本算法思想是：从图中一顶点vi出发，访问它，并进行标记，然后依次搜索vi的每个邻接点vj；若vj没被访问过，则对vj进行访问标记，然后，依次搜索vj的每个邻接点；若vj的邻接点没被访问过，则访问vj 的邻接点，并进行标记……直到图中和vi有通路的所有顶点都被访问。
二叉树的先序遍历是DFS的一种小范围情况:
实线表调用，虚线表返回(回溯)。得到ABDEGCF.
void Preorder(BiTree root)
{
if (root==NULL) return;
else
{
访问根结点；
Preorder(root->Lchild);
Preorder(root->Rchild);
......
等价类与并查集的原理和应用(2006-07-27 20:15:00)
摘要：等价类与并查集的原理和应用
并查集主要解决判断两个元素是否同属一个集合，和把两个不属同一集合的两个元素进行合并的问题。(想想最小生成树中的kruskal算法:关键是判别两个节点是否属同一连通分量，这里并查集可以以很好的时间复杂度解决它，几乎是线性时间！！)
首先要知道关于等价类（就相当于前面说的同属一个集合）的基本性质。
等价类三大性质：（用ＸºＹ表Ｘ与Ｙ等价）
自反性：如ＸºＸ则ＸºＸ；
对称性：如ＸºＹ则ＹºＸ；
传递性：如ＸºＹ且ＹºＺ则ＸºＺ；
等价类应用：
设初始有一集合s={0,1,2,3,4,5,6,7,8,9,10,11}
依次读若干事先定义的等价对
0º4,3º1,6º10,8º9,7º4,6º8,3º5,2º11,11º0.
我们想把每次读入一个等价对后，把等价集合合并起来。
则每读入一个等价对后的集合状态是：（用｛｝表示一个等价集合）
初始 {0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}
0 º 4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11......
广度优先搜索(BFS)的原理和应用(2006-07-27 17:55:00)
摘要：广度优先搜索(BFS)的原理和应用
二叉树中的层序遍历就属于一种BFS(Board First Search)
层序遍历会得到ABCDEFG的层序优先序列(BFS序列)。在层序遍历过程中，可以注意到先访问的节点的孩子节点必然先被访问(如访问了Ａ后访问Ｂ和Ｃ，那么Ｂ的孩子结点一定在Ｃ的孩子结点前被访问――仅针对下一层的孩子而言)。据这个特性，可以用队列来实现这个遍历。
void Layer(bitree *p)
{
queue<node*> Q; //定义一个队列
node *N;
Q.push(*p); //起始点入队
while(!Q.empty())
{
N=Q.front();
Q.pop();
cout<<N->data<<endl;
if(N->lchild!=NULL) //将扩展子结点(仅一层)全都入队
Q.push(N->lchild);
if(N->rchild!=NULL)
Q.push(N->rchild);
}
}
BFS比它更进一步，可以针对图的结构进行BFS遍历
的BFS(从Ｖ１开始)路径是
广搜的一般结构如下：
定义一个队列;
起始点入队；
while(队列不空){
队头结点出队;
若它是所求的目标状态,跳出循环;
否则，将它扩展出的子结点,全都入队;
}
若循环中找到目标,输出结果;
否则输出无解;
它的主要特点是：
n &nb......
一个简单枚举例子(2006-07-27 17:34:00)
摘要：一个简单枚举例子：
题目：
Zero Sum (USACO 36)
问题描述：
给定一个整数N（3=<N<=9).在序列1…N中插入‘＋’，‘－’，‘ ’。按字典序输出所有使得表达式为0的情况。
Sample Input：
7
Sample Output
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-23+4+5+6+7
1-23-45+67
1-2+3+4-5+6-7
1-2-3-4-5+6+7
问题分析：
v 在1..N中插入‘＋’，‘－’，‘ ’一共有多少中插法？
考虑最坏情况N＝9 时有3^8＝6561 情况。这个解空间比较小，这就意味着我们可以列举所有情况看它是否满足“使得表达式为0”(枚举)。
构造一个变量：
string digital = "11223344556677889";
对变量的操作：
输入n后把digital中2*n – 1 后剔除并在奇数位置按字典序枚举各种插入情况。对每种情况如果表达式值为0。则输出。
源程序：
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
string digital="11223344556677889"; //后面直接对它修改后做为表达式
int n; //规模
int check() //检查字符串表示的表达式是否为0
{
int i;
string tmp;
for(i=0;i<digital.size();i++)
if(digital[i]!=' ')
tmp+=digital[i];
istringst......
开天窗程序(2006-07-27 17:29:00)
摘要：
开天窗(枚举+贪心):
大家的电子辞典应该都有开天窗这样的游戏吧。
现在我们就来讨论一下开天窗的程序。
题目：
Extended Lights Out (zoj 1354)
问题描述：
有一个5行6列的按钮阵列，每个按钮有一盏灯，当它被按下，它和它相邻四个(上下左右)的灯状态改变一次(亮->灭 或灭->亮)。
现在给出了这个阵列的初始亮灭状态，找一种操作让灯全灭。
问题分析：
v 显然按键是顺序无关的，而且最多按一次(按两次等于不按)。
v 最直接的想法：30个按键，每个有两种操作选择，总共要枚举2^30 ＝1073741824种方案。有点时间复杂度概念的人应该都知道这个方法不行……
v 要想使每一行的灯全灭掉，大家想一下，若第一行的灯的状态告诉你了，你怎样让这第一行灯全灭掉？(只要求这一行)。直观地看，把它的第一行的亮灯下面的开关按一下，上面就应该灭了，这样，把第一行的每个亮灯下面的第二行开关按一下，就可以把第一行亮灯全部干掉……
v 远点看，如果你的第二行开关没有全部干掉第一行的灯，第3,4,5行的开关根本对第一行不起作用，你第一行的灯永远也不会全灭……
v 假设你已经搞定第一行了，可第二行不一定全灭，于是要对第三行的开关操作。
v 后面各行的开关操作都受上一行约束……
v 各行操作完后，上面N-1行的灯应该全灭了，判断最后一行是否全灭，如是则就搞定这题了，否则要考虑改变第一行的开关状态继续往下这样……因为只有第一行不受别行约束……
问题的解决：
v 毫无疑问，搜索之。第1行有6个格，每格点或不点，共2^6＝64种状态。
v ......
简单机器人模拟(2006-07-27 17:20:00)
摘要：
简单机器人模拟
题目：(zju1708: Robot Motion)
以矩阵形式给定一张地图和机器人的初始位置。矩阵上每一点的字母代表在这一点机器人的移动方向。如果机器人按图中信息能走出的话输出需要的步数。如果机器人进入某个循环则输出循环前所走的步数和循环的长度。
v Sample Input
v 3 6 5 //地图行列大小和机器人起始点
NEESWE //ＮＥＳＷ分别表示North,East,South,West四个方向
WWWESS
SNWWWW
4 5 1 //另一个TEST
SESWE
EESNW
NWEEN
EWSEN
0 0 0 //000结束输入
v Sample Output
10 step(s) to exit
3 step(s) before a loop of 8 step(s)
源程序如下：
#include<iostream>
using namespace std;
int data[100][100];
int row,col; //地图行列数
void move(int r,int c)
{
int step=1; //记录每个坐标的步数信息(开始是第一步)
bool Noexit=true; //是否已经出界状态(开始肯定没出界^_^)
while(Noexit&&data[r][c]<0) //要判断是否出界还要......
程序设计基本知识结构(2006-07-27 17:08:00)
摘要：基本知识结构:
• 编码
• 文件输入/输出
• 大文件的问题
• 行超长的问题
• 数学运算
• 字符串处理
• 表达式求值/展开
• 英文数字朗读
• 简单程序的模拟执行(文法识别)
• 递归
• 数据结构
• 表示
• 线性结构
• 树: 边列表, 父亲, 遍历结果, “括号表示”
• A(B(H(), I(), J()), C(D(), E(F(), G())))
• 图
• 线性结构基本算法
• 排序
•&n......
一个简单的贪心算法(买牛奶)(2006-07-27 16:53:00)
摘要：
简单的贪心算法
题目：Mixing Milk（usco76）
问题描述：
某商人欲从M个农民那里购买N公斤牛奶。给定整数M，N及若干个农民拥有牛奶的价格和总量。问他最少需要多少钱可以购买N公斤牛奶
v Sample Input:
100 5 //商人要买的牛奶量和总共有的农民数(N,M)
5 20 //以下５行，是每个农民的牛奶单价和他有的牛奶总量
9 40
3 10
8 80
6 30
v Output:
630 //花的最少钱
用贪心法的关键是找到最优的度量标准。既然本题要求花钱最小，我们就可以选择牛奶的价格为度量标准。这是个简单的贪心算法：商人想花最少钱买牛奶，肯定是先挑便宜的买，把最便宜的买光了，还不够量的话，就去买次便宜的……直到数量够了为止。
源程序如下：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct intpair
{
intpair(int a=0,int b=0)
{
price=a;
num=b;
}//intpair
int price,num;//价格和数量
} ;
bool small(intpair v1,intpair v2)//为sort写的小函数
{
return v1.price<v2.price;
}//......