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

ACM板子

一、算法板

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. 递归+迭代（动态规划）

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
// 递归实现斐波那契数列（时间复杂度 O(2^n)）
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

// 迭代实现斐波那契数列（时间复杂度 O(n)）
int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

/*配合记忆化数组后*/

// 自顶向下（递归+记忆化）
int memo[1000] = {0};
int fib_top_down(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib_top_down(n-1) + fib_top_down(n-2);
    return memo[n];
}

// 自底向上（迭代动态规划）
int fib_bottom_up(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

5. 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
struct road{ int to;  int w; };
struct node{ vector<road> r; };

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

void solve(){
    int n,m,s;
    cin>>n>>m>>s;
    int t1,t2,tw, temp, tx;  s=1;
    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]<<" ";
    }
}

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 加法 版本
int arr[100005];

struct node{
    int l,r;
    int sum=0,lz=0;
} tree[400005];

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

void pushdown(int i){
    if(tree[i].l == tree[i].r) return;
    if(tree[i].lz!=0){
        int lz = tree[i].lz;
        tree[2*i].lz += lz; 
        tree[2*i+1].lz += lz;
        tree[2*i].sum += lz*(tree[2*i].r-tree[2*i].l+1);
        tree[2*i+1].sum += lz*(tree[2*i+1].r-tree[2*i+1].l+1);
        tree[i].lz = 0;
    }
}

// 乘法+加法 版本
int arr[100005]; int m;
struct node{
    int l,r;
    int sum;
    int plz=0,mlz=1;
} tree[400005];

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)%m;
}

void pushdown(int i){
    if(tree[i].l==tree[i].r) return;
    if(tree[i].plz!=0 || tree[i].mlz!=1){
        int plz = tree[i].plz, mlz = tree[i].mlz;
        tree[i<<1].mlz = (tree[i<<1].mlz*mlz)%m;
        tree[i<<1].plz = (tree[i<<1].plz*mlz+plz)%m;
        tree[i<<1|1].mlz = (tree[i<<1|1].mlz*mlz)%m;
        tree[i<<1|1].plz = (tree[i<<1|1].plz*mlz+plz)%m;

        int s1=tree[i<<1].r-tree[i<<1].l+1, s2=tree[i<<1|1].r-tree[i<<1|1].l+1;
        tree[i<<1].sum = (mlz*tree[i<<1].sum+plz*s1)%m;
        tree[i<<1|1].sum = (mlz*tree[i<<1|1].sum+plz*s2)%m;

        tree[i].plz = 0; tree[i].mlz = 1;
    }
}

void add(int l, int r, int mk, int pk, int i=1){
    if(tree[i].l>=l && tree[i].r<=r){
        int s = tree[i].r - tree[i].l +1;
        tree[i].mlz = (tree[i].mlz*mk)%m;
        tree[i].plz = (mk*tree[i].plz + pk)%m;
        tree[i].sum = (mk*tree[i].sum+pk*s)%m;
        return;
    }
    if(tree[i].l>r || tree[i].r<l) return;
    pushdown(i);
    if(tree[i<<1].r>=l) add(l,r,mk,pk,i<<1);
    if(tree[i<<1|1].l<=r) add(l,r,mk,pk,i<<1|1);
    tree[i].sum = (tree[i<<1].sum + tree[i<<1|1].sum)%m;
}

int search(int l, int r, int i=1){
    if(tree[i].l>=l && tree[i].r<=r) return tree[i].sum;
    if(tree[i].l>r || tree[i].r<l) return 0;
    pushdown(i);
    int s = 0;
    if(tree[i<<1].r>=l) s = (s+search(l,r,i<<1))%m;
    if(tree[i<<1|1].l<=r) s = (s+search(l,r,i<<1|1))%m;
    return s;
}

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

二、方便板

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
38
39
40
41
42
43
//  codeforce
#include<bits/stdc++.h>
using namespace std;
#define ll long long

void init(){}

void solve(){
    
}

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

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

void init(){}

void solve(){
    
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    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
59
// 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 T;
    _ftime(&T);
    srand(T.millitm);
    //生成读入数据
    freopen("test.in", "w", stdout); //生成 使两份基本代码 将要读入的数据
    if (!freopen("test.in", "w", stdout)) {
        perror("freopen");   // 会打印 "No such file or directory"
        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

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