^-^
We see things not as they are, but as we are.
ACM-template
最近更新：2025-11-12   |   字数总计：2.4k   |   阅读估时：14分钟   |   阅读量：次
  1. 一、算法板
    1. 1. 快速幂
    2. 2. 最大公约数
    3. 3. 求素数
    4. 4. dijkstra 单源最短路径
    5. 5. 树状数组
    6. 6. 线段树
    7. 7. 并查集
    8. 8. KMP
    9. 9. 贪心（填坑题型）
    10. 10. 逆元
    11. 11. 组合数
  2. 二、方便板
    1. 1. 框架
    2. 2. 结构体
    3. 3. 快读快写
    4. 4. 对拍
    5. 5. 保留小数
  3. 三、小贴士
    1. 1.数据量判断

一、算法板

1. 快速幂

1
2
3
4
5
6
7
8
9
using ull = unsigned long long;
ull qpow(ull a, ull b, ull mod) {
	ull res = 1;
	for (a %= mod; b; b >>= 1) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
	}
	return res;
}

2. 最大公约数

1
2
3
4
5
6
7
8
int gcd(int a, int b) {
	while (b != 0) {
    	int tmp = a;
    	a = b;
    	b = tmp % b;
    }
    return a;
}

3. 求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool isPrime(int a) {
    if (a < 2) return 0;
    for (int i = 2; (long long)i * i <= a; ++i)  // 防溢出
    if (a % i == 0) return 0;
    return 1;
}

// 线性筛（欧拉筛）
vector<int> pri;
bool not_prime[N];

void pre(int n) {
  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;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

4. dijkstra 单源最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// #define int long long
// #define INT_MAX LLONG_MAX

struct road{ int to;  int w; };
struct node{ vector<road> r; };

int dis[100005];
int vis[100005];
node arr[100003];

void dijkstra(){
    int n,m;
    cin>>n>>m;
    int t1,t2,tw, temp, tx;
    for(int i=0;i<m;i++){
        cin>>t1>>t2>>tw;
        arr[t1].r.push_back({t2,tw});
        // arr[t2].r.push_back({t1,tw}); //有向边就注释，无向边就留下
    }
    fill(dis,dis+n+1,INT_MAX);
    fill(vis,vis+n+1,0);
    dis[1]=0;
    priority_queue< 
        pair<int,int>, 
        vector<pair<int,int>>, 
        greater<pair<int,int>> 
    > pq;
    pq.push({0,1});
    
    while(!pq.empty()){
        auto[d, i] = pq.top();  pq.pop();
        if(vis[i]) continue;
        vis[i] = 1;

        for(auto iter:arr[i].r){
            temp = dis[i]+ iter.w;
            tx = iter.to;
            if(temp<dis[tx]){
                dis[tx] = temp;
                pq.push({dis[tx],tx});
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
}

5. 树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* 单点修改 + 区间查询 */
#define int long long
#define M 2000005
#define mod LLONG_MAX
struct node{
    int sum;
    int l,r;
}tree[M];
int arr[M];

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

void add(int x, int d, int i=1){
    if(tree[i].l==x && tree[i].r==x){
        tree[i].sum =  (tree[i].sum + d)%mod; return;
    }
    int mid = (tree[i].l+tree[i].r)>>1;
    if(x<=mid) add(x,d,i<<1);
    else add(x,d,i<<1|1);

    tree[i].sum = (tree[i<<1].sum + tree[i<<1|1].sum)%mod;
}

int search(int l, int r, int i=1){
    if(tree[i].l>r || tree[i].r<l) return 0;
    else if(tree[i].l>=l && tree[i].r<=r) return tree[i].sum;

    int mid=(tree[i].l+tree[i].r)>>1, cnt=0;
    if(mid>=l) cnt = (cnt + search(l,r,i<<1) )%mod;
    if(mid+1<=r) cnt = (cnt + search(l,r,i<<1|1) )%mod;
    return cnt; 
}

6. 线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
struct node{
    int l,r; int sum; int tag;
}tree[400005];
int arr[100005];

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

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 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;
    if(jobr >= tree[i].l && jobl <= mid){
        down(i);
        add(jobl, jobr, k, i<<1);
    } 
    if(jobl <= tree[i].r && jobr >= mid+1){
        down(i);
        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;
    if(jobr >= tree[i].l && jobl <= mid){
        down(i);
        sum += search(jobl, jobr, i<<1);
    }
    if(jobl <= tree[i].r && jobr >= mid+1){
        down(i);
        sum += search(jobl, jobr, i<<1|1);
    }
    return sum;
}

7. 并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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. 贪心（填坑题型）

1
2
3
4
5
6
7
8
9
10
11
void solve(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    int ans = v[0];
    for(int i=1;i<n;i++){
        if(v[i]>v[i-1]) ans+=v[i]-v[i-1];
    }
    cout<<ans<<endl;
}

10. 逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 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) {
  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); }

11. 组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long c(long long n, long long m){   // C(m,n)
    if(n < 0 || n > m) return 0;
    n = min(n, m-n);
    long long res = 1;
    for(long long i=1;i<=n;i++){
        long long a = m-n+i;
        long long b = i;
        long long g = gcd(a,b);
        a/=g; b/=g;
        g = gcd(res,b);
        res/=g; b/=g;
        if(a && res > LLONG_MAX / a) return LLONG_MAX;
        res*=a;
    }
    return res;
}

二、方便板

1. 框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//  codeforce
#include<bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

//  AtCoder
#include<bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

2. 结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct node {
    int a;
    double b;

    // 重载等于操作符
    bool operator==(const node& other) const {
        return a == other.a && b == other.b;
    }
    // 重载小于操作符，用于排序和 std::map
    bool operator<(const node& other) const {
        if (a != other.a) return a < other.a;
        return b < other.b;
    }
};

// 为 node 定义哈希函数
struct node_hash {
    size_t operator()(const node& s) const {
        return hash<int>()(s.a) ^ hash<double>()(s.b);
    }
};

3. 快读快写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}

4. 对拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 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;
}

5. 保留小数

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

三、小贴士

1.数据量判断

#常数指令操作量为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 ✔️ ❌ ❌ ❌ ❌ ❌ ❌
2025-11-12 该篇文章被 Apeiron 归为分类: ACM

上一篇：ACM-library 下一篇：CF-0
© 2025 ❤ Apeiron
🔮There is no end, only extending.🔮 本站由Hexo驱动｜使用Hexo-theme-A4主题