信息学竞赛模板汇总

模板直达链接

• 模板一 — 快速幂
• 模板二 — 二分查找
• 模板三 — 二叉堆
• 模板四 — 快速排序
• 模板五 — 归并排序
• 模板六 — 高精度运算
• 模板七 — 字典树
• 模板八 — 数学
• 模板九 — 并查集
• 模板十 — 邻接表
• 模板十一 — 数状数组
• 模板十二 — 线段树
• 模板十三 — 图论
• 模板十四 — 字符串
• 模板十五 — 几何
• 模板十六 — 组合计数
• 模板十七 — 最长上升子序列
• 模板十八 — 最近公共祖先
• 模板十九 — 二分图
• 待补充。。。

一些注意事项

1. 由数据范围确定算法

题目给定数据范围估计算法（来源：AcWing站长 总结）：

2. 输入输出的选择

超过 $10^5$（十万）的数量级，则用 printf 和 scanf，低于则都可用 cin 和 cout。

但也可以将输入输出同步关闭，则 cin 和 cout 等效与 scanf 和 printf 的效率：

ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

注意： 当解除同步后，切勿将 scanf、printf 和 cin、cout 混用！！！

快读模板：

template<typename T>
void read(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

3. 初始化数组

初始化无穷大数组可以初始化为 0x3f。注意数组为函数的参数的话，memset不可sizoef 数组名，该数组为指针，没有大小，但可以自己设定分配的大小。如下示例：

int arr[n];
memset(arr, 0, sizeof(arr));	//正确

int *arr = new int[n];
memset(arr, 0, sizeof(arr));	//错误
memset(arr, 0, sizeof(int) * n);//正确

4. 进制转换输出

转换

1. 二进制：#include<bitset>，bitset具体使用及参数说明见 传送门

bitset<8>(a)将数字a转换为8位二进制数，

string s;
int x = 20;
bitset<8> bit(x);
s = bit.to_string();	//转换为2进制字符串
cout << s;

2. 8，10，16进制：

char *a = new int[20];
int x = 20;
sprintf(a, "%d", x);	//转换为10进制
sprintf(a, "%o", x);	//转换为8进制
sprintf(a, "%x", x);	//转换为16进制

输出

包含#include<iomanip>头文件：

int x = 20;
cout << x;		//原样输出，10进制
cout << hex << x;	//输出16进制
cout << oct << x;	//输出8进制
cout << bitset<8>(x);	//输出8位2进制

5. to_string

若编译器中不支持 to_string 方法，可以自己写一个模板类完成转换

template<typename T>
string to_string(T s){
    stringstream in;
    in << s;
    return in.str();
}

6. 爆 long long

可以使用 __int128 类型，C++ 11 以上支持。其大致有 39 位数长度。

typedef I128 __int128

若存在该乘法需要模上一个数，则还可以使用 快速乘

LL qmul(LL a, LL b){
    LL s = 0;
    while(b){
        if(b & 1) s = (s + a) % MOD;
        a = (a + a) % MOD;
        b >>= 1;
    }
    return s;
}

7. DEV-CPP 开C++11

具体步骤如下：

1. 点开上方工具栏中的 【工具】按钮
2. 选择【编译选项】
3. 在【编译器】栏目下勾选【编译时加入以下命令】
4. 在对话框中填入 -std=c++11 即可

8. 常用头文件

#include<bits/stdc++.h>

using namespace std;

#define frein freopen("in.txt", "r", stdin)
#define freout freopen("out.txt", "w", stdout)
#define sync ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define gcd __gcd
#define pb push_back
#define fi first
#define se second
#define lowbit(x) (x & -x)
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define pl (p << 1)
#define pr (p << 1 | 1)
typedef pair<int, int> PII;
typedef long long LL;
// head

9. set 自定义排序和去重

typedef pair<double, double> PDD;

//自定义set比较器，只要保证两个相同元素始终返回false即可实现去重效果
class Cmp {
public:
    bool operator() (const PDD &a, const PDD &b) const{
        //两个元素a和b的误差较小，视为相等，返回false
        if(abs(a.fi - b.fi) < eps && abs(a.se - b.se) < eps) return false;
        
        //不相等元素的大小比较，按照斜率较小，再截距较小的优先级
        if(abs(a.fi - b.fi) >= eps) return a.fi < b.fi;
        return a.se < b.se;
    }
};

set<PDD, Cmp> st;