noip知识点（转载）

1、模拟算法（暴力枚举），按照题目的要求，题目怎么说就怎么做，保证时间和正确性即可。
2、搜索与回溯，主要的是DFS（深度优先搜索）和BFS（宽度优先搜索），基本没有直接的暴力搜索。一般是记忆化搜索加剪枝，普及组第三题难度。
3、简单操作：如筛法、前缀和、快速幂、高精度、辗转相除法等，掌握全面即可应对大部分处理数据上的问题。
4、队列（单调队列）、栈、堆、链表等基础数据结构。
5、简单二分和分治（快速排序，归并排序）。
6、贪心，要保证贪心的正确性，如果无法证明也可以用来骗分。
7、数学知识、公式计算，要点在于公式的化简与变形，经过反复操作后也许就能得出重要结论。
8、简单的动态规划，容易推出状态转移方程，要注意初值与计算边界条件。
9、字符串基本操作，插入、删除、查找等。
10、经典例题变形加深：八皇后、马的走法、背包问题等。

————————————————
版权声明：本文为CSDN博主「zsjzliziyang」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。摘自该文章，原文链接：https://blog.csdn.net/zsjzliziyang/article/details/81915298

1、简单搜索

for (int i = 1; i <= n; i ++ )
{
    //...可能存在多重循环
    if ()  // 满足条件
    {

    }
}

2、DFS模板

dfs(int u) // 简单版
{
    if(找到了||走不下去了)
    {
        return；

    }
    开始下一个情况（dfs(u+1)）;

} 

dfs()//参数用来表示状态  
{  
    if(到达终点状态)  
    {  
        ...//根据题意添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        return;  
    if(特殊状态)//剪枝
        return ;
    for(扩展方式)  
    {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记；  
            dfs（）；  
            (还原标记)；  
            //是否还原标记根据题意  
            //如果加上（还原标记）就是 回溯法  
        }  

    }  
}

链接：https://www.acwing.com/blog/content/461/

3、试除法求质数

bool is_prime(int x)
{
	if (x < 2) return false;
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0) 
			return false;
	
	return true;
}

4、朴素法求素数（筛选法）

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i; j <= n; j += i)
            st[j] = true;

5、线性筛选法（算法速度更快）

void get_prime(int x)  //st[x]==0表示质数 
{
	for (int i = 2; i <= n; i ++ )
	{
		if (!st[i]) prime[cnt++] = i;
		for (int j = 0; prime[j] <= n / i; j ++)
			st[prime[j]*i] = true;
			if (i % prime[j] == 0) break;
	}
}

6、一维前缀和

for (int i = 1; i <= n; i ++ )  //s表示前缀和数组， a表示原数组
    s[i] = s[i-1] + a[i];

7、二维前缀和

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j]；
//S[i, j] = 第i行j列格子左上部分所有元素的和
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

8、高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

9、高精度乘法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

10、高精度除法（除数为低精度）

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

11、快速幂

int qmi(int m, int k, int p)
{
	int res = 1 % p,t = m;
	while (k)
	{
		if (k&1) res = res * t % p; // k&1：当k为奇数时，二进制最后一位肯定为1,1&1=1
		t = t * t % p;
		k >>= 1; //k = k >> 1, >> 右移运算符， >>1表示右移一位（0010变成0001)，实际上就是除以2 
	}
	return res; 
}

12、辗转相除法

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

1、 简单搜索