2022.10.25：模板库迁移至cnblogs。
1.离散化
//unordered_map<int, int> b;
int b(int x) {
return lower_bound(a + 1, a + n + 1, x) - a; //返回1~r的数
}
void disc() {
sort(a + 1, a + n + 1);
int r = unique(a + 1, a + n + 1) - a - 1;
// f(i, 1, r) b[a[i]] = i;
return;
}
注：\(a\) 为原数组， unique(a+1,a+n+1) 对 \(a\) 去重，返回最后一个没有去掉的数的下标。
理论上，利用 unordered_map 可以将取出每个数离散化之后的数的时间复杂度优化到 \(O(1)\)，比 lower_bound 优。
但是实验证明， lower_bound 的时间更短。
2.计算程序运行时间
#include <time.h>
int main()
{
clock_t start, finish;
//clock_t为CPU时钟计时单元数
start = clock();
//clock()函数返回此时CPU时钟计时单元数
/*
你的代码
*/
finish = clock();
//clock()函数返回此时CPU时钟计时单元数
cout <<endl<<"the time cost is:" << double(finish - start) / CLOCKS_PER_SEC<<endl;
//finish与start的差值即为程序运行花费的CPU时钟单元数量，再除每秒CPU有多少个时钟单元，即为程序耗时；也可以使用下面一种：
cout << finish-start << "/" << CLOCKS_PER_SEC << " (s)" << endl;
return 0;
}
3.对拍
#include <stdio.h>
#include <stdlib.h>
int main()
{
//For Windows
//对拍时不开文件输入输出
//当然，这段程序也可以改写成批处理的形式
while(1)
{
system("gen.exe > test.in");//数据生成器将生成数据写入输入文件
system("test1.exe < test.in > a.out");//获取程序1输出
system("test2.exe < test.in > b.out");//获取程序2输出
if(system("fc a.out b.out"))
{
//该行语句比对输入输出
//fc返回0时表示输出一致，否则表示有不同处
system("pause");//方便查看不同处
return 0;
//该输入数据已经存放在test.in文件中，可以直接利用进行调试
}
}
}
4.线性筛欧拉函数
const int N = 1000000;
int phi[1000010];
bool comp[1000010];
int prime[100010], cnt;
void euler() {
phi[1] = 1;
f(i, 2, N) {
if(!comp[i]) {
prime[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && prime[j] * i <= N; j++) {
comp[prime[j] * i] = 1;
if(i % prime[j] == 0) {
phi[i * prime[j]] = prime[j] * phi[i];
break;
}
phi[i * prime[j]] = phi[prime[j]] * phi[i];
}
}
}
5.矩阵快速幂（来源：CF185A）
#include<bits/stdc++.h>
using namespace std;
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
const int mod = 1e9 + 7;
ll n;
struct mat {
int n;
ll a[110][110];
}a;
mat mul(mat& a, mat& b) {
mat res;
res.n = a.n;
memset(res.a, 0, sizeof(res.a));
f(i, 1, res.n) {
f(j, 1, res.n) {
f(k, 1, res.n) {
res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
}
}
}
return res;
}
mat qpow(mat a, ll p) {
mat res;
res.n = a.n;
memset(res.a, 0, sizeof(res.a));
res.a[1][1] = 1;
while(p) {
if(p & 1) {
res = mul(res, a);
}
a = mul(a, a);
p >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
a.n = 2;
a.a[1][1] = a.a[2][2] = 3; a.a[1][2] = a.a[2][1] = 1;
mat ans = qpow(a, n);
cout << ans.a[1][1];
return 0;
}
6.ST表（考前必背！）
贴此模板，注意定义域是 \(n\)！
void ST_prework() {
f(i, 1, n) st[i][0] = a[i];
int mx = log(n) / log(2);
f(j, 1, mx) {
int mxi = n - (1 << j) + 1;
f(i, 1, mxi) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int mx = log(r - l + 1) / log(2);
int ans;
ans = max(st[l][mx], st[r - (1 << mx) + 1][mx]);
return ans;
}
7.Dinic（不在提高组纲里面）
注意贴此模板时要注意在 main 函数内把 head memset 为 -1！！！要给 s 和 t 赋初始值！！！
int n, m, s, t;
int head[10010], nxt[200010], to[200010], c[200010], cur[10010];
void add(int u, int v, int w)
{
nxt[cnt] = head[u];
to[cnt] = v;
c[cnt] = w;
head[u] = cnt++;
nxt[cnt] = head[v];
to[cnt] = u;
c[cnt] = 0;
head[v] = cnt++;
}
bool bfs()
{
queue<int> q;
q.push(s);
cur[s] = head[s];
memset(d, -1, sizeof d);
d[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == t)
return 1;
for (int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if (d[v] != -1 || !c[i])
continue;
d[v] = d[u] + 1;
cur[v] = head[v];
q.push(v);
}
}
return 0;
}
int find(int u, int limit)
{
if (u == t)
return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = nxt[i])
{
cur[u] = i;
int v = to[i];
if (d[v] == d[u] + 1 && c[i] > 0)
{
int f = find(v, min(limit - flow, c[i]));
if (!f)
d[v] = -1;
c[i] -= f;
c[i ^ 1] += f;
flow += f;
}
}
return flow;
}
int dinic()
{
int maxflow = 0, flow;
while (bfs())
while (flow = find(s, inf))
maxflow += flow;
return maxflow;
}
8.结构体构造函数
struct edge{
int x,y,z;
edge(){};//这一句话不能少
edge(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
}e[400010];
signed main() {
e[1]=edge(i,n+2,y);
}
9.倍增求 LCA（考前必看）
LCA这样写：dfs处理深度，同时在递归子树之前处理它的所有 k 级祖先！别的顺序就是错的！另外，跳完之后如果两个是一样的直接返回！
void pre_lca(int i) {
int k = log2(dep[i]);
f(j, 1, k) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
}
void dfs(int now, int fa) {
dep[now] = dep[fa] + 1;
anc[now][0] = fa;
pre_lca(now);
f(i, 0, (int)g[now].size() -1 ) {
if(g[now][i] != fa) dfs(g[now][i], now);
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
int nbit = 0;
while(d) {
if(d & 1) x = anc[x][nbit];
d >>= 1;
nbit++;
}
if(x == y) return x;
int k = log2(dep[x]);
for(int i = k; i >= 0; i--){
if(anc[x][i] == anc[y][i]) continue;
else {
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
10.高斯消元
其中 b[n][n + 1] 是增广矩阵，其中第 n+1 列是常数。
这里保证一定有唯一解。
void gauss() {
//消成上三角矩阵
f(i, 1, n) {
//枚举把哪一列的元素求出，也就是哪一行换成上三角形式
//找绝对值最大的元素作为非零元素（可以提升精度）
int maxj = 0;
f(j, i, n) if(fabs(b[j][i]) > fabs(b[maxj][i])) maxj = j;
//交换
f(j, i, n + 1) swap(b[i][j], b[maxj][j]);
//归一
for(int j = n + 1; j >= i; j--) b[i][j] /= b[i][i];
//相减
f(j, i + 1, n) for(int k = n + 1; k >= i; k--) b[j][k] -= b[i][k] * b[j][i];
}
//消成对角矩阵
for(int i = n; i >= 1; i--) {
f(j, 1, i - 1) {
b[j][n + 1] -= b[j][i] * b[i][n + 1];
b[j][i] = 0;
}
}
}