没啥用的板子

· · 个人记录

\text{洛谷 ver.}

\text{博客园 ver.}

\text{别人写的更吊的（南大）}

\text{别人写的更吊的（华东师大）}

\text{别人写的更吊的（上大 邝斌 kuangbin 2018） }

burh.

菜到极致才会写这些放这里。

这里都是板子题

动态规划

01 背包

\text{板子 P1048}

一维

const int N = 11451;

int n, m, a[N], b[N], dp[N] = {0};

int main() {

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &a[i], &b[i]);  
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = n; j >= a[i]; j--) {
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
    printf("%d", dp[n]);

    return 0;
}

二维

const int N = 11451;

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

int main() {

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &a[i], &b[i]);  
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j < a[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);
        }
    }
    printf("%d", dp[m][n]);

    return 0;
}

完全背包

\text{板子 P1616}

const int N = 11451;

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

int main() {

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &a[i], &b[i]);  
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j < a[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);
        }
    }
    printf("%d", dp[m][n]);

    return 0;
}

最长上升子序列（LIS）

\text{板子 B3637} \&\& \text{AT\_chokudai\_S001\_h}

二分


const int N = 1145141;

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

int main() {

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = N;
    }
    int c = 0;
    b[0] = 0;
    for (int i = 1; i <= n; ++i) {
        if (b[c] < a[i]) b[++c] = a[i];
        else {
            int l = 1, r = c;
            while (l < r) {
                int mid = (l + r) / 2;
                if (a[i] < b[mid]) r = mid;
                else l = mid + 1;
            }
            b[l] = a[i];
        }
    }
    cout << c;

    return 0;
}

DP

int n, a[N] = {0}, dp[N];
signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        dp[i] = 1;
        for (int j = 1; j < i; ++j) {
            dp[i] = (a[i] > a[j] ? max(dp[i], dp[j] + 1) : dp[i]);
        }
    }

    sort(dp + 1, dp + 1 + n);
    cout << dp[n];

    return 0;
}

最长公共子序列（LCS）

\text{板子 P1439}

没有代码，因为我没写，挂在这只是提醒自己要写这题。

最长公共上升子序列（LCIS）

\text{板子 CF10D}

同样没写。

数据结构

树状数组

单点修改 区间查询

\text{板子 P3374}

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

const int N = 1e6 + 9;

int n, m, opt, a[N], l, r, t[N];

inline void build() {
    for (int i = 1; i <= n; ++i) {
        t[i] += a[i];
        int j = i + lowbit(i);
        if (j <= n) t[j] += t[i];
    }
}

inline void upd(int x, int v) {
    a[x] += v;
    for (int i = x; i <= n; i += lowbit(i)) {
        t[i] += v;
    }
}

int query(int l, int r) {
    int ans = 0;
    while (r >= l) {
        ans += a[r];
        r--;
        for (; r - lowbit(r) >= l; r -= lowbit(r)) {
            ans += t[r];
        }
    }
    return ans;
}

int main() {    

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build();
    while (m--) {
        cin >> opt >> l >> r;
        if (opt == 1) {
            upd(l, r);
        }
        else cout << query(l, r) << '\n';
    }

    return 0;
}

区间修改 单点查询

\text{板子 P3368}

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

const int N = 1e6 + 9;

int n, m, opt, a[N], l, r, t[N], k;

inline void upd2(int l, int r, int k) { // 区间修改
    for (int i = l; i <= n; i += lowbit(i)) {
        t[i] += k;
    }
    for (int i = r + 1; i <= n; i += lowbit(i)) {
        t[i] -= k;
    }
}

int query1(int k) {
    int ans = 0;
    while (k > 0) {
        ans += t[k];
        k -= lowbit(k);
    }
    return ans;
}

int main() {        

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    while (m--) {
        cin >> opt;
        if (opt == 1) {
            cin >> l >> r >> k;
            upd2(l, r, k);
        }
        else {
            cin >> k;
            cout << a[k] + query1(k) << '\n';
        }
    }

    return 0;
}
int lowbit(int k) {return k & (-k);}

const int N = 1e6 + 9;

int n, m, opt, a, l, r, t[N], k;

inline void upd1(int x, int v) { // 单点修改
    for (int i = x; i <= n; i += lowbit(i)) {
        t[i] += v;
    }
}
inline void upd2(int l, int r, int k) { // 区间修改
    for (int i = l; i <= n; i += lowbit(i)) {
        t[i] += k;
    }
    for (int i = r + 1; i <= n; i += lowbit(i)) {
        t[i] -= k;
    }
}
int query(int k) {
    int ans = 0;
    while (k > 0) {
        ans += t[k];
        k -= lowbit(k);
    }
    return ans;
}

signed main() {
//int main() {      

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    int lst = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a;
        upd1(i, a - lst);
        lst = a;
    }
    while (m--) {
        cin >> opt;
        if (opt == 1) {
            cin >> l >> r >> k;
            upd2(l, r, k);
        }
        else {
            cin >> k;
            cout << query(k) << '\n';
        }
    }

    return 0;
}

区间修改 区间查询

\text{板子 LOJ132}

没写。

并查集

\text{板子 P3367}

const int N = 1e6 + 9;

int n, m, opt, x, y, f[N];

int find(int x) {
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

int main() {        

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
    }
    while (m--) {
        cin >> opt >> x >> y;
        if (opt == 1) {
            f[find(x)] = find(y);
        }
        else {
            cout << (find(x) == find(y) ? "Y\n" : "N\n");
        }
    }

    return 0;
}

拓扑排序（邻接表）

\text{板子 B3644}

int n, p, ind[N], vis[N];
vector<int> g[N];
queue<int> q;

void tps() {
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) {
            q.push(i);
            vis[i] = 1;
        }
    }
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        cout << t << ' ';
        for (auto v : g[t]) {
            if (!vis[v]) {
                ind[v]--;
                if (!ind[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {  
        while (1) {
            cin >> p;
            if (!p) break;
            g[i].push_back(p);
            ind[p]++;
        }
    }
    tps();

    return 0;
}

图的存储与出边排序

\text{板子 B3613}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 1145141;

ll n, m, u, v, t;
vector<ll> g[N];

int main() {

    scanf("%lld", &t);
    while (t--){
        for (ll i = 0; i <= n; ++i) g[i].clear();
        scanf("%lld %lld", &n, &m);
        for (ll i = 1; i <= m; ++i) {
            scanf("%lld %lld", &u, &v);
            g[u].push_back(v);
        }
        for (ll i = 1; i <= n; ++i) {
            sort(g[i].begin(), g[i].end());
            for (ll j = 0; j < g[i].size(); ++j) {
                printf("%lld ", g[i][j]);
            }
            puts("");
        }
    }
    return 0;
}

存图（邻接矩阵 + 邻接表）

\text{板子 B3643}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 11451;

ll n, m, u, v;
vector<ll> g[N];
bool a[N][N];

void dfs(char p) {

    if (p != '*'){
        printf("%c", p);
        for (ll i = 1; i <= n; ++i) {
            if (a[i][0] == n) {
                dfs(a[i][1]);
                dfs(a[i][2]);
            }
        }
    }
}

int main() {

    memset(a, 0, sizeof a);
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= m; ++i) {
        scanf("%lld %lld", &u, &v);
        a[u][v] = 1;
        a[v][u] = 1;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll i = 1; i <= n; ++i) {
        for (ll j = 1; j <= n; ++j) {
            printf("%d ", a[i][j]);
        }
        puts("");
    }
    for (ll i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
        printf("%lld ", g[i].size());
        for (ll j = 0; j < g[i].size(); ++j) {
            printf("%lld ", g[i][j]);
        }
        puts("");
    }

    return 0;
}

图遍历 + 回溯

\text{板子 AT\_abc284\_e}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 1145141, MAXN = 1e6; 

ll n, m, u, v, ans = 0;
vector<ll> g[N];
bool vis[N];

void dfs(ll a){
    if (ans == MAXN) return;
    ++ans;
    for (ll i = 0; i < g[a].size(); ++i) {
        ll v = g[a][i];
        if (vis[v]) continue;
        vis[v] = 1;
        dfs(v);
        vis[v] = 0;
    }
}

int main() {

    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= m; ++i) {
        scanf("%lld %lld", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(vis, 0, sizeof vis);
    vis[1] = 1;
    dfs(1);
    printf("%lld", ans);

    return 0;
}

图遍历（DFS）

\text{板子 B3862}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 1145141;

ll n, m, maxn = 0, u, v;
vector<ll> g[N];
bool vis[N];
void dfs(ll p, ll k) {
    vis[p] = 1;
    maxn = max(maxn, p);
    if (n == k) return;
    for (ll i = 0; i < g[p].size(); ++i) {
        if (!vis[g[p][i]]) dfs(g[p][i], k + 1);
    }
}

int main() {

    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= m; ++i) {
        scanf("%lld %lld", &u, &v);
        g[u].push_back(v);
    }
    for (ll i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
    }
    for (ll i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof vis);
        maxn = 0;
        dfs(i, 0);
        printf("%lld ", maxn);
    }

    return 0;
}

二叉树 DFS

\text{板子 P4913}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 1145141;

ll n;
struct Tree{
    ll l, r;
}tree[N];
ll maxn = 0;

void dfs(ll p, ll d) {
    maxn = max(maxn, d); 
    if (tree[p].l != 0) dfs(tree[p].l, d + 1);
    if (tree[p].r != 0) dfs(tree[p].r, d + 1);
}

int main() {

    scanf("%lld", &n);
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld %lld", &tree[i].l, &tree[i].r);
    }
    dfs(1, 1);
    printf("%lld", maxn);

    return 0;
}

\text{板子 P1305}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 11451;

ll n;
char a[N][N];

void dfs(char p) {

    if (p != '*'){
        printf("%c", p);
        for (ll i = 1; i <= n; ++i) {
            if (a[i][0] == p) {
                dfs(a[i][1]);
                dfs(a[i][2]);
            }
        }
    }
    return;
}

int main() {

    scanf("%lld", &n);
    for (ll i = 1; i <= n; ++i) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    dfs(a[1][0]);

    return 0;
}

二叉树遍历

\text{板子 B3642}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 1145141;

struct Tree {
    ll l, r;
}tree[N];
ll n;
void dfs(ll n) {
    printf("%lld ", n);
    if(tree[n].l != 0) dfs(tree[n].l);
    if(tree[n].r != 0) dfs(tree[n].r);
}
void dfs2(ll n) {
    if(tree[n].l != 0) dfs2(tree[n].l);
    printf("%lld ", n);
    if(tree[n].r != 0) dfs2(tree[n].r);
}
void dfs3(ll n) {
    if(tree[n].l != 0) dfs3(tree[n].l);
    if(tree[n].r != 0) dfs3(tree[n].r);
    printf("%lld ", n);
}

int main() {

    scanf("%lld", &n);
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld %lld", &tree[i].l, &tree[i].r);
    }
    dfs(1);
    puts("");
    dfs2(1);
    puts("");
    dfs3(1);

    return 0;
}

DFS + BFS

\text{板子 P5318}

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll;

const ll N = 1145141;

ll n, m, maxn = 0, u, v;
vector<ll> g[N];
bool vis[N];
queue<ll> k;
void dfs(ll k, ll en){
    vis[k] = 1;
    cout << k << ' ';
    if (n == en) return;
    for (ll i = 0; i < g[k].size(); ++i) {
        if (!vis[g[k][i]]) dfs(g[k][i], en + 1);
    }
}
void bfs(ll p) {
    vis[p] = 1;
    k.push(p);
    while (!k.empty()) {
        ll h = k.front();
        k.pop();
        printf("%lld ", h);
        for (ll i = 0; i < g[h].size(); ++i) {
            if (!vis[g[h][i]]) {
                vis[g[h][i]] = 1;
                k.push(g[h][i]);
            }
        }
    }
}

int main() {

    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= m; ++i) {
        scanf("%lld %lld", &u, &v);
        g[u].push_back(v);
    }
    for (ll i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
    }
    dfs(1, 0);
    puts("");
    memset(vis, 0, sizeof vis);
    bfs(1);

    return 0;
}

线段树（区间加 + 区间求和）

\text{板子 P3373}

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 9;

int d[N], a[N], v[N], b[N];

void build(int s, int t, int p) {
    if (s == t) {
        d[p] = a[s];
        return;
    }
    int m = s + ((t - s) >> 1);
    build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
void upd(int l, int r, int c, int s, int t, int p) {
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c, b[p] += c;
        return;
    }
    int m = s + ((t - s) >> 1);
    if (b[p] && s != t) {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    if (l <= m) upd(l, r, c, s, m, p * 2);
    if (r > m) upd(l, r, c, m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return d[p];
    int m = s + ((t - s) >> 1);
    if (b[p]) {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    int sum = 0;
    if (l <= m) sum = getsum(l, r, s, m, p * 2);
    if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
    return sum;
}

int opt, l, r, k, n, m;

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, n, 1);
    while (m--) {
        cin >> opt >> l >> r;
        if (opt == 1) {
            cin >> k;
            upd(l, r, k, 1, n, 1);
        }
        else {
            cout << getsum(l, r, 1, n, 1) << '\n';
        }
    }

    return 0;
}

数学

快速幂

int fp(int a, int b) {
    int r = 1;
        while (b > 0) {
        if (b & 1) r = r * a;
        a = a * a;
        b >>= 1;
    }
    return r;
}

快速幂 + 取模

\text{板子 P1226}

int fpm(int a, int b, int m) {
    a %= m;
    int x = 1;
    while (b > 0) {
        if (b & 1) x = x * a % m;
        a = a * a % m;
     b >>= 1;
  }
  return x;
}

龟乘

int mul(int x, int y, int p) {
    int res = 0;
    while (y) {
    if (y & 1) res = (res + x) % p;
    x = (x + x) % p;
        y >>= 1;
    }
    return res;
}

质数

复杂度 O(\sqrt n) 算法

\text{板子 P5736}

bool pri(int n){
    if (!n || n == 1) return 0;
    for (int i = 2; i <= sqrt(n); i++)
        if (!(n % i)) return 0;
    return 1;
}

线性筛

\text{板子 P3383}

bool isprime[100000010];
int prime[6000010], cnt = 0;
void pri(int n) {
    memset(isprime, 1, sizeof isprime);
    isprime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (isprime[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

Miller Rabin 算法（O(k \log n)）

\text{板子 SP288}

namespace mr {
    const int mprime[] = {2, 3, 5, 7, 11, 13, 17, 37};
    int mul(int x, int y, int p) {
        int res = 0;
        while (y) {
            if (y & 1) res = (res + x) % p;
            x = (x + x) % p;
            y >>= 1;
        }
        return res;
    }
    int qpow(int x, int y, int p) {
        int res = 1;
        while (y) {
            if (y & 1) res = mul(res, x, p);
            x = mul(x, x, p);
            y >>= 1;
        }
        return res;
    }
    bool mil(int n, int a) {
        int d = n - 1, r = 0;
        while (!(d & 1)) d >>= 1, r++;
        int z = qpow(a, d, n);
        if (z == 1) return 1;
        for (int i = 0; i < r; i++) {
            if (z == n - 1) return 1;
            z = mul(z, z, n);
        }
        return 0;
    }
    bool milpri(int n) {
        if (n <= 1) return 0;
        for (int i = 0; i < 8; i++) {
            if (n == mprime[i]) return 1;
            if (!(n % mprime[i])) return 0;
            if (!mil(n, mprime[i])) return 0;
        }
        return 1;
    }
}
using namespace mr;

组合数

int com(int n, int m) {
    int res = 1;
    for (int i = 1; i <= m; ++i){
        res = res * (n - m + i) / i;
    }
    return res;
}

卢卡斯定理

\mathrm C ^ m _ n \bmod p = \mathrm C ^ {\left\lfloor \frac{m}{p} \right\rfloor} _ {\left\lfloor \frac{n}{p} \right\rfloor} \times \mathrm C ^ {m \bmod p} _ {n \bmod p} \bmod p (p \in \mathbf P) 
int c(int n, int m){
    if (n < m) return 0;
    if (m > n - m) m = n - m;
    int a = 1, b = 1;
    for (int i = 0; i < m; i++) {
        a = (a * (n - i)) % mod;
        b = (b * (i + 1)) % mod;
    }
    return a * fpm(b, mod - 2, mod);
}
int lucas(int n, int m) {
    if (!m) return 1;
    return (c(n % mod, m % mod) * lucas(n / mod, m / mod)) % mod;
}

欧拉函数

我记得我做过一道欧拉函数的题，但我忘了是哪题了 /kk。

int phi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; ++i) {
        if (!(n % i)) {
            ans = ans / i * (i - 1);
            while (!(n % i)) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

扩展欧几里得

\text{板子 P1082}

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

线性求 [1,n] 每个数在模 p 意义下的逆元

\text{板子 P3811}

#define int long long

const int N = 1e7;

int n, p, inv[N];

signed main() {
    scanf("%lld %lld", &n, &p);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (int)(p - p / i) * inv[p % i] % p;

    }
    for (int i = 1; i <= n; ++i) printf("%lld\n", inv[i]);

    return 0;
}

中国剩余定理

\begin{cases} x \equiv a_1 \pmod{r_1}\\ x \equiv a_2 \pmod{r_2}\\ x \equiv a_3 \pmod{r_3}\\ ... \end{cases} 
void exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}
int crt(int k, int* a, int* r) {// k 为方程数
    int n = 1, ans = 0;
    for (int i = 1; i <= k; i++) n = n * r[i];
    for (int i = 1; i <= k; i++) {
        int m = n / r[i], b, y;
        exgcd(m, r[i], b, y);
        ans = (ans + a[i] * m * b % n) % n;
    }
    return (ans % n + n) % n;
}

裴蜀定理

\text{板子 P4549}

关于 x, y\in \N_+ 的不定方程 ax+by=c 有整数解的充要条件为 \gcd(a, b) | c。

对于此题，方程为 X_1A_1+X_2A_2+...+X_nA_n=S，那么 S 的最小值为 \displaystyle \gcd ^ n _ {i = 1} A_i。


int t, a, ans = 0;

int main() {
    cin >> t;
    while (t--) {
        cin >> a;
        ans = __gcd(ans, abs(a));
    }
    cout << ans;
    return 0;
}

自适应辛普森

\text{板子 P4525} \text{\&\&} \text{P4526}

double f(double x) {
    return f(x);//被积函数
}
double simpson(double l, double r) {
    double mid = (l + r) / 2;
    return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;
}

double asr(double l, double r, double eps, double ans, int step) {
    double mid = (l + r) / 2;
    double fl = simpson(l, mid), fr = simpson(mid, r);
    if (abs(fl + fr - ans) <= 15 * eps && step < 0)
    return fl + fr + (fl + fr - ans) / 15;
    return asr(l, mid, eps / 2, fl, step - 1) + asr(mid, r, eps / 2, fr, step - 1);
}

double calc(double l, double r, double eps) {
  return asr(l, r, eps, simpson(l, r), 12);
}

高精度

没有，因为我高精度的题都是 Python 过的，几百年后再更 /kk。

杂

快读快写 1

inline ll read() {
    ll n = 0;
    int f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        n = (n << 3) + (n << 1) + (c ^ 48);
        c = getchar();
    }
    return n * f;
}
inline void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x>9) write(x / 10);
    putchar(x % 10 ^ 48);
    return;
}

快读快写 2

压行了，但懒得修。

char buf[1 << 21], *p1, *p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll read() {ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x * f;}
inline void print(ll x, char ch = 0) {if (x < 0) putchar('-'), print(-x);else {if (x >= 10) print(x / 10);putchar(x % 10 + '0');}if (ch) putchar(ch);return;}

快读快写 3

不知道从哪 Copy 来的。

用 fin fout 代替 cin cout。

namespace fastio {
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
        IN& operator>>(__int128 &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        IN& operator>>(long double &a){getDouble(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        OUT& operator<<(__int128 a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        OUT& operator<<(long double a){putDouble(a);return *this;}
        ~OUT(){flush();}
    };
}
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;

__int128 输入输出

inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar(); 
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        print(x/10);
    }
    putchar(x%10+'0');
}

输入大数并取模

关流慎用。

int read(int md) {
    int x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ '0');
        if (x >= md) x %= md, f = 1;
        c = getchar();
    }
    if (f) x += md;
    return x;
}

威佐夫博弈

设两堆石子的石子数分别为 x,y，设 w=(\text{int})(\dfrac{\sqrt 5 + 1}{2}\times |x-y|)，若 w = \min(x,y)，则先手输，反之先手赢。

\text{板子 P2252}

#include <bits/stdc++.h>

using namespace std;

int x, y, w, p;

int main() {

    cin >> x >> y;
    p = abs(x - y);
    w = (int)(p * ((sqrt(5) + 1) / 2));
    if (w == min(x, y)) cout << 0;
    else cout << 1;

}

似乎是很厉害的快读快写

从别人代码整过来的，我太菜了看不懂。

C++17 以上版本可用。

似乎只能在 Linux 下才能过编？

namespace fastio {
    #include <sys/mman.h>
    #include <sys/stat.h>
    #ifndef __OY_LINUXIO__
    #define __OY_LINUXIO__
    #ifdef __unix__
    #endif
    #if __cpp_constexpr >= 201907L
    #define CONSTEXPR20 constexpr
    #define INLINE20 constexpr
    #else
    #define CONSTEXPR20
    #define INLINE20 inline
    #endif
    #define cin OY::LinuxIO::InputHelper<>::get_instance()
    #define cout OY::LinuxIO::OutputHelper::get_instance()
    #define endl '\n'
    #ifndef INPUT_FILE
    #define INPUT_FILE "in.txt"
    #endif
    #ifndef OUTPUT_FILE
    #define OUTPUT_FILE "out.txt"
    #endif
    namespace OY {
        namespace LinuxIO {
            static constexpr size_t INPUT_BUFFER_SIZE = 1 << 26, OUTPUT_BUFFER_SIZE = 1 << 20;
    #ifdef OY_LOCAL
            static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
    #else
            static constexpr char input_file[] = "", output_file[] = "";
    #endif
            template <typename U, size_t E>
            struct TenPow {
                static constexpr U value = TenPow < U, E - 1 >::value * 10;
            };
            template <typename U>
            struct TenPow<U, 0> {
                static constexpr U value = 1;
            };
            struct InputPre {
                uint32_t m_data[0x10000];
                CONSTEXPR20 InputPre() {
                    std::fill(m_data, m_data + 0x10000, -1);
                    for (size_t i = 0, val = 0; i != 10; i++)
                        for (size_t j = 0; j != 10; j++) m_data[0x3030 + i + (j << 8)] = val++;
                }
            };
            struct OutputPre {
                uint32_t m_data[10000];
                CONSTEXPR20 OutputPre() {
                    uint32_t *c = m_data;
                    for (size_t i = 0; i != 10; i++)
                        for (size_t j = 0; j != 10; j++)
                            for (size_t k = 0; k != 10; k++)
                                for (size_t l = 0; l != 10; l++) *c++ = i + (j << 8) + (k << 16) + (l << 24) + 0x30303030;
                }
            };
            template < size_t MMAP_SIZE = 1 << 30 >
            struct InputHelper {
                static INLINE20 InputPre pre{};
                struct stat m_stat;
                char *m_p, *m_c, *m_end;
                InputHelper(FILE *file = stdin) {
    #ifdef __unix__
                    auto fd = fileno(file);
                    fstat(fd, &m_stat);
                    m_c = m_p = (char *)mmap(nullptr, m_stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
                    m_end = m_p + m_stat.st_size;
    #else
                    uint32_t size = fread(m_c = m_p = new char[INPUT_BUFFER_SIZE], 1, INPUT_BUFFER_SIZE, file);
                    m_end = m_p + size;
    #endif
                }
                static InputHelper<MMAP_SIZE> &get_instance() {
                    static InputHelper<MMAP_SIZE> s_obj(*input_file ? fopen(input_file, "rt") : stdin);
                    return s_obj;
                }
                template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
                InputHelper & operator>>(Tp &x) {
                    x = 0;
                    while (!isdigit(*m_c)) m_c++;
                    x = *m_c++ ^ '0';
                    while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) x = x * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
                    if (isdigit(*m_c)) x = x * 10 + (*m_c++ ^ '0');
                    return *this;
                }
                template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
                InputHelper & operator>>(Tp &x) {
                    typename std::make_unsigned<Tp>::type t{};
                    bool sign{};
                    while (!isdigit(*m_c)) sign = (*m_c++ == '-');
                    t = *m_c++ ^ '0';
                    while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) t = t * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
                    if (isdigit(*m_c)) t = t * 10 + (*m_c++ ^ '0');
                    x = sign ? -t : t;
                    return *this;
                }
                InputHelper &operator>>(char &x) {
                    while (*m_c <= ' ') m_c++;
                    x = *m_c++;
                    return *this;
                }
                InputHelper &operator>>(std::string &x) {
                    while (*m_c <= ' ') m_c++;
                    char *c = m_c;
                    while (*c > ' ') c++;
                    x.assign(m_c, c - m_c), m_c = c;
                    return *this;
                }
                InputHelper &operator>>(std::string_view &x) {
                    while (*m_c <= ' ') m_c++;
                    char *c = m_c;
                    while (*c > ' ') c++;
                    x = std::string_view(m_c, c - m_c), m_c = c;
                    return *this;
                }
            };
            struct OutputHelper {
                static INLINE20 OutputPre pre{};
                FILE *m_file;
                char m_p[OUTPUT_BUFFER_SIZE], *m_c, *m_end;
                OutputHelper(FILE *file = stdout) {
                    m_file = file;
                    m_c = m_p, m_end = m_p + OUTPUT_BUFFER_SIZE;
                }
                ~OutputHelper() {
                    flush();
                }
                static OutputHelper &get_instance() {
                    static OutputHelper s_obj(*output_file ? fopen(output_file, "wt") : stdout);
                    return s_obj;
                }
                void flush() {
                    fwrite(m_p, 1, m_c - m_p, m_file), m_c = m_p;
                }
                OutputHelper &operator<<(char x) {
                    if (m_end - m_c < 20) flush();
                    *m_c++ = x;
                    return *this;
                }
                OutputHelper &operator<<(std::string_view s) {
                    if (m_end - m_c < s.size()) flush();
                    memcpy(m_c, s.data(), s.size()), m_c += s.size();
                    return *this;
                }
                OutputHelper &operator<<(uint64_t x) {
                    if (m_end - m_c < 20) flush();
    #define CASEW(w)                                                           \
    case TenPow<uint64_t, w - 1>::value... TenPow<uint64_t, w>::value - 1: \
        *(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, w - 4>::value]; \
        m_c += 4, x %= TenPow<uint64_t, w - 4>::value;
                    switch (x) {
                            CASEW(19);
                            CASEW(15);
                            CASEW(11);
                            CASEW(7);
                        case 100 ... 999:
                            *(uint32_t *)m_c = pre.m_data[x * 10];
                            m_c += 3;
                            break;
                            CASEW(18);
                            CASEW(14);
                            CASEW(10);
                            CASEW(6);
                        case 10 ... 99:
                            *(uint32_t *)m_c = pre.m_data[x * 100];
                            m_c += 2;
                            break;
                            CASEW(17);
                            CASEW(13);
                            CASEW(9);
                            CASEW(5);
                        case 0 ... 9:
                            *m_c++ = '0' + x;
                            break;
                        default:
                            *(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, 16>::value];
                            m_c += 4;
                            x %= TenPow<uint64_t, 16>::value;
                            CASEW(16);
                            CASEW(12);
                            CASEW(8);
                        case 1000 ... 9999:
                            *(uint32_t *)m_c = pre.m_data[x];
                            m_c += 4;
                            break;
                    }
    #undef CASEW
                    return *this;
                }
                OutputHelper &operator<<(uint32_t x) {
                    if (m_end - m_c < 20) flush();
    #define CASEW(w)                                                           \
    case TenPow<uint32_t, w - 1>::value... TenPow<uint32_t, w>::value - 1: \
        *(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, w - 4>::value]; \
        m_c += 4, x %= TenPow<uint32_t, w - 4>::value;
                    switch (x) {
                        default:
                            *(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, 6>::value];
                            m_c += 4;
                            x %= TenPow<uint32_t, 6>::value;
                            CASEW(6);
                        case 10 ... 99:
                            *(uint32_t *)m_c = pre.m_data[x * 100];
                            m_c += 2;
                            break;
                            CASEW(9);
                            CASEW(5);
                        case 0 ... 9:
                            *m_c++ = '0' + x;
                            break;
                            CASEW(8);
                        case 1000 ... 9999:
                            *(uint32_t *)m_c = pre.m_data[x];
                            m_c += 4;
                            break;
                            CASEW(7);
                        case 100 ... 999:
                            *(uint32_t *)m_c = pre.m_data[x * 10];
                            m_c += 3;
                            break;
                    }
    #undef CASEW
                    return *this;
                }
                OutputHelper &operator<<(int64_t x) {
                    if (x >= 0)
                        return (*this) << uint64_t(x);
                    else
                        return (*this) << '-' << uint64_t(-x);
                }
                OutputHelper &operator<<(int32_t x) {
                    if (x >= 0)
                        return (*this) << uint32_t(x);
                    else
                        return (*this) << '-' << uint32_t(-x);
                }
            };
        }
    }
    #endif
}

火车头

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")