第一次参加ACM协会的活动，接触了一些算法，总结一些。

前缀和

定义：给定一个数组A[1..n]，前缀和数组PrefixSum[1..n]定义为：PrefixSum[i] = A[0]+A[1]+…+A[i-1];
用途：对数据做预处理简化之后的操作，降低时间复杂度。
示例：求两个整数a到b之间的所有数字的各个位数中1出现的次数，代码

尺取法

简介：尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案。
OJ
program

套路

int r, l = 0;
while(1){
	while(当前区间不满足条件&&r<n){
		r++;
		更新区间信息；
	}
	if(当前区间不满足条件){
		break;
	}
	更新ans；
	l++;
	更新区间信息；
}

二分法

简介：顾名思义，二分法采取了二分的思想，因此二分法也具有较为理想的时间复杂度–O(logn)。但是二分法也有自己的要求，首先是数据储存在数组中，链表无法使用，再就是数据必须是有序的。
OJ
program

套路：

void find(){
    int l = max, r = n * max;	//根据具体情况确定两个边界
    while(l < r){
        int mid = (l + r) / 2;
        if(check(mid) == 1){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    printf("%d\n", l);
}

这一段基本是固定的，主要难点就是check函数怎么写。

DFS

简介：深度优先搜索，从当前节点出发；依次访问与该节点相连的节点，按照深度优先的原则，直至找到结果或者判断条件不成立时返回上一层继续往下进行搜索。返回后要做标记，避免重复访问，进行回溯。
OJ
program

BFS

简介：广度优先搜索，经常用于检索最短路径。与队列相互配合使用，注意每次元素入栈后立即标记该元素被访问而不是真正被访问后再标记。路径的记录可以采用一些特殊的方法，目前只会几种简单的，所以不记录了。
OJPOJ - 3414
program

套路

int bfs(int x, int y){
   	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	v[y][x] = 1;
	s[y][x] = 0;
	while(!q.empty()){
	    tp = q.front();
	    q.pop();
	    if(条件满足){
	        return 结果;
	    }else{
	    	遍历所有与该节点相邻的节点，如果满足条件放入队列尾部，并标记已访问
	    }
	}
	return 0;
}