Apeironverse | Where eternity meets creation

ACM-template

最近更新：2025-11-12 | 字数总计：5.6k | 阅读估时：33分钟 | 阅读量：次

一、算法板
二、方便板

一、算法板

1. 快速幂

#define int long long
#define mod 998244353
int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b&1) res = (res*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return res;
}


// 矩阵快速幂
#define int long long
#define mod 998244353
vector<vector<int>> f(vector<vector<int>>& v1, vector<vector<int>>& v2){
    int n1 = v1.size(), m1 = v1[0].size(), n2 = v2.size(), m2 = v2[0].size();
    vector<vector<int>> res(n1, vector<int>(m2));
    for(int i=0;i<n1;i++){
        for(int k=0;k<n2;k++){
            for(int j=0;j<m2;j++){
                res[i][j] += v1[i][k] * v2[k][j];
                res[i][j] %= mod;
            }
        }
    }
    return res;
}

vector<vector<int>> qpow(vector<vector<int>> v, int k, int n){
    vector<vector<int>> res(n, vector<int>(n));
    for(int i=0;i<n;i++) res[i][i] = 1;
    while(k){
        if(k&1) res = f(res, v);
        v = f(v, v);
        k >>= 1;
    }
    return res;
}

2. 线性基

#define int long long
bool zero = false;
vector<int> basis(vector<int> v){
    zero = false;
    int n = v.size();
    int m = 0;
    for(int k=61;k>=0;k--){
        int flag = 0;
        for(int i=m;i<n;i++){
            if(v[i]&(1ll<<k)){
                swap(v[m],v[i]);
                flag = 1;
                break;
            }
        }
        if(flag){
            for(int i=0;i<n;i++){
                if(i==m || (v[i]&(1ll<<k))==0) continue;
                v[i] ^= v[m];
            }
            m++;
        }
    }
    if(m!=n) zero = true;
    vector<int> base(m);
    for(int i=0;i<m;i++) base[m-1-i] = v[i];  // 从小到大排序
    return base;
}

int getkmin(vector<int>& base, int k){   // 获取第k小的异或和
    int m = base.size();
    if(zero && k==1) return 0;
    if(zero) k--;
    if(k>(1ll<<m)-1) return -1;
    int res = 0;
    for(int i=0;i<m;i++){
        if(k & (1ll<<i)){
            res ^= base[i];
        }
    }
    return res;
}
int getkmax(vector<int>& base, int k){   // 获取第k大的异或和
    int m = base.size();
    int num = zero ? (1ll<<m) : (1ll<<m)-1;
    return getkmin(base, num-k+1);
}

3. 线性筛

vector<int> pri;
const int N = 10000099;
bool not_prime[N];
int mfa[N];  // 第i个数的最小公因子

void pre(int n = N){
    for(int i=0;i<=n;i++) mfa[i] = i;
    for(int i=2;i<=n;++i){
        if(!not_prime[i]){
            pri.push_back(i);
        }
        for(int pri_j : pri){
            if(i * pri_j > n) break;
            not_prime[i * pri_j] = true;
            mfa[i*pri_j] = min(mfa[i*pri_j], pri_j);
            if(i % pri_j == 0) break;
        }
    }
}

4. dijkstra 单源最短路径

#define int long long
const int MAXN = 100005;

struct node{
    vector<array<int,2>> to; // {idx, w}  // 多测记得清空
}arr[MAXN];

int dis[MAXN];  // 到达i点的最小费用
int vis[MAXN];  // 到达i点的最小费用是否已经确定
int pre[MAXN];  // 到达i点的最小费路径中i的前驱

void dijkstra(int n, int root){
    fill(dis, dis+n+1, LLONG_MAX);
    fill(vis, vis+n+1, 0);
    dis[root] = 0;
    priority_queue< 
        pair<int,int>, 
        vector<pair<int,int>>, 
        greater<pair<int,int>> 
    > pq;
    pq.push({dis[root], root});
    while(!pq.empty()){
        int x = pq.top().second;  pq.pop();
        if(vis[x]) continue;
        else vis[x] = 1;

        for(auto it:arr[x].to){
            int nx = it[0], w = it[1];
            int d = dis[x] + w;
            if(d < dis[nx]){
                dis[nx] = d;
                pre[nx] = x;
                pq.push({dis[nx], nx});
            }
        }
    }
}

5. 树状数组

int tree[1000005];

int lowb(int x){
    return x&(-x);
}
void init(int n){
    for(int i=0;i<=n;i++) tree[i] = 0;
}
void add(int x, int k, int n){
    for(int i=x;i<=n;i+=lowb(i)) tree[i]+=k;
}
int search(int l, int r, int n){
    int ans = 0;
    for(int i=l-1;i>0;i-=lowb(i)) ans -= tree[i];
    for(int i=r;i>0;i-=lowb(i)) ans += tree[i];
    return ans;
}

6. 线段树

const int MAXN = 100005;
struct node{
    int l,r; 
    int sum = 0;
    int tag = 0;
    void clear(){
        *this = node();
    }
}tree[4*MAXN];
int arr[MAXN];

void lazy(int k, int i){
    tree[i].sum += (tree[i].r - tree[i].l + 1) * k;
    tree[i].tag += k;
}
void down(int i){
    lazy(tree[i].tag, i<<1);
    lazy(tree[i].tag, i<<1|1);
    tree[i].tag = 0;
}
void up(int i){
    tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
}

void build(int l, int r, int i=1){
    tree[i].clear();
    tree[i].l = l; tree[i].r = r;
    if(tree[i].l == tree[i].r){
        tree[i].sum = arr[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l, mid, i<<1);
    build(mid+1, r, i<<1|1);
    up(i);
}

void add(int jobl, int jobr, int k, int i=1){
    if(jobl <= tree[i].l && jobr >= tree[i].r){
        lazy(k, i); return;
    }
    int mid = (tree[i].l+tree[i].r)>>1;
    down(i);
    if(jobr >= tree[i].l && jobl <= mid){
        add(jobl, jobr, k, i<<1);
    } 
    if(jobl <= tree[i].r && jobr >= mid+1){
        add(jobl, jobr, k, i<<1|1);
    }
    up(i);
}

int search(int jobl, int jobr, int i=1){
    if(jobl <= tree[i].l && jobr >= tree[i].r){
        return tree[i].sum;
    }
    int sum = 0;
    int mid = (tree[i].l+tree[i].r)>>1;
    down(i);
    if(jobr >= tree[i].l && jobl <= mid){
        sum += search(jobl, jobr, i<<1);
    }
    if(jobl <= tree[i].r && jobr >= mid+1){
        sum += search(jobl, jobr, i<<1|1);
    }
    return sum;
}

7. 并查集

int pre[200005];

void build(int n){
    for(int i=0;i<=n;i++) pre[i]=i;
}
int find(int i){
    if(pre[i] == i) return i;
    return pre[i] = find(pre[i]);
}
void join(int i, int j){
    int x = find(i), y = find(j);
    pre[x] = y;
}
bool isSet(int i, int j){ 
    return find(i)==find(j);
}

8. KMP

void kmp(string s, string t){
	int n=s.length(), l=t.length();
	vector<int> next(l,0);
	vector<int> ans;
	int i=1,pre=0,p=0;
	while(i<l){
		if(t[i]==t[pre]){
			next[i] = (++pre); i++;
		}
		else{
			if(pre==0) i++;
			else pre = next[pre-1];
		}
	}
	i=0;
	while(i<n){
		if(s[i]==t[p]){
			i++; p++;
		}
		else if(p==0) i++;
		else p = next[p-1];

		if(p==l){
			ans.push_back(i-p+1);
			p = next[p-1];
		}
	}
	
	for(int it:ans) cout<<it<<endl;
	//for(int i=0;i<l;i++) cout<<next[i]<<" ";
	//cout<<endl;
}

9. NTT 数论变换

constexpr int N = 1 << 20, P = 998244353;

int qpow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % P;
    x = 1ll * x * x % P;
    y >>= 1;
  }
  return res;
}

int r[N];

void ntt(vector<int>& x, int lim, int opt) {
  for (int i = 0; i < lim; ++i)
    if (r[i] < i) swap(x[i], x[r[i]]);
  for (int m = 2; m <= lim; m <<= 1) {
    int k = m >> 1;
    int gn = qpow(3, (P - 1) / m);
    for (int i = 0; i < lim; i += m) {
      int g = 1;
      for (int j = 0; j < k; ++j, g = 1ll * g * gn % P) {
        int tmp = 1ll * x[i + j + k] * g % P;
        x[i + j + k] = (x[i + j] - tmp + P) % P;
        x[i + j] = (x[i + j] + tmp) % P;
      }
    }
  }
  if (opt == -1) {
    reverse(x.begin() + 1, x.begin() + lim);
    int inv = qpow(lim, P - 2);
    for (int i = 0; i < lim; ++i) x[i] = 1ll * x[i] * inv % P;
  }
}

vector<int> f(vector<int> A, vector<int> B) {
  if (A.empty() || B.empty()) return {};
  int n = A.size();
  int m = B.size();
  int max_len = max(n, m), lim = 1;
  while (lim < (max_len << 1)) lim <<= 1;
  A.resize(lim, 0);
  B.resize(lim, 0);

  for (int i = 0; i < lim; ++i) 
    r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);
    
  ntt(A, lim, 1);
  ntt(B, lim, 1);
  
  vector<int> C(lim);
  for (int i = 0; i < lim; ++i) 
    C[i] = 1ll * A[i] * B[i] % P;
  ntt(C, lim, -1);

  C.resize(n + m - 1);
  return C;
}

10. 逆元

// Extended Euclidean algorithm.(扩展欧几里得法)
void ex_gcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= a / b * x;
  }
}
int inverse(int a, int m) {   // a^-1 mod m
  int x, y;
  ex_gcd(a, m, x, y);
  return (x % m + m) % m;
}

// Binary exponentiation.(快速幂法，适用于模数为素数)
int pow(int a, int b, int m) {
  long long res = 1, po = a;
  for (; b; b >>= 1) {
    if (b & 1) res = res * po % m;
    po = po * po % m;
  }
  return res;
}
int inverse(int a, int p) { return pow(a, p - 2, p); }  // a^-1 mod p

11. 组合数取模

const int MAXN = 1000005;
long long fa[MAXN];
long long ifa[MAXN];

long long qpow(long long a, long long b) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init() {
    fa[0] = 1;
    ifa[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fa[i] = fa[i - 1] * i % mod;
    }
    ifa[MAXN - 1] = qpow(fa[MAXN - 1], mod - 2);
    for (int i = MAXN - 2; i >= 1; i--) {
        ifa[i] = ifa[i + 1] * (i + 1) % mod;
    }
}

// O(1) 查询组合数 C(n, m) % mod，n在上，m在下
long long C(long long n, long long m) {
    if (n < 0 || n > m) return 0;
    return fa[m] * ifa[n] % mod * ifa[m - n] % mod;
}

12. 字符串哈希

const int MAXN = 100005;

string s;
unsigned long long p[MAXN];
unsigned long long h[MAXN];

void init(){
    int n = s.size();
    const int base = 131;
    p[0] = 1; h[0] = s[0];
    for(int i=1;i<n;i++){
        h[i] = h[i-1]*base + s[i];
        p[i] = p[i-1]*base;
    }
}
unsigned long long get(int l, int r){
    unsigned long long res = h[r];
    if(l>0) res -= h[l-1]*p[r-l+1];
    return res;
}

bool cmp(int x1, int x2){
    int res = 0, len = s.size()-max(x1,x2);
    int l = 1, r = len;
    while(l<=r){
        int mid = (l+r)>>1;
        auto t1 = get(x1, x1+mid-1);
        auto t2 = get(x2, x2+mid-1);
        if(t1==t2){
            res = max(res, mid);
            l = mid+1;
        }else r = mid-1;
    }
    if(res == len) return x1 > x2;
    return s[x1+res]<s[x2+res];
}

// 字符串后缀排序预处理
int suf[MAXN];
int rk[MAXN];

void init2(){
    int n = s.size();
    for(int i=0;i<n;i++) suf[i] = i;
    sort(suf, suf+n, cmp);
    for(int i=0;i<n;i++) rk[suf[i]] = i+1;
}

13. 分解质因数

vector<int> breakdown(int N){
    vector<int> result;
    for(int i=2;i*i<=N;i++){
        if(N%i == 0){  // 如果 i 能够整除 N，说明 i 为 N 的一个质因子．
          while(N%i == 0) N /= i;
          result.push_back(i);
        }
    }
    if(N != 1){  // 说明再经过操作之后 N 留下了一个素数
        result.push_back(N);
    }
    return result;
}

14. BSGS 大步小步算法

// 1. a⊥p的条件下，求 a^x = b (mod p) 的x最小解， 负数为无解
int BSGS(int a, int b, int p) {
    if (1 % p == b % p) return 0;
    unordered_map<int, int> hash;
    int k = sqrt(p) + 1;
    for (int i = 0, j = b % p; i < k; i ++)
        hash[j] = i, j = j * a % p;
    int ak = 1;
    for (int i = 1; i <= k; i ++)
        ak = ak * a % p;
    for (int i = 1, j = ak; i <= k; i ++) {
        if (hash.count(j)) return i * k - hash[j];
        j = j * ak % p;
    }
    return -1e9;
}

//2. a不一定与b互质 (exBSGS)

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

int ExBSGS(int a, int b, int p) {
    b = (b % p + p) % p;
    if (1 % p == b % p) return 0;
    int d = __gcd(a, p);
    if (d > 1) {
        if (b % d) return -1e9;
        int x, y;
        Exgcd(a / d, p / d, x, y);
        return ExBSGS(a, b / d * x, p / d) + 1;
    }
    return BSGS(a, b, p);
}

    // int a,b,p; cin>>a>>b>>p;
    // int res;
    // if (__gcd(a, p) == 1) res = BSGS(a, b, p);
    // else res = ExBSGS(a, b, p);
    // if (res < 0) cout << "No Solution" << '\n';
    // else cout << res << '\n';

15. ST表

const int MAXN = 100005;
int arr[MAXN];
int stmax[MAXN][32];

void init(int n){
    for(int i=0;i<=n;i++) stmax[i][0] = arr[i];
    for(int p=1;p<=__lg(n);p++){
        for(int i=0;i + (1ll<<p) <= n;i++){
            int pv = 1ll<<(p-1);
            stmax[i][p] = max(stmax[i][p-1], stmax[i+pv][p-1]);
        }
    }
}

int search(int l, int r){
    int len = r-l+1;
    int p = __lg(len);
    int pv = 1ll<<p;
    int res = max(stmax[l][p], stmax[r-pv+1][p]);
    return res;
}

// st表倍增法求LCA（最近公共祖先）
const int MAXN = 500005;
struct node{
    int fa = 0;
    int deep = 0;
    vector<int> to;  // 多测记得清空
}arr[MAXN];
int stlca[MAXN][21];

void bfs(int root){
    arr[root].deep = 1;
    arr[root].fa = root;
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int t = q.front(); q.pop();
        for(int it:arr[t].to){
            if(it == arr[t].fa) continue;
            arr[it].fa = t;
            arr[it].deep = arr[t].deep+1;
            q.push(it);
        }
    }
}

void init(int n, int root){
    bfs(root);
    for(int i=0;i<=n;i++) stlca[i][0] = arr[i].fa;
    for(int p=1;p<=20;p++){
        for(int i=0;i<=n;i++){
            stlca[i][p] = stlca[stlca[i][p-1]][p-1];
        }
    }
}

int lca(int u, int v){
    if(u==v) return u;
    if(arr[u].deep > arr[v].deep){
        for(int p=20;p>=0;p--){
            int t = stlca[u][p];
            if(arr[t].deep<=arr[v].deep) continue;
            else u = t;
        }
        u = stlca[u][0];
        if(u==v) return v;
    }
    if(arr[v].deep > arr[u].deep){
        for(int p=20;p>=0;p--){
            int t = stlca[v][p];
            if(arr[t].deep<=arr[u].deep) continue;
            else v = t;
        }
        v = stlca[v][0];
        if(v==u) return u;
    }

    for(int p=20;p>=0;p--){
        int nu = stlca[u][p], nv = stlca[v][p];
        if(nu==nv) continue;
        else{
            u = nu; v = nv;
        }
    }
    return stlca[u][0];
}

16. 虚树

const int MAXN = 250005;

struct node{
    int fa = 0;
    int deep = 0;
    vector<int> to;  // 多测记得清空
}arr[MAXN], brr[MAXN];  // arr是实树，brr是虚树
int stlca[MAXN][21];

// ---------- lca ----------
void bfs(int root){
    arr[root].deep = 1;
    arr[root].fa = root;
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int t = q.front(); q.pop();
        for(int it:arr[t].to){
            if(it == arr[t].fa) continue;
            arr[it].fa = t;
            arr[it].deep = arr[t].deep+1;
            q.push(it);
        }
    }
}
void init(int n, int root){
    bfs(root);
    for(int i=0;i<=n;i++) stlca[i][0] = arr[i].fa;
    for(int p=1;p<=20;p++){
        for(int i=0;i<=n;i++){
            stlca[i][p] = stlca[stlca[i][p-1]][p-1];
        }
    }
}
int lca(int u, int v){
    if(u==v) return u;
    if(arr[u].deep > arr[v].deep){
        for(int p=20;p>=0;p--){
            int t = stlca[u][p];
            if(arr[t].deep<=arr[v].deep) continue;
            else u = t;
        }
        u = stlca[u][0];
        if(u==v) return v;
    }
    if(arr[v].deep > arr[u].deep){
        for(int p=20;p>=0;p--){
            int t = stlca[v][p];
            if(arr[t].deep<=arr[u].deep) continue;
            else v = t;
        }
        v = stlca[v][0];
        if(v==u) return u;
    }

    for(int p=20;p>=0;p--){
        int nu = stlca[u][p], nv = stlca[v][p];
        if(nu==nv) continue;
        else{
            u = nu; v = nv;
        }
    }
    return stlca[u][0];
}
// ---------- lca ----------

int idx = 1;   // 多测idx记得重置
int dfn[MAXN];
void dfs(int x){
    dfn[x] = idx++;
    for(auto it:arr[x].to){
        if(it == arr[x].fa) continue;
        dfs(it);
    }
}

bool cmp(int x, int y) {
    return dfn[x] < dfn[y];  // 按照 dfs 序排序
}

int b1[MAXN], b2[MAXN];  // b1是重要节点数组，b2是b1加上lca后的节点数组
int build_virtual_tree(int m){  // 返回虚树大小
    int len = 0;
    sort(b1+1, b1+m+1, cmp);
    for(int i=1;i<m;i++){
        b2[++len] = b1[i];
        b2[++len] = lca(b1[i], b1[i+1]);
    }
    b2[++len] = b1[m];
    sort(b2+1, b2+len+1, cmp);
    len = unique(b2+1, b2+len+1) - b2 - 1;  // 去重

    for(int i=0;i<=len;i++) brr[b2[i]].to.clear();
    for(int i=1;i<len;i++){
        int lc = lca(b2[i], b2[i+1]);
        brr[lc].to.push_back(b2[i+1]);  // 连边，如有边权 就是 distance(lc,a[i+1])
    }
    return len;
}

17. 凸包

#define int long long
struct point{
    double x,y;

    point operator+ (const point& b) const{ return {x+b.x, y+b.y}; }
    point operator- (const point& b) const{ return {x-b.x, y-b.y}; }
    double operator^ (const point& b) const{ return x*b.y - y*b.x; }
    double operator* (const point& b) const{ return x*b.x + y*b.y; }
};
double dis(const point &a, const point &b){
    double res = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return sqrt(res);
}

double area(const vector<point> &v){
    if(v.size() < 3) return 0;
    double res = 0;
    int n = v.size();
    for(int i=0;i<n;i++){
        double tmp = (v[i]^v[(i+1)%n]);
        res += tmp;
    }
    res = res*1.0/2;
    return abs(res);
}

vector<point> andrew(vector<point> p){
    // 字典序排序
    sort(p.begin(), p.end(), [](const point& a, const point& b){
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    // 去重
    p.erase(unique(p.begin(), p.end(), [](const point& a, const point& b) {
        return a.x == b.x && a.y == b.y;
    }), p.end());

    int n = p.size();
    if(n <= 2) return p; // 只有1~2个点，本身就是凸包

    vector<point> st; // 使用 vector 模拟栈
    
    // 求下凸壳
    for(int i=0;i<n;i++){
        while(st.size()>1 && ((st.back()-st[st.size()-2])^(p[i]-st.back()))<=0){
            st.pop_back();
        }
        st.push_back(p[i]);
    }
    // 求上凸壳
    int k = st.size();
    for(int i=n-2;i>=0;i--){
        while(st.size()>k && ((st.back()-st[st.size()-2])^(p[i]-st.back()))<=0){
            st.pop_back();
        }
        st.push_back(p[i]);
    }

    st.pop_back();
    return st;  // 返回逆时针顺序的凸包
}

18. 闵可夫斯基和

#define int long long
struct point{
    int x,y;

    point operator+ (const point& b) const{ return {x+b.x, y+b.y}; }
    point operator- (const point& b) const{ return {x-b.x, y-b.y}; }
    int operator^ (const point& b) const{ return x*b.y - y*b.x; }
    int operator* (const point& b) const{ return x*b.x + y*b.y; }
};

void pre(vector<point> &v){
    for(int i=1;i<v.size();i++){
        if(v[i].x<v[0].x || (v[i].x==v[0].x && v[i].y<v[0].y)){
            swap(v[0],v[i]);
        }
    }
    auto cmp = [&](const point &a, const point &b){
        auto cross = (a - v[0]) ^ (b - v[0]);
        if(cross != 0) return cross > 0;
        return ((a-v[0])*(a-v[0])) < ((b-v[0])*(b-v[0]));
    };
    sort(v.begin()+1, v.end(), cmp);
    
    int k = v.size() - 1;
    while(k>=1 && ((v[k] - v[0]) ^ (v.back() - v[0])) == 0) k--;
    reverse(v.begin() + k + 1, v.end());
}

vector<point> minkowski_sum(vector<point> a, vector<point> b){
    pre(a); pre(b);
    vector<point> c{a[0] + b[0]};
    a.push_back(a[0]);
    b.push_back(b[0]);
    for(int i=0;i+1<a.size();i++) a[i] = a[i+1] - a[i];
    for(int i=0;i+1<b.size();i++) b[i] = b[i+1] - b[i];
    a.pop_back(); b.pop_back();
    c.resize(a.size()+b.size()+1);

    auto cmp = [](const point &a, const point &b){
        return (a^b) > 0 ;
    };
    merge(a.begin(),a.end(), b.begin(),b.end(), c.begin()+1, cmp);
    for(int i=1;i<c.size();i++) c[i] = c[i] + c[i-1];
    c.pop_back();
    return c;
}

19. 字典树

const int MAXN = 1000005;
struct node{
    int val;
    int pass;
    int end;
    array<int,26> to{};
}tree[MAXN];
int idx = 1;  // 多测记得重置

void init(){
    array<int,26> a0{};
    for(int i=0;i<=idx;i++){
        tree[i].to = a0;
        tree[i].pass = 0;
        tree[i].end= 0;
    }
    idx = 1;
}

void insert(const string& s){
    int cur = 0;
    for(int i=0;i<s.length();i++){
        int val = s[i]-'a';
        if(tree[cur].to[val]==0){
            tree[cur].to[val] = idx;
            tree[idx].val = val;
            tree[idx].pass = 0;
            idx++;
        }
        cur = tree[cur].to[val];
        tree[cur].pass++;
    }
    tree[cur].end++;
}

void erase(const string& s){
    int cur = 0;
    for(int i=0;i<s.length();i++){
        int val = s[i]-'a';
        int nx = tree[cur].to[val];
        tree[nx].pass--;
        if(tree[nx].pass == 0){
            tree[cur].to[val] = 0;
            return;
        }        
        else cur = nx;
    }
    tree[cur].end--;
}

二、方便板

1. 框架

/* ❀ Apeiron Coding ❀ */
#include<bits/stdc++.h>
using namespace std;
#define Apeiron main
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define endl '\n'
#define int long long

void solve(){
    
}

signed Apeiron(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int A=1;
    cin>>A;
    while(A--){
        solve();
    }
    cout.flush();
    return 0^0;
}

2. 复杂度

#常数指令操作量为10^8~10^9(一般认为是5*10^8)

	o(logn)	o(n)	o(nlogn)	o(n√n)	o(n^2)	o(2^n)	o(n!)
n<=11	✔️	✔️	✔️	✔️	✔️	✔️	✔️
n<=25	✔️	✔️	✔️	✔️	✔️	✔️	❌
n<=5000	✔️	✔️	✔️	✔️	✔️	❌	❌
n<=10^5	✔️	✔️	✔️	✔️	❌	❌	❌
n<=10^6	✔️	✔️	✔️	❌	❌	❌	❌
n<=10^7	✔️	✔️	❌	❌	❌	❌	❌
n<=10^9	✔️	❌	❌	❌	❌	❌	❌

3. 结构体

struct node {
    int a;
    double b;
    // 通过通过解引用 this 指针并赋一个全新构造的匿名对象，构建结构体内置清空方法
    void clear(){
        *this = node();
    }
    
    // 重写运算符
    bool operator < (const node &a) const{
        return 
    }
    {//直接传入一个参数，不必要写friend
        if(x == a.x)
            return y < a.y;
        return x < a.x;//按x升序排列
    }
};

// 创建 node 哈希容器
struct node_hash {
    size_t operator()(const node& s) const {
        return hash<int>()(s.a) ^ hash<double>()(s.b);
    }
};
unordered_set<node,node_hash> ust;

// 创建 node 集合
struct cmp {
    bool operator () (const node& u, const node& v) const {
    	return u.a < v.a;
    }
};
set<node,cmp> st;

// 创建 node 优先队列
auto cmp = [](node x, node y) -> bool{
    return x.a < x.b;
};
priority_queue<node, vector<node>, decltype(cmp)> q(cmp);

4. 快读快写

#define LOCAL
#include<iostream>
#include<cstdio>
using namespace std;
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            #define SIZE (1<<20)
            char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(p3=out,1,SIZE,stdout))
            #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        template<typename type>
        inline void read(type &x)
        {
            x=0;bool flag(0);char ch=getchar();
            while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            flag?x=-x:0;
        }
        template<typename type>
        inline void write(type x,bool flag=1)
        {
            x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
            do Stack[++top]=x%10,x/=10;while(x);
            while(top) putchar(Stack[top--]|48);
            flag?putchar('\n'):putchar(' ');
        }
        #ifndef LOCAL
            #undef SIZE
            #undef getchar
            #undef putchar
            #undef flush
        #endif
    }
}using namespace ly::IO;

signed main()
{
    int a,b;
    read(a),read(b);
    write(a,0),write(b); //write(x,flag=1),其中flag=0为空格，1为换行
    return 0;
}

5. 对拍

// gen.cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tt 20

ll Random(ll mod)
{
    ll ans = 2147483647;
    ans = ans * rand() % mod;
    return ans+1;
}

int main()
{
    //引入时间随机种子
    struct _timeb Tt;  _ftime(&Tt);  srand(Tt.millitm);
    //生成读入数据
    freopen("test.in", "w", stdout);
    if (!freopen("test.in", "w", stdout)) {
        perror("freopen");
        return 1;
    }
    /* ------------------------------------ */

    int T = Random(tt);  //t的范围是[1, tt]
    cout<<T<<endl;
    while(T--){

    }
    return 0;
}

// code1.cpp & code2.cpp
freopen("test.in", "r", stdin);
freopen("code1.out", "w", stdout);

freopen("test.in", "r", stdin);
freopen("code2.out", "w", stdout);

// check.cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t=200;
    while (t--)
    {
        system("gen.exe");
        system("code1.exe");
        system("code2.exe");
        if (system("fc code1.out code2.out")) 
            break;
    }
    if(t==-1) cout<<"!!!!! all accepted !!!!!"<<endl;
    else cout<<"!!!!! wrong answer !!!!!"<<endl;
    return 0;
}

6. 保留小数

1 2	double x = 3.1415926535; cout << fixed << setprecision(2) << x << endl; // 输出：3.14

7. Lambda表达式

// Form： auto f = [capture list] (parameter list) -> return type { function body }

// capture list 是捕获列表, "="是值捕获，"&"是引用捕获
// parameter list 是参数列表
// return type 是返回值类型
// function body 是函数体

int x = 10;
auto f = [x] (int y) -> int { return x + y; }; // 值捕获 x
x = 20; // 修改外部的 x
cout << f(5) << endl; // 输出 15，不受外部 x 的影响

int x = 10;
auto f = [&x] (int y) -> int { return x + y; }; // 引用捕获 x
x = 20; // 修改外部的 x
cout << f(5) << endl; // 输出 25，受外部 x 的影响

// Lambda表达式写递归(c++ 23)
int n; cin>>n;
auto f = [&](this auto& f, int x) ->int{
    if(x==1 || x==2) return 1;
    return f(x-1) + f(x-2);
};
cout<<f(n)<<endl;

// Lambda表达式写递归(c++ 14)
int n; cin>>n;
auto f = [](auto &self, int x) ->int{
    if(x==1 || x==2) return 1;
    return self(self, x-1) + self(self, x-2);
};
cout<<f(f,n)<<endl;

8. 随机化

1
2
3

using ull = unsigned long long;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
ull a = rnd();

2025-11-12 该篇文章被 Apeiron 归为分类: ACM