C++ 常用代码集合

发表于2023-08-01更新于2023-09-18

会把一些常用的 C++ 代码片段写到这里，不定时更新。

代码模板

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
/*******************************************
 * Code Info
    Author: xvl_
    Date: Unknown
 * Problem Info
    Online Judge: Unknown
    Url: Unknown
*******************************************/
#include <bits/stdc++.h>
namespace xvl_ { 
    #define ll long long
    #define ld long double
    #define IMAX 1e9
    #define LMAX 1e18
    #define SP(n, x) std :: setprecision(n) << std :: fixed << x
    #define Off_Sync ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
    void debug() { std :: cerr << "debug" << "\n"; } 
    template <typename T> inline T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> inline T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
    template <typename T> inline T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> inline T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;

int main() {
    // freopen("InName.in", "r", stdin);
    // freopen("OutName.out", "w", stdout);
    Off_Sync;

    return 0;
}

十进制数转二进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
unsigned ll n;
vector <int> ans;
void bin(vector <int>& A, unsigned ll n) {
    do {
        A.push_back(n & 1);
        n >>= 1;
    } while (n);
}
int main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    bin(ans, n);
    for (int i = 0; i < ans.size(); i++) cout << ans[i];
    return 0;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, m, p;
int qpow(ll n, ll m, int p) { return !m ? 1 : ((m & 1 ? n : 1) * (m = qpow(n, m >> 1, p)) % p * m % p); }
int main() {
    ios :: sync_with_stdio(0);
    cin >> n >> m >> p;
    cout << qpow(n, m, p);
    return 0;
}

最长上升子序列 / LIS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, ans = -INF;
int a[5005], dp[5005];
int main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j <= i; j++) {
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

最长上升子序列 / LIS （二分优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, ans;
int a[100005], g[100005];
int main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) g[i] = INF;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        g[lower_bound(g + 1, g + ans + 1, a[i]) - g] = a[i];
        ans = max(ans, (int)(lower_bound(g + 1, g + ans + 1, a[i]) - g));
    }
    cout << ans;
    return 0;
}