模板库

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;
        }
    }
}

原文地址：http://www.cnblogs.com/Zeardoe/p/16824443.html