提高组大纲及模板-526互联

https://www.noi.cn/upload/resources/file/2023/03/15/1fa58eac9c412e01ce3c89c761058a43.pdf

数据结构

线性结构

【 5 】双端栈
【 5 】双端队列
【 5 】单调队列
【 6 】优先队列
【 6 】ST 表（Sparse Table）

struct sparseTable
{
	int g(int x, int y)
	{
		return std::max(x, y);
		//需满足 g(x, x) = x
	}
	
	int f[maxn][maxk], log[maxn];
	void init(int n, int a[])
	{
		for (int i = 1; i <= n; i++) log[i] = std::log2(i);
		for (int i = 1; i <= n; i++) f[i][0] = a[i];
		
		int K = std::log2(n);
		for (int j = 1; j <= K; j++)
		{
			for (int i = 1; i <= n; i++)
			{
				if (i + (1 << (j - 1)) > n) f[i][j] = f[i][j - 1];
				else f[i][j] = g(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	
	int query(int l, int r)
	{
		int t = log[r - l + 1];
		return g(f[l][t], f[r - (1 << t) + 1][t]);
	}
} ST;

集合与森林

【 6 】并查集

struct dsu
{
	int fa[maxn], size[maxn];
	void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i, size[i] = 1; }
	int getFath(int u) { return fa[u] == u ? fa[u] : fa[u] = getFath(fa[u]); }
	void follow(int u, int v)
	{
		int fu = getFath(u), fv = getFath(v);
		if (size[fu] < size[fv]) fa[fu] = fv, size[fv] += size[fu];
		else fa[fv] = fu, size[fu] += size[fv];
	}
} D;

【 6 】树的孩子兄弟表示法

特殊树

【 6 】二叉堆
【 6 】树状数组

树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。

【 6 】线段树

struct segmentTree
{
	struct node
	{
		int l, r;
		long long sum, tag;
	}
	T[maxn * 4];
	
	long long build(int p, int l, int r, long long a[])
	{
		T[p].l = l, T[p].r = r, T[p].tag = 0;
		if (l == r) return T[p].sum = a[l];
		else return T[p].sum = build(p << 1, l, (l + r) >> 1, a) + build((p << 1) + 1, ((l + r) >> 1) + 1, r, a);
	}
	
	void downData(int p)
	{
		T[p << 1].sum += T[p].tag * (T[p << 1].r - T[p << 1].l + 1), T[p << 1].tag += T[p].tag;
		T[(p << 1) + 1].sum += T[p].tag * (T[(p << 1) + 1].r - T[(p << 1) + 1].l + 1), T[(p << 1) + 1].tag += T[p].tag;
		T[p].tag = 0;
	}
	
	long long add(int p, int l, int r, long long k)
	{
		if (r < T[p].l || T[p].r < l) return T[p].sum;
		else if (l <= T[p].l && T[p].r <= r) return T[p].tag += k, T[p].sum += k * (T[p].r - T[p].l + 1);
		else return downData(p), T[p].sum = add(p << 1, l, r, k) + add((p << 1) + 1, l, r, k);
	}
	
	long long query(int p, int l, int r)
	{
		if (r < T[p].l || T[p].r < l) return 0;
		else if (l <= T[p].l && T[p].r <= r) return T[p].sum;
		else return downData(p), query(p << 1, l, r) + query((p << 1) + 1, l, r);
	}
}
T;

【 6 】字典树（Trie 树）

struct trie
{
	struct node
	{
		int val;
		node *next[maxm];
		node()
		{
			val = 0;
			for (int i = 1; i <= 26; i++) next[i] = NULL;
		}		
	};

	node root;

	void insert(char s[], int x)
	{
		node *p = &root;
		int n = strlen(s + 1);
		for (int i = 1; i <= n; i++)
		{
			int t = s[i] - 'a' + 1;
			if (p -> next[t] == NULL) p -> next[t] = new node;
			p = p -> next[t];
		}
		p -> val = x;
	}
	
	int find(char s[])
	{
		node *p = &root;
		int n = strlen(s + 1);
		for (int i = 1; i <= n; i++)
		{
			int t = s[i] - 'a' + 1;
			if (p -> next[t] == NULL) return -1;
			else p = p -> next[t];
		}
		if (p -> val == 0) return -1;
		else return p -> val;
	}
}
T;

【 7 】笛卡尔树

不会

【 8 】平衡树：AVL、treap、splay 等

不会

常见图

【 5 】稀疏图
【 6 】偶图（二分图）

struct Hungarian
{
    int road[maxn], link[maxn], dfn;

    bool dfs(int u)
    {
        for (int j = g.Last[u], v; j != 0; j = g.Next[j])
        {
            if (road[v = g.to[j]] == dfn) continue;
            road[v] = dfn;
            if (link[v] == -1 || dfs(link[v]))
            {
                link[v] = u;
                return 1;
            }
        }
        return 0;
    }

    int getMaxMatch(int n)
    {
        int ans = 0;
        dfn = 0;
        for (int i = 1; i <= n; i++) link[i] = road[i] = -1;
        for (int i = 1; i <= n; i++) 
        {
            dfn++;
            ans += dfs(i);
        }
        return ans; 
    }
}
H;

【 6 】欧拉图
【 6 】有向无环图
【 7 】连通图与强连通图
【 7 】双连通图

哈希表

【 5 】数值哈希函数构造
【 6 】字符串哈希函数构造
【 6 】哈希冲突的常用处理方法

算法

复杂度分析

【 6 】时间复杂度分析
【 6 】空间复杂度分析

算法策略

【 6 】离散化

基础算法

【 6 】分治算法

排序算法

【 5 】归并排序
【 5 】快速排序

int a[maxn], b[maxn];
void qsort(int l, int r)
{
	if (l >= r) return;
	int x = a[(l + r) >> 1];
	int i = l, j = r;
	for (int k = l; k <= r; k++)
	{
		if (a[k] < x) b[i++] = a[k];
		if (a[k] > x) b[j--] = a[k];
	}
	for (int k = l; k < i; k++) a[k] = b[k];
	for (int k = i; k <= j; k++) a[k] = x;
	for (int k = r; k > j; k--) a[k] = b[k];
	qsort(l, i - 1), qsort(j + 1, r);
	return;
}

【 6 】堆排序
【 5 】桶排序
【 6 】基数排序

字符串相关算法

【 5 】字符串匹配：KMP 算法

//不会

搜索算法

【 6 】搜索的剪枝优化
【 6 】记忆化搜索
【 7 】启发式搜索
【 7 】双向广度优先搜索
【 7 】迭代加深搜索

图论算法

【 6 】最小生成树：Prim 和 Kruskal 等算法
【 7 】次小生成树

//不会

【 6 】单源最短路：Bellman-Ford、Dijkstra、SPFA 等算法

bool mark[maxn];
long long dis[maxn];

void dijk(int n, int s)
{
	std::priority_queue< std::pair<long long, int> > q;
	for (int i = 1; i <= n; i++) mark[i] = 0;
	for (int i = 1; i <= n; i++) dis[i] = 1LL << 60;
	dis[1] = 0;
	q.push(std::make_pair(0, 1));
	while (!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if (mark[u]) continue;
		mark[u] = 1;
		for (int j = g.Last[u]; j != 0; j = g.Next[j])
		{
			int v = g.to[j];
			if (mark[v] == 1) continue;
			if (dis[v] > dis[u] + g.w[j])
			{
				dis[v] = dis[u] + g.w[j];
				q.push(std::make_pair(-dis[v], v));
			}
		}
	}
	return;
}

【 7 】单源次短路
【 6 】Floyd-Warshall 算法
【 6 】有向无环图的拓扑排序
【 6 】欧拉道路和欧拉回路
【 6 】二分图的判定
【 7 】强连通分量

struct Tarjan
{
	int dfn[maxn], low[maxn];
	int dfnCnt;
	int scc[maxn], sccCnt;
	int stack[maxn], top;
	int mark[maxn];
	
	void dfs(int u)
	{
		if (mark[u] == 1) return;
		stack[++top] = u, mark[u] = 1;
		dfn[u] = low[u] = ++dfnCnt;
		for (int j = g.Last[u]; j != 0; j = g.Next[j])
		{
			int v = g.to[j];
			if (dfn[v] == 0) dfs(v), low[u] = std::min(low[u], low[v]);
			else if (mark[v]) low[u] = std::min(low[u], dfn[v]);
		}
		
		if (dfn[u] == low[u])
		{
			sccCnt++;
			int t;
			do
			{
				t = stack[top--];
				mark[t] = 0;
				scc[t] = sccCnt;
			}
			while(t != u);
		}
		return;
	}
	
	void getScc(int n)
	{
		dfnCnt = sccCnt = top = 0;
		for (int i = 1; i <= n; i++)
		{
			if (dfn[i] == 0)
			{
				dfnCnt = 0;
				dfs(i);
			}
		}
	}
}
T;

【 7 】割点、割边
【 6 】树的重心、直径、DFS 序与欧拉序
【 6 】树上差分、子树和与倍增
【 6 】最近公共祖先

struct LCA
{
	int fa[maxn][maxk], depth[maxn];
	int K;
	
	void init(int n, int root)
	{
		K = std::log2(n);
		dfs(root, 0);
		for (int j = 1; j <= K; j++)
		{
			for (int i = 1; i <= n; i++)
			{
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
	}
	
	void dfs(int u, int fath)
	{
		fa[u][0] = fath, depth[u] = depth[fath] + 1;
		for (int j = g.Last[u]; j != 0; j = g.Next[j])
		{
			int v = g.to[j];
			if (v == fath) continue;
			dfs(v, u);
		}
	}
	
	int getLca(int u, int v)
	{
		if (depth[u] > depth[v]) std::swap(u, v);
		for (int i = K; i >= 0; i--)
		{
			if (depth[fa[v][i]] >= depth[u]) v = fa[v][i];
		}
		if (u == v) return u;
		for (int i = K; i >= 0; i--)
		{
			if (fa[u][i] != fa[v][i])
			{
				u = fa[u][i], v = fa[v][i];
			}
		}
		return fa[u][0];
	}
} L;

动态规划

【 6 】树型动态规划
【 7 】状态压缩动态规划
【 8 】动态规划的常用优化

数学及其他

初等数学

【 5 】代数（高中部分）
【 6 】几何（高中部分）

初等数论

【 5 】同余式
【 7 】欧拉定理和欧拉函数
【 7 】费马小定理
【 7 】威尔逊定理
【 7 】裴蜀定理
【 7 】模运算意义下的逆元
【 7 】扩展欧几里得算法
【 7 】中国剩余定理

离散与组合数学

【 6 】多重集合
【 6 】等价类
【 6 】多重集上的排列
【 6 】多重集上的组合
【 6 】错排列、圆排列
【 6 】鸽巢原理
【 6 】二项式定理
【 7 】容斥原理
【 7 】卡特兰（Catalan）数

线性代数

【 5 】向量与矩阵的概念
【 6 】向量的运算
【 6 】矩阵的初等变换
【 6 】矩阵的运算：加法、减法、乘法与转置

struct martix
{
	int n, m;
	long long mar[maxn][maxn];
	
	martix(int _n, int _m)
	{
		n = _n, m = _m;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				mar[i][j] = 0;
	}
	
	martix operator * (const martix &t) const
	{
		martix ans(n, t.m);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= t.m; j++)
				for (int k = 1; k <= m; k++)
					ans.mar[i][j] = (ans.mar[i][j] + mar[i][k] * t.mar[k][j]) % mod;
		return ans;
	}
	
	martix operator ^ (long long t) const
	{
		martix ans(n, m), x(n, m);
		for (int i = 1; i <= n; i++)
			ans.mar[i][i] = 1;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				x.mar[i][j] = mar[i][j];
		while (t)
		{
			if (t & 1) ans = ans * x;
			x = x * x;
			t >>= 1;
		}
		return ans;
	}
};

【 6 】特殊矩阵的概念：单位阵、三角阵、对称阵和稀疏矩阵
【 7 】高斯消元法