这个页面主要记录了作者的代码模板,同时也是作者成长的见证。

为了方便使用与迁移,本页面的所有算法均只包含函数,数据结构均使用 $\text{namespace}$ 进行封装。

其中,算法可以直接调用,数据结构请在调用之前添加下面的代码或者在调用时使用NAME :: Things()

using namespace NAME;

My Temple

试机程序

最简单的试机模板,可以用来检测编译器是否可以正常运行。

#include <cstdio>

using namespace std;

int main() {
printf("Hello World");
return 0;
}
#include <cstdio>

using namespace std;

int main() {
int a , b;
scanf("%d%d" , &a , &b);
printf("%d\n" , a + b);
return 0;
}

数论 & 组合数学

Gcd & Lcm

使用欧几里得算法求最大公约数,时间复杂度 $O(\log a)$

int gcd(int a , int b){
return !b ? a : gcd(b , a % b);
}

顺便求一下两个数的最小公倍数,公式为 $lcm(a , b) = \frac{a \times b}{gcd(a , b)}$。

int gcd(int a , int b){
return !b ? a : gcd(b , a % b);
}

int lcm(int a , int b){
return (a * b) / gcd(a , b);
}

Exgcd

使用扩展欧几里得算法求形如 $ax \equiv b \pmod p$ 的不定方程的一组整数解。

时间复杂度与欧几里得相同,也为 $O(\log a)$

void exgcd(int &x , int &y , int a , int b){
if(b == 0){
x = 1 , y = 0;
return ;
}
exgcd(x , y , b , a % b);
int tx = x; x = y , y = tx - a / b * y;
}

乘法逆元

乘法逆元的做法有两种,分别是费马小定理与线性递推。

其中,费马小定理的采用快速幂实现,时间复杂度为 $O(\log p)$ ,适合处理单个数的逆元。

const int HA = 998244353;

long long Pow(long long a , long long b){
if(b == 0) return 1;
if(b == 1) return a % HA;
long long mid = Pow(a , b >> 1) % HA;
if(b & 1) return mid * mid % HA * a % HA;
else return mid * mid % HA;
}

long long get_inv(long long x){
return Pow(x , HA - 2);
}

而线性递推法可以在 $O(n)$ 的时间内处理从 $1$ 到 $n$ 的所有数的逆元,很适合用来预处理逆元。

long long inv[100005] , n , HA;

inv[1] = 1;
for(int i = 2; i <= n; i ++){
inv[i] = (HA - HA / i) * inv[HA % i] % HA;
}

还有一个更好记忆的版本

const int HA = 998244353;

long long inv[100005] , n;

long long Pow(long long a , long long b){
if(b == 0) return 1;
if(b == 1) return a % HA;
long long mid = Pow(a , b >> 1) % HA;
if(b & 1) return mid * mid % HA * a % HA;
else return mid * mid % HA;
}

inv[n] = Pow(n , HA - 2);

for(int i = n; i >= 1; i --){
inv[i - 1] = inv[i] * i % HA;
}

素数判定

可以在$O(\sqrt n)$的时间内判定一个数是否为质数。

bool ISPrime(int x){
for(int i = 2; i * i <= x; i ++){
if(x % i == 0) return 0;
}
return 1;
}

埃氏筛法

可以在 $O(\log \log n)$ 的时间内筛出从 $1$ 到 $n$ 的所有素数。

bool Prime[N];

void IS_Prime(int n){
for(int i = 2; i <= n; i ++){
Prime[i] = true;
}
for(int i = 2; i * i <= n; i ++){
if(Prime[i]){
for(int j = 2 * i; j < n; j += i) Prime[j] = false;
}
}
return ;
}

欧拉筛

可以在严格 $O(n)$ 的时间内筛出从 $1$ 到 $n$ 的所有素数。

int a[N]; 
bool Prime[N];
int num = 0;

void IS_Prime(int n){
for(int i = 2; i <= n; i ++){
Prime[i] = true;
}
for(int i = 2; i * i <= n; i ++){
if(Prime[i]){
a[num ++] = i;
}
for(int j = 1; j <= num && i * a[j] < n; j ++){
Prime[i * a[j]] = false;
if(!(i % a[j])) break;
}
}
return ;
}

组合数的计算

在 $O(k)$ 的时间内求出从 $n$ 个元素中选出 $k$ 种的方案数。

int C(int n , int k){
int ans = 1;
for(int i = 1; i <= k; i ++){
ans = ans * (n - i + 1) / i;
}
return ans;
}

错排公式

在 $O(n)$ 的时间内算出 $n$ 个元素错位排列的方案数

int d[100001] , n , HA;   //d[i] i个元素错位排列的方案数

d[0] = 1 , d[2] = 1;

for(int i = 3; i <= n; i ++){
d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % HA;
}

组合数表

使用 $\text{Pascal}$ 公式在 $O(n^2)$ 的时间内打出组合数表

#define ll long long
#define N 1001

ll c[N][N]; //c[i][j]表示在i个数中选n个数的组合数
void get_num(int n){
c[0][0] = 1;
for(int i = 1; i <= n; i ++){
c[i][0] = 1;
for(int j = 1; j <= i; j ++){
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}

Lucas定理

ll Pow(ll a , ll b){
if(b == 0) return 1;
if(b == 1) return a;
ll mid = Pow(a , b >> 1) % HA;
if(b % 2 == 0){
return mid * mid % HA;
}
else{
return mid * mid % HA * a % HA;
}
}

ll fac[M] , inv[M];

void prepare(){
fac[0] = 1;
rep(i , 1 , HA){
fac[i] = fac[i - 1] * i % HA;
}
}

ll C(ll n , ll m){
if(n == 0 || m > n) return 0;
else if(n == m) return 1;
else{
return 1ll * fac[n] % HA * Pow(fac[m] , HA - 2) % HA * Pow(fac[n - m] , HA - 2) % HA;
}
}

ll Lucas(ll n , ll m , ll HA){
if(!m) return 1;
else{
return 1ll * C(n % HA , m % HA) * Lucas(n / HA , m / HA , HA) % HA;
}
}

数据结构

并查集

用来判断两个元素是否在一个集合中,也可以维护图的联通性。

在采用路径压缩时,查找与合并均为 $O(\log n)$。

使用前不要忘记初始化

int pre[100001];

int find(int root) {
if(pre[root] == root) return root;
else return pre[root] = find(pre[root]);
}

int start(int n) {
for(int i = 1; i <= n; i ++) pre[i] = i;
}

树状数组

用于部分替代线段树的数据结构。

单点查询与单点修改均为 $O(\log n)$

namespace Tree_array{
int tree[N];

int lowbit(int x){
return x & (- x);
}

void add(int x , int val){
for(int i = x; i <= n; i += lowbit(i)){
tree[i] += val;
}
}
int query(int x){
int ans = 0;
for(int i = x; i ; i -= lowbit(i)){
ans += tree[i];
}
return ans;
}
}

另外,树状数组可以用来求逆序对数,时间复杂度也为 $O(\log n)$

#define N 100001

int n , a[N] , b[N];

namespace Tree_array{
int tree[N];

int lowbit(int x){ return x & (-x); }

void add(int x , int val){
for(int i = x; i <= n; i += lowbit(i)){
tree[i] += val;
}
}
long long query(int x){
long long ans = 0;
for(int i = x; i ; i -= lowbit(i)){
ans += tree[i];
}
return ans;
}
}

namespace Solve{
void input(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
b[i] = a[i];
}
sort(b + 1 , b + 1 + n);
ll number = unique(b + 1 , b + 1 + n) - b - 1;
for(int i = 1; i <= number; i ++){
a[i] = lower_bound(b + 1 , b + 1 + n , a[i]) - b;
}
}

long long main(){
long long ans;
input();
for(int i = 1; i <= n; i ++){
Tree_array :: add(a[i] , 1);
ans += i - Tree_array :: query(a[i]);
}
return ans;
}
}

线段树

用来维护一段序列的数据结构,主要利用了分治思想。

缺陷在于要维护的元素必须具有区间可加性。

建树的时间复杂度为 $O(n)$,其他操作均为 $O(\log n)$

//区间加 & 区间查询

namespace Segment_tree{
#define lson(x) x << 1
#define rson(x) x << 1 | 1

ll a[N];

struct Node{
int num , add_tag;
}node[N << 2];

inline void pushup(int x){
node[x].num = node[lson(x)].num + node[rson(x)].num;
}

inline void pushdown(int x , int l , int r){
if(!node[x].add_tag) return ;
int mid = (l + r) >> 1;
node[lson(x)].add_tag += node[x].add_tag;
node[lson(x)].num += node[x].add_tag * (mid - l + 1);
node[rson(x)].add_tag += node[x].add_tag;
node[rson(x)].num += node[x].add_tag * (r - mid);
node[x].add_tag = 0;
}

void build(int x , int l , int r){
if(l == r){
node[x].num = a[l];
return ;
}
int mid = (l + r) >> 1;
build(lson(x) , l , mid);
build(rson(x) , mid + 1 , r);
pushup(x);
}

void range_add(int x , int l , int r , int ql , int qr , int add){
if(ql <= l && r <= qr){
node[x].add_tag += add;
node[x].num += add * (r - l + 1);
return ;
}
pushdown(x , l , r);
int mid = (l + r) >> 1;
if(ql <= mid){
range_add(lson(x) , l , mid , ql , qr , add);
}
if(mid + 1 <= qr){
range_add(rson(x) , mid + 1 , r , ql , qr , add);
}
pushup(x);
}

int range_query(int x , int l , int r , int ql , int qr){
if(ql <= l && r <= qr){
return node[x].num;
}
pushdown(x , l , r);
int ans = 0;
int mid = (l + r) >> 1;
if(ql <= mid){
ans += range_query(lson(x) , l , mid , ql , qr);
}
if(mid + 1 <= qr){
ans += range_query(rson(x) , mid + 1 , r , ql , qr);
}
return ans;
}
}

//区间加 & 区间乘 & 区间查询

namespace Segment_tree{
#define lson(x) x << 1
#define rson(x) x << 1 | 1

int a[N] , HA;

struct Node{
int num;
int add_tag , mul_tag;
}node[N << 2];

I void pushup(int x){
node[x].num = node[lson(x)].num + node[rson(x)].num;
node[x].num %= HA;
}

void build(int x , int l , int r){
node[x].mul_tag = 1;
if(l == r){
node[x].num = a[l] % HA;
return ;
}
int mid = (l + r) >> 1;
build(lson(x) , l , mid);
build(rson(x) , mid + 1 , r);
pushup(x);
}

void pushdown(int x , int l , int r){
int mid = (l + r) >> 1;
if(node[x].mul_tag != 1){
node[lson(x)].mul_tag *= node[x].mul_tag;
node[lson(x)].mul_tag %= HA;
node[lson(x)].add_tag *= node[x].mul_tag;
node[lson(x)].add_tag %= HA;
node[lson(x)].num *= node[x].mul_tag;
node[lson(x)].num %= HA;

node[rson(x)].mul_tag *= node[x].mul_tag;
node[rson(x)].mul_tag %= HA;
node[rson(x)].add_tag *= node[x].mul_tag;
node[rson(x)].add_tag %= HA;
node[rson(x)].num *= node[x].mul_tag;
node[rson(x)].num %= HA;
node[x].mul_tag = 1;
}
if(node[x].add_tag){
node[lson(x)].add_tag += node[x].add_tag;
node[lson(x)].add_tag %= HA;
node[lson(x)].num += node[x].add_tag * (mid - l + 1);
node[lson(x)].num %= HA;

node[rson(x)].add_tag += node[x].add_tag;
node[rson(x)].add_tag %= HA;
node[rson(x)].num += node[x].add_tag * (r - mid);
node[rson(x)].num %= HA;
node[x].add_tag = 0;
}
return ;
}

void range_add(int x , int l , int r , int ql , int qr , int val){
if(ql <= l && r <= qr){
node[x].add_tag += val;
node[x].add_tag %= HA;
node[x].num += val * (r - l + 1);
node[x].num %= HA;
return ;
}
pushdown(x , l , r);
int mid = (l + r) >> 1;
if(ql <= mid){
range_add(lson(x) , l , mid , ql , qr , val);
}
if(mid + 1 <= qr){
range_add(rson(x) , mid + 1 , r , ql , qr , val);
}
pushup(x);
}

void range_mul(int x , int l , int r , int ql , int qr , int val){
if(ql <= l && r <= qr){
node[x].mul_tag *= val;
node[x].mul_tag %= HA;
node[x].add_tag *= val;
node[x].add_tag %= HA;
node[x].num *= val;
node[x].num %= HA;
return ;
}
int mid = (l + r) >> 1;
pushdown(x , l , r);
if(ql <= mid){
range_mul(lson(x) , l , mid , ql , qr , val);
}
if(mid + 1 <= qr){
range_mul(rson(x) , mid + 1 , r , ql , qr ,val);
}
pushup(x);
}

int range_query(int x , int l , int r , int ql , int qr){
if(ql <= l && r <= qr){
return node[x].num % HA;
}
pushdown(x , l , r);
int ans = 0;
int mid = (l + r) >> 1;
if(ql <= mid){
ans += range_query(lson(x) , l ,mid , ql , qr);
ans %= HA;
}
if(mid + 1 <= qr){
ans += range_query(rson(x) , mid + 1 , r , ql , qr);
ans %= HA;
}
return ans % HA;
}

}

Trie树

字典树,时间复杂度为 $O(|s|)$

namespace Trie{
struct Node{
int son[27] , cnt , size;
}node[N];

int tot;

void insert(string s){
int len = s.length() , rt = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a';
if(!node[rt].son[c]){
node[rt].son[c] = ++ tot;
}
rt = node[rt].son[c];
node[rt].size ++;
}
node[rt].cnt ++;
}

int find(string s){
int len = s.length() , rt = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a';
if(!node[rt].son[c]){
return 0;
}
rt = node[rt].son[c];
}
return node[rt].cnt;
}

int get(string s){
int len = s.length() , rt = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a';
if(!node[rt].son[c]){
return 0;
}
rt = node[rt].son[c];
}
return node[rt].size;
}
}

ODT

即珂朵莉树,原理依托于区间推平操作,无稳定复杂度。但在数据随机的情况下具有良好效果。

namespace ODT{
int n , m , s;
int a[N];

struct Node {
int l , r;
mutable int val;
bool operator < (const Node &b) const {
return l < b.l;
}
};

set<Node> S;

void build(int n){
for(int i = 1; i <= n; i ++){
S.insert(Node{i , i , a[i]});
}
}

set<Node>::iterator spilt(int pos){
set<Node>::iterator it = S.lower_bound((Node){pos , pos , -1});
if(it != S.end() && it -> l == pos){
return it;
}
it --;
Node ins = *it;
S.erase(it);
S.insert((Node){ins.l , pos - 1 , ins.val});
return S.insert((Node){pos , ins.r , ins.val}).first;
}

void assign(int l , int r , int val){
set<Node>::iterator R = spilt(r + 1);
set<Node>::iterator L = spilt(l);
S.erase(L , R);
S.insert(Node{l , r , val});
}

void range_add(int l , int r , int val){
set<Node>::iterator R = spilt(r + 1);
set<Node>::iterator L = spilt(l);
for(set<Node>::iterator i = L; i != R; i ++){
i -> val += val;
}
}

int Pow(int a , int n , int HA){
if(n == 0) return 1;
if(n == 1) return a % HA;
int c = Pow(a , n / 2 , HA) % HA;
if(n % 2 == 0)
return (c * c) % HA;
else
return (((c * c) % HA) * a) % HA;
}

int range_pow(int l , int r , int val , int HA){
set<Node>::iterator R = spilt(r + 1);
set<Node>::iterator L = spilt(l);
int ans = 0;
for(set<Node>::iterator i = L; i != R; i ++){
ans += (int)(i -> r - i -> l + 1) * Pow(i -> val , val , HA);
ans %= HA;
}
return ans;
}

int range_query(int l , int r , int k){
#define pairs pair<int , int>

vector<pairs> V;
V.clear();

set<Node>::iterator R = spilt(r + 1);
set<Node>::iterator L = spilt(l);
for(set<Node>::iterator i = L; i != R; i ++){
V.push_back(pairs(i -> val , i -> r - i -> l + 1));
}
sort(V.begin() , V.end());
int sum = 0;
for(vector<pairs> :: iterator i = V.begin(); i != V.end(); i ++){
sum += i -> second;
if(sum >= k){
return i -> first;
}
}
return -1;

#undef pairs
}
}

左偏树

即可并堆,可以快速合并两个优先队列。

插入和弹出的复杂度均为 $O(\log n)$,获取堆顶元素为 $O(1)$,合并为 $O(\log n_1 + \log n_2)$

namespace Left_tree{
#define lson(x) node[x].l
#define rson(x) node[x].r

struct Node{
int pre , dis , far;
int l , r;
}node[N];

int find(int root){
if(node[root].pre == root) return root;
else return node[root].pre = find(node[root].pre);

}

int merge(int x , int y){
if(!x || !y) return x + y ;
if(node[x].dis > node[y].dis) swap(x , y);
node[x].r = merge(rson(x) , y);
node[rson(x)].pre = x;
if(node[lson(x)].far < node[rson(x)].far){
swap(lson(x) , rson(x));
}
node[x].far = node[rson(x)].far + 1;
return x;
}

void pop(int x){
int l = lson(x) , r = rson(x);
node[x].dis = -1;
node[l].pre = l , node[r].pre = r;
node[x].pre = merge(l , r);
}
}

Fhq_treap

非旋Treap,不用旋转的平衡树。

具有插入,删除,查询某个数的排名,寻找排名为 $i$ 的数,查询前驱,后继六种操作,时间复杂度均为 $O(\log n)$,是一种很高效的数据结构。

namespace Treap{
#define lson(x) node[x].l
#define rson(x) node[x].r

int cnt , root;

struct Node{
int dis , size , rd;
int l , r;
Node(int dis = 0) : dis(dis) , size(1) , rd(rand()) , l(0) , r(0) {};
}node[N];

inline void update(int x){
node[x].size = (lson(x) ? node[lson(x)].size : 0) + (rson(x) ? node[rson(x)].size : 0) + 1;
}

void spilt(int n , int k , int &x , int &y){
if(!n) x = y = 0;
else if(node[n].dis >= k){
spilt(lson(n) , k , x , y);
lson(n) = y; update(y = n);
}
else{
spilt(rson(n) , k , x , y);
rson(n) = x; update(x = n);
}
}

int merge(int x , int y){
if(!x || !y) return x + y;
if(node[x].rd < node[y].rd){
rson(x) = merge(rson(x) , y);
update(x); return x;
}
else{
lson(y) = merge(x , lson(y));
update(y); return y;
}
}

void insert(int k){
int x , y;
spilt(root , k , x , y);
node[++ cnt] = Node(k);
root = merge(merge(x , cnt) , y);
}

void remove(int k){
int x , y , z;
spilt(root , k , x , y);
spilt(y , k + 1 , y , z);
y = merge(lson(y) , rson(y));
root = merge(merge(x , y) , z);
}

int rank(int k){
int x , y , ans;
spilt(root , k , x , y);
ans = (x ? node[x].size : 0) + 1;
root = merge(x , y);
return ans;
}

int search(int x , int r){
int rank = (lson(x) ? node[lson(x)].size : 0) + 1;
if(r == rank) return node[x].dis;
else if(r < rank) return search(lson(x) , r);
else return search(rson(x) , r - rank);
}

inline int lower(int k){
int x , y , t;
spilt(root , k , x , y);
t = x;
while(rson(t)) t = rson(t);
root = merge(x , y);
return node[t].dis;
}

inline int upper(int k){
int x , y , t;
spilt(root , k + 1, x , y);
t = y;
while(lson(t)) t = lson(t);
root = merge(x , y);
return node[t].dis;
}

}

图论

Floyd

多源最短路算法,原理为动态规划,时间复杂度为 $O(n^3)$

int n , m;
int f[N][N];

void Floyd(){
for(int k = 1; k <= n; k ++){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
f[i][j] = min(f[i][j] , f[i][k] + f[k][j]);
}
}
}
}

Dijkstra

稳定的多源最短路算法,朴素版本的时间复杂度为 $O(n^2)$,可以通过堆优化降至 $O(n \log(n + m))$

这里只给出堆优化版本

#define PII pair<int , int>

int dis[100001];
bool vis[100001];

void Dijkstra(int sta){
priority_queue<PII , vector<PII> , greater<PII> > Q;

memset(vis , 0 , sizeof(vis));
memset(dis , 0x3f3f3f3f , sizeof(dis));

dis[sta] = 0;
Q.push(make_pair(dis[sta] , sta));
while(!Q.empty()){
int fro = Q.top().second; Q.pop();
if(vis[fro]) continue;
for(int i = head[fro]; i; i = edge[i].last){
int to = edge[i].to;
if(dis[to] > dis[fro] + edge[i].dis){
dis[to] = dis[fro] + edge[i].dis;
Q.push(make_pair(dis[to] , to));
}
}
}
}

SPFA

稳定的多源最短路算法,时间复杂度为 $O(k \times m)$, 其中,$k$ 为每个元素的平均入队次数,一般为 $2$,但可以通过数据构造卡至 $n$

极其不建议考场使用,但在判定负环时具有不可代替的作用。

int dis[100001];
bool vis[100001];

void SPFA(int sta){
queue<int> q;

memset(dis , 1e9 , sizeof(dis));
memset(vis , 0 , sizeof(vis));

dis[sta] = 0;
q.push(sta); vis[sta] = 1;
while(!q.empty()){
int fro = q.front(); q.pop();
vis[fro] = false;
for(int i = hend[fro]; i ; i = edge[i].last){
int to = edge[i].to;
if(dis[to] > dis[fro] + edge[i].dis){
dis[to] = dis[fro] + edge[i].dis;
if(!vis[to]){
vis[to] = 1;
q.push(edge[i].to);
}
}
}
}
}

Kruskal

最小生成树算法,时间复杂度为 $O(n \log n)$

int Kruskal(){
for(int i = 1; i <= n; i ++){
pre[i] = i;
}
int num , ans;
sort(edge + 1 , edge + 1 + m , cmp);
for(int i = 1; i <= m; i ++){
int l = find(edge[i].from); r = find(edge[i].to);
if(l == r) continue;
ans += edge[i].dis;
pre[l] = r; num ++;
if(num == n - 1) break;
}
return ans;
}

Tarjan(割点)

使用 $\text{Tarjan}$ 算法求割点,时间复杂度为 $O(n)$

int dfn[N] , low[N] , cnt;
bool cut[N];

inline void Tarjan(int x , int fa){
dfn[x] = low[x] = ++ cnt;
int child = 0;
for(int i = hend[x]; i ; i = edge[i].last){
int to = edge[i].to;
if(!dfn[to]){
Tarjan(to , fa);
low[x] = min(low[x] , low[to]);
if(low[to] > dfn[x] && x != fa) cut[x] = 1;
}
if(x == fa) child ++;
low[x] = min(low[x] , dfn[to]);
}
if(child >= 2 && x == fa) cut[x] = true;
}

LCA

倍增求最近公共祖先。

预处理为 $O(n \log n)$,每一次查询为 $O(\log n)$

namespace LCA{
int fa[N][22];
int dep[N];

void search(int x){
for(int i = head[x]; i ; i = edge[i].last){
int to = edge[i].to;
if(to == fa[x][0]) continue;
fa[to][0] = x;
dep[to] = dep[x] + 1;
search(to);
}
}

void build(){
for(int j = 1; j <= log2(n); j ++){
for(int i = 1; i <= n; i ++){
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
}

int LCA(int x , int y){
if(dep[x] < dep[y]) swap(x , y);
while(dep[x] > dep[y]){
x = fa[x][(int )log2(dep[x] - dep[y])];
}
if(x == y) return x;
for(int i = log2(dep[x]); i >= 0; i --){
if(dep[x] != dep[y]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
}

Others

竞赛模板

作者常用的考场代码模板,采用宏定义的方式定义了一些常见的代码写法,熟练使用可以大幅度提高编码速度。

#include <bits/stdc++.h>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

int main() {
#ifdef LOCAL
freopen("try.in" , "r" , stdin);
freopen("try1.out" , "w" , stdout);
#endif


return 0;
}

快速读入

比赛用

比赛常用的快读版本,可以读入所有整数类,且在实现快速读入的同时尽量减少了代码量,便于记忆。

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

工业用

工业代码中常用的快速读入,最大化的减少了读入的时间。

namespace FastIO{
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE],*is = ibuf , *its = ibuf;
char obuf[BUFSIZE],*os = obuf , *ot = obuf + BUFSIZE;

inline char getch(){
if(is == its)
its = (is = ibuf) + fread(ibuf , 1 , BUFSIZE , stdin);
return (is == its) ? EOF : *is++;
}

inline int getint(){
int res = 0,neg = 0,ch = getch();
while(!(isdigit(ch) || ch == '-') && ch != EOF)
ch = getch();
if(ch == '-'){
neg = 1;ch = getch();
}
while(isdigit(ch)){
res = (res << 3) + (res << 1)+ (ch - '0');
ch = getch();
}
return neg ? - res : res;
}

inline void flush(){
fwrite(obuf , 1 , os - obuf , stdout);
os = obuf;
}

inline void putch(char ch){
*os ++ = ch;
if(os == ot) flush();
}

inline void putint(int res){
static char q[10];
if(res == 0) putch('0');
else if(res < 0){ putch('-'); res = -res; }
int top = 0;
while(res){
q[top ++] = res % 10 + '0';
res /= 10;
}
while(top--) putch(q[top]);
}

inline void space(bool x){
if(!x) putch('\n');
else putch(' ');
}
}

inline void read(int &x){
int rt = FastIO::getint();
x = rt;
}

inline void print(int x,bool enter){
FastIO::putint(x);
FastIO::flush();
FastIO::space(enter);
}

对拍

此版本为 $\text{Windows}$ 下的对拍原码,使用 $\text{Mac OS}$ 或 $\text{Linux}$ 的读者请自行查找适用于自己系统的对拍代码

考场不对拍,爆零两行泪。

#include <bits/stdc++.h>
#include <windows.h>

using namespace std;

int num , s , t;

int main(){
while(1){
system("cls");
do{
num ++; system("data.exe");
s = clock(); system("a.exe");
t = clock(); system("b.exe");
if(system("fc try1.out try2.out")) break;
else{
printf("AC on text #%d , time is %d\n" , num , t - s);
}
}while(true);
printf("WA on text #%d , time is %d\n" , num , t - s);
system("fc try1.out try2.out");
system("pause > nul");
}
return 0;
}

THE END


评论
va
avatar
Album.
起风了,唯有努力生存
Go To My Github
公告
成为很厉害很厉害的人,最重要的,就是要热血。永远不要让你的血凉下去。