经验贴

20.两个分数求最小公倍数：先得到两个最简的分数，然后用这两个分数的分子的最小公倍数 / 这两个分数的分母的最大公约数。即答案

19.用int开的数组MLE的时候可以考虑题目数据是不是在short的范围内改用short可以缓解。
如果不行则考虑滚动数组节约内存。

18.对字符数组的输入还可以控制从某个位置开始读入，例如：

	char s[22];
	scanf("%s", s + 1);
	//或者 cin >> s + 1;
	//这样读入的时候第一个字符就在s[1]了

17.在正数范围比long long 还要厉害的有unsigned long long....

16.递归中要注意剪枝，因为递归是先由某个状态递归到底。在这个过程中很多值都会算好了。那么在下次递归到需要这个值的时候就可以直接调用了。例如斐波那契数的递归：

int ff[555];//记忆化数组。

int f(int n)
{
	
	if (n == 1 || n == 2) return 1;
	if (ff[n]) return ff[n];
	return ff[n] = f(n - 1) + f(n - 2);

}

15.求一个给定的数组中的最小的两个值的方法：类似求一个最值的遍历，依旧是O(n)，但是一开始的时候要赋值两个数组里的数，核心代码如下：

	int i, j;
	for (i = 0; i < n; ++i) scanf("%d", &L[i]);
	int m1 = 0, m2 = 1;
	if (L[m1] > L[m2]) swap(m1, m2);
	for (i = 2; i < n; ++i)
	{
		if (L[i] < L[m1])
		{
			m2 = m1;
			m1 = i;
		}
		else if (L[i] < L[m2]) m2 = i;
	}

14.对于将题目分解成若干个子问题来循环求解（递归求解）是非常关键的思想，在许多问题中广泛应用（如概率题，汉诺塔）；

13.注意前缀和的使用，例如需要一个数列中各种区间和，那么没有必要两次循环完全遍历暴力累加。。。。可以先一次遍历，计算出sum[i]为前i项和，那么区间[l,r]的和就为sum[r] - sum[l-1];这样便从On^2 优化到 On.

12.杭电扩栈：#pragma comment(linker, "/STACK:1024000000,1024000000")

11.二分法的精髓是灵活的与其他算法融合。刚做了一道有趣的二分查找答案的题目，题目给了一条递推公式，但是每条等式里都有两个未知变量，而用递归调用的话直接爆栈。。所以就用二分查找答案了（传入mid作为其中一个未知变量的知，并通过一次遍历算出某已知量是否相等）即可。

10.一种简单博弈思想：一堆石头，每次只能拿连续的石头，则先手只要一开始就把石头平均分成两堆，就一定能在最后取完石头（每次模仿对手的动作）；那么需要做的就只是判断什么情况石头不能被平均分成两堆。。。

9.对于一些题目需要%m的，就要目测一下会不会溢出，会的话用上同余定理，在中间用上%m;

8. 对于开根号和平方，慎用或考虑用，一是精度问题，二是大数越界问题（可能有帮助）。
另一外一点要注意的他们的参数类型一定要正确，不然会WA，若不对应，一定要用括号()对其强制转换。

7.memset并不是简单的赋值，故记住只能使用-1或0对全数组进行初始化。

6.善用标记数组和-1， 0， 1，
例如vis[i] = 1表示访问过，