头像

封禁用户

新初一蒟蒻QwQ求$\Huge\color{red}{AK}$呜呜呜 $$CSP2022 \color{red}{RP++}$$




离线:4小时前


最近来访(15574)
用户头像
獨洎蕜傷
用户头像
Noyce765103
用户头像
迎风飘扬
用户头像
hanyucan
用户头像
憨憨_40
用户头像
AcWing2AK
用户头像
Jackle
用户头像
Finn2009
用户头像
高瑞琪
用户头像
封禁用户1
用户头像
顶顶.
用户头像
偷了初十兵战
用户头像
夏语聪
用户头像
云衣醉梦
用户头像
天元之弈
用户头像
林科大
用户头像
Mr.watanuo
用户头像
道理都懂就不ac
用户头像
lmagawaujizane
用户头像
754839

活动打卡代码 AcWing 1. A + B

封禁用户
13小时前

为了误导初学者
先放一波正常代码:

/*
             A          K         K         CCCCCCCCCCCC SSSSSSSSSSS  PPPPPPPPPPPPP
            A A         K       K          C             S            P           P
           A   A        K     K           C              S            P           P
          A     A       K   K            C               S            P           P
         A       A      K K              C               SSSSSSSSSSS  PPPPPPPPPPPPP
        AAAAAAAAAAA     K   K            C                         S  P
       A           A    K     K           C                        S  P
      A             A   K       K          C                       S  P
     A               A  K         K         CCCCCCCCCCC  SSSSSSSSSSS  P


             A          K         K         IIIIIIIIIII    OOOOOOOOOOO    IIIIIIIIIII
            A A         K       K                I         O         O         I
           A   A        K     K                  I         O         O         I
          A     A       K   K                    I         O         O         I
         A       A      K K                      I         O         O         I
        AAAAAAAAAAA     K   K                    I         O         O         I
       A           A    K     K                  I         O         O         I
      A             A   K       K                I         O         O         I
     A               A  K         K         IIIIIIIIIII    OOOOOOOOOOO    IIIIIIIIIII
*/
#include <bits/stdc++.h>
using namespace std;
int a, b;                   //定义两个整型变量a和b
int main() {
    scanf("%d%d", &a, &b);  //读入a和b,当然用cin也没毛病
    printf("%d\n", a + b);  //输出a+b,当然用cout也没毛病
    return 0;
} 





































这个引用表示强调……

首先声明此题非常困(jian)(dan),连国(ru)(men)(cai)(niao)都做不(de)出,我想了1年(miao)(jiu)把这题想出来了。

$\Huge此帖强烈建议收藏$

点赞的童鞋们!

身体健康万事如意周赛AK题解爆赞期末考试三科满分!

搞恶!

搞恶!

非常搞恶!

是不是只有我把这道题标注成困难啊……

A+B尝试代码快捷键点这里!!!!!!

在各位大佬的建议下,我又写了这个帖子hhh……
前方高能!!!警告!!!

本文长度恐怖!比上次还恐怖!请各位大佬蒟蒻们小心!

建议慢慢食用


y总一定全看得懂……必须的
其实有四五个算法是查的但是我也懵了……

算法一、DFS一号

#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
int dfs(int x, int sum) {
    if (x > n) return sum;
    int i = dfs(x + 1, sum);
    int j = dfs(x + 1, sum + a[x]);
    if (i == s) return i;
    if (j == s) return j;
    return -1;
}
int main() {
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]), s += a[i];
    cout << dfs(1, 0) << endl;
    return 0;
}

算法二、DFS二号

#include <bits/stdc++.h>
using namespace std;
int a, b;
int dfs(int x) {
    if (x <= 5) return x;
    return dfs(x / 2) + dfs(x - x / 2);
} 
int main() {
    scanf("%d%d", &a, &b);
    printf("%d\n", dfs(a) + dfs(b));
    return 0;
}

算法三、BFS

#include <bits/stdc++.h>
using namespace std;
int n = 2, a[5], s;
queue<int> q;
void bfs() {
    q.push(0);
    int c = 0;
    while (q.size()) {
        c++;
        int f = q.front(); q.pop();
        if (f == s) {printf("%d\n", f); exit(0);}
        q.push(f + a[c]);
        q.push(f);
    }
}
int main() {
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]), s += a[i];
    bfs();
    return 0;
}

算法四、直接算咯

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
} 

算法五、二分

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    int l = 0, r = 200000000;
    while (l < r) {
        int mid = l + r >> 1;
        if (mid == a + b) {printf("%d\n", mid); return 0;}
        if (mid <  a + b) l = mid + 1;
        if (mid >  a + b) r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

算法六、稍微有点暴力的枚举

但是还是$1892ms$卡过了欸

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    for (int i = 0;i <= 200000000; i++) if (a + b == i) {printf("%d\n", i); break;}
    return 0;
} 

算法七、最短路之dijkstra

思路:定义节点1到节点2路径长度为a,节点2到节点3路径长度为b
则答案为节点1到节点3的最短路(也就是$a+b$)

#include <bits/stdc++.h>
using namespace std;
int w[5][5], d[5], v[5];
int n = 3;
void dijkstra() {
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0;
    for (int i = 1;i < n; i++) {
        int x = 0;
        for (int j = 1;j <= n; j++)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1;y <= n; y++)
            d[y] = min(d[y], d[x] + w[x][y]);
    }
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    memset(w, 0x3f, sizeof w);
    w[1][2] = a; w[2][3] = b;
    dijkstra();
    printf("%d\n", d[3]);
    return 0;
}

算法八、最短路之SPFA

思路同上

#include <bits/stdc++.h>
using namespace std;
int a, b, n = 3;
int w[5][5], d[5], v[5];
queue<int> q;
void spfa() {
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0, v[1] = 1;
    q.push(1);
    while (q.size()) {
        int x = q.front(); q.pop();
        v[x] = 0;
        for (int i = 1;i <= n; i++) {
//          if (w[x][i] == 0x3f) continue;
            if (d[i] > d[x] + w[x][i]) {
                d[i] = d[x] + w[x][i];
                if (!v[i]) q.push(i), v[i] = 1;
            }
        }
    }
}
int main() {
    scanf("%d%d", &a, &b);
    memset(w, 0x3f, sizeof w);
    w[1][2] = a; w[2][3] = b;
    spfa();
    printf("%d\n", d[3]);
    return 0;
}

算法九、最短路之Floyd

思路同上

#include <bits/stdc++.h>
using namespace std;
int d[5][5], n = 3;
int main() {
    int a, b; scanf("%d%d", &a, &b);
    memset(d, 0x3f, sizeof d);
    d[1][2] = a; d[2][3] = b;
    for (int k = 1;k <= n; k++)
        for (int i = 1;i <= n; i++)
            for (int j = 1;j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    printf("%d\n", d[1][3]);
    return 0;
}

算法十、高精

#include<bits/stdc++.h>
using namespace std;
string a0, b0;
int a[1005], b[1005];
int main(){
    cin >> a0 >> b0;
    int l1 = a0.size(), l2 = b0.size();
    for (int i = 0;i < l1; i++) a[l1 - i] = a0[i] - 48;
    for (int i = 0;i < l2; i++) b[l2 - i] = b0[i] - 48;
    l1 = max(l1, l2);
    for (int i = 1;i <= l1; i++) {
        a[i] += b[i];
        if (a[i] > 9) a[i + 1] += 1, a[i] %= 10;
    }
    if (a[max(l1, l2) + 1] > 0) l1++;
    for (int i = l1;i >= 1; i--) printf("%d", a[i]);
    return 0;
}

算法十一、最小生成树之kruskal

思路其实和最短路的一样,只是改成用最小生成树的方法求罢了

#include <bits/stdc++.h>
using namespace std;
struct rec {
    int x, y, z;
} edge[5];

int fa[5], m = 2, ans = 0;

int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}
int cmp(rec a, rec b) { return a.z < b.z; }

int main() {
    int a, b; scanf("%d%d", &a, &b);
    edge[1] = (rec){1, 2, a};
    edge[2] = (rec){2, 3, b};
    for (int i = 1;i <= m + 1; i++) fa[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1;i <= m; i++) {
        int x = get(edge[i].x);
        int y = get(edge[i].y);
        if (x == y) continue;
        fa[x] = y;
        ans += edge[i].z;
    }
    printf("%d\n", ans);
    return 0;
}

算法十二、最小生成树之prim

思路同上

#include <bits/stdc++.h>
using namespace std;
int w[5][5], d[5], n = 3, ans, v[5];

void prim() {
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0;
    for (int i = 1;i < n; i++) {
        int x = 0;
        for (int j = 1;j <= n; j++)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1;y <= n; y++)
            if (!v[y]) d[y] = min(d[y], w[x][y]);
    }
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    memset(w, 0x3f, sizeof w);
    w[1][2] = a; w[2][3] = b;
    prim();
    int ans = 0;
    for (int i = 2;i <= n; i++) ans += d[i];
    printf("%d\n", ans);
    return 0;
}

算法十三、前缀和

#include <bits/stdc++.h>
using namespace std;
int a[5], s[5];
int main() {
    for (int i = 1;i <= 2; i++) scanf("%d", &a[i]), s[i] += a[i] + s[i - 1];
    printf("%d\n", s[2]);
    return 0;
}

算法十四、后缀和

#include <bits/stdc++.h>
using namespace std;
int a[5], s[5];
int main() {
    for (int i = 2;i >= 1; i--) scanf("%d", &a[i]), s[i] += a[i] + s[i + 1];
    printf("%d\n", s[1]);
    return 0;
}

算法十五、位运算

#include <bits/stdc++.h>
using namespace std;
int add(int a, int b) {
    if (b == 0) return a;
    return add(a ^ b, (a & b) << 1);
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%d\n", add(a, b));
    return 0;
}

算法十六、树的直径——BFS

emmm……思路继续和最短路的一样。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int head[maxn * 2],edge[maxn * 2],Next[maxn * 2],ver[maxn * 2];
int vis[maxn], dist[maxn];
int n = 3, p, q, d;
int tot = 0;
int maxd = 0;

void add(int u,int v,int w) {
    ver[ ++ tot] = v,edge[tot] = w;
    Next[tot] = head[u],head[u] = tot;
}

int BFS(int u) {
    queue<int>Q;
    while(!Q.empty()) Q.pop();
    memset(vis, 0, sizeof vis);
    memset(dist, 0, sizeof dist);  
    Q.push(u);
    int x, max_num = 0;
    while(!Q.empty()) {
        x = Q.front();
        Q.pop();
        vis[x] = 1;
        for(int i = head[x]; i ; i = Next[i]) {
            int y = ver[i];
            if(vis[y]) continue;
            vis[y] = 1;
            dist[y] = dist[x] + edge[i];
            if(dist[y] > maxd) {
                maxd = dist[y];
                max_num = y;
            }
            Q.push(y);
        }
    }
    return max_num;
}
int main(void) {
    int a, b; scanf("%d%d", &a, &b);
    add(1, 2, a); add(2, 1, a);
    add(2, 3, b); add(3, 2, b);
    BFS(BFS(1));
    int ans = 0;
    for (int i = 1;i <= n; i++) ans = max(ans, dist[i]);
    printf("%d\n", ans);
    return 0;
}

算法十七、树的直径——DFS

思路同上

#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
struct node {
    int u, v, w, nex;
} edge[2 * maxn + 10];
int n = 3, d[maxn + 10], head[maxn + 10], f_num, cnt = 0, ans;
inline void add(int x,int y,int z) {
    edge[++cnt].u = x;
    edge[cnt].v = y;
    edge[cnt].w = z;
    edge[cnt].nex = head[x];
    head[x] = cnt;
}
inline void dfs(int x, int fa) {
    if(ans < d[x]) {
        ans = d[x];
        f_num = x;
    }
    for (int i = head[x]; i != -1; i = edge[i].nex) {
        int j = edge[i].v;
        if (j == fa)continue;
        d[j] = d[x] + edge[i].w;    
        dfs(j, x);
    }
}
int main() {
    memset(head, -1, sizeof(head));
    int a, b; scanf("%d%d", &a, &b);
    add(1, 2, a); add(2, 1, a);
    add(2, 3, b); add(3, 2, b);
    dfs(1, 0);
    ans = 0;
    d[f_num] = 0;
    dfs(f_num, 0);
    for (int i = 1;i <= n; i++) ans = max(ans, d[i]);
    printf("%d", ans);
    return 0;
}

算法十八、树的直径——树形DP

还是一样咯

#include <bits/stdc++.h>
using namespace std;
int f[5], n = 3, cnt, h[5], ans, dis[5];
struct edge {
    int to, next, vi;
} e[5];
void add(int u, int v, int w) {
    e[cnt].to= v;
    e[cnt].vi = w;
    e[cnt].next = h[u];
    h[u] = cnt++;
}
void dp(int u, int fa) {
    for (int i = h[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        dp(v, u);
        ans = max(ans, dis[v] + dis[u] + e[i].vi);
        dis[u] = max(dis[u], dis[v] + e[i].vi);
    }
}
int main() {
    memset(h, -1, sizeof h);
    int a, b; scanf("%d%d", &a, &b);
    add(1, 2, a); add(2, 1, a);
    add(2, 3, b); add(3, 2, b);
    dp(1, 0);
    printf("%d\n", ans);
    return 0;
}

算法十九、网络流

从别的大佬那边搞过来的,但是一点都看不懂┭┮﹏┭┮

#include<bits/stdc++.h>
using namespace std;
#define set(x) Set(x)
#define REP(i,j,k) for (int i=(j),_end_=(k);i<=_end_;++i)
#define DREP(i,j,k) for (int i=(j),_start_=(k);i>=_start_;--i)
#define mp make_pair
#define x first
#define y second
#define pb push_back
template<typename T> inline bool chkmin(T &a,const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a,const T &b){ return a < b ? a = b, 1 : 0; }
typedef long long LL;
typedef pair<int,int> node;
const int dmax = 1010, oo = 0x3f3f3f3f;
int n, m;
int a[dmax][dmax] , ans;
int d[dmax], e[dmax];
priority_queue <node> q;
inline bool operator >(node a,node b){ return a.y>b.y; }
bool p[dmax];
void Set(int x){ p[x] = 1; }
void unset(int x){ p[x] = 0; }
bool check(int x){ return x != 1 && x != n && !p[x] && e[x] > 0; }
void preflow(){
    e[1] = oo;
    d[1] = n - 1;
    q.push(mp(1, n - 1));
    set(1);
    while (!q.empty()) {
        bool flag = 1;
        int k = q.top().x;
        q.pop(), unset(k);
        DREP(i, n, 1)
        if ((d[k] == d[i] + 1 || k == 1) && a[k][i] > 0){
            flag = 0;
            int t = min(a[k][i], e[k]);
            e[k] -= t;
            a[k][i] -= t;
            e[i] += t;
            a[i][k] += t;
            if (check(i)) {
                q.push(mp(i, d[i]));
                set(i);
            }
            if (e[k] == 0) break;
        }
        if (flag) {
            d[k] = oo;
            REP(i, 1, n)
            if (a[k][i] > 0) chkmin(d[k], d[i] + 1);
        }
        if (check(k)) {
            q.push(mp(k, d[k]));
            set(k);
        }
    }
    ans = e[n];
}
int main() {
    n = 2, m = 2;
    int x, y;
    scanf("%d%d", &x, &y);
    a[1][2] += x + y;
    preflow();
    printf("%d\n", ans);
    return 0;
}

算法二十、线段树

转化为区间求和问题

#include <bits/stdc++.h>
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
using namespace std;
struct SegmentTree {
    int l, r; //区间左右端点 
    long long sum, add; //sum 区间和  add 延迟标记 
} tree[400010];
int a[100010], n = 1, m = 2;
void build (int p, int l, int r) {
    l(p) = l, r(p) = r;
    if(l == r) {sum(p) = a[l]; return;}
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
void spread(int p) {
    if(add(p)) { //节点p有标记 
        sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1); //更新左子节点信息 
        sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1); //更新右子节点
        add(p * 2) += add(p); //给左子节点打延迟标记 
        add(p * 2 + 1) += add(p); //给右子节点打延迟标记 
        add(p) = 0; //清除p的标记 
    }
}
void change(int p, int l, int r, int d) {
    if(l <= l(p) && r >= r(p)) { //完全覆盖 
        sum(p) += (long long) d * (r(p) - l(p) + 1); //更新节点信息 
        add(p) += d; //给节点打延迟标记 
        return;
    }
    spread(p); //下传延迟标记 
    int mid = l(p) + r(p) >> 1;
    if(l <= mid) change(p * 2, l, r, d);
    if(r > mid) change(p * 2 + 1, l, r, d);
    sum(p) = sum(p * 2) + sum(p * 2 + 1);
}
long long ask(int p, int l, int r) {
    if(l <= l(p) && r >= r(p)) return sum(p);
    spread(p);
    int mid = l(p) + r(p) >> 1;
    long long val = 0;
    if(l <= mid) val += ask(p * 2, l, r);
    if(r > mid) val += ask(p * 2 + 1, l, r);
    return val;
}
int main() {
    a[1] = 0;
    build(1, 1, n);
    while(m--) { 
        int d = 0;
        scanf("%d", &d);
        change(1, 1, 1, d);
    }
    printf("%lld\n", ask(1, 1, 1));
    return 0;
}

算法二十一、树状数组

思路一样,区间求和

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100010;
int a[SIZE], n = 1, m = 2;
long long c[2][SIZE], sum[SIZE];

long long ask(int k, int x) {
    long long ans = 0;
    for(; x ; x -= x & -x) ans += c[k][x];
    return ans;
}

void add(int k,int x,int y) {
    for(; x <= n; x += x & -x) c[k][x] += y;
}

int main() {
    a[1] = 0;
    while(m--) {
        int d = 0;
        scanf("%d", &d);
        add(0, 1, d);
        add(0, 2, -d);
        add(1, 1, d);
        add(1, 2, -2 * d);
    }
    long long ans = sum[1] + 2 * ask(0, 1) - ask(1, 1);
    ans -= sum[0] + 1 * ask(0, 0) - ask(1, 0);
    printf("%lld\n", ans);
    return 0;
}

算法二十二、分块

思路一样,区间求和

#include<bits/stdc++.h>
using namespace std;
long long a[50000010], sum[50000010], add[50000010];
int L[50000010], R[50000010];
int pos[50000010];
int n = 1, m = 2, t;

void change(int l, int r, long long d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += d;
        sum[p] += d*(r - l + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++) add[i] += d;
        for (int i = l; i <= R[p]; i++) a[i] += d;
        sum[p] += d*(R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) a[i] += d;
        sum[q] += d*(r - L[q] + 1);
    }
}

long long ask(int l, int r) {
    int p = pos[l], q = pos[r];
    long long ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) ans += a[i];
        ans += add[p] * (r - l + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++)
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; i++) ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}

int main() {
    a[1] = 0;
    t = sqrt(n*1.0);
    for (int i = 1; i <= t; i++) {
        L[i] = (i - 1)*sqrt(n*1.0) + 1;
        R[i] = i*sqrt(n*1.0);
    }
    if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
        }
    while (m--) {
        int d;
        scanf("%d", &d);
        change(1, 1, d);
    }
    printf("%lld\n", ask(1, 1));
}

算法二十三、LCT

来自洛谷

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data,rev,sum;
    node *son[2],*pre;
    bool judge();
    bool isroot();
    void pushdown();
    void update();
    void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
    node *now=lct+ ++top;
    now->data=x;
    now->pre=now->son[1]=now->son[0]=lct;
    now->sum=0;
    now->rev=0;
    return now;
}
bool node::judge()
{
    return pre->son[1]==this;
}
bool node::isroot()
{
    if(pre==lct)return true;
    return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
    if(this==lct||!rev)return;
    swap(son[0],son[1]);
    son[0]->rev^=1;
    son[1]->rev^=1;
    rev=0;
}
void node::update()
{
    sum=son[1]->sum+son[0]->sum+data;
}
void node::setson(node *child,int lr)
{
    this->pushdown();
    child->pre=this;
    son[lr]=child;
    this->update();
}
void rotate(node *now)
{
    node *father=now->pre,*grandfa=father->pre;
    if(!father->isroot()) grandfa->pushdown();
    father->pushdown();
    now->pushdown();
    int lr=now->judge();
    father->setson(now->son[lr^1],lr);
    if(father->isroot()) now->pre=grandfa;
    else grandfa->setson(now,father->judge());
    now->setson(father,lr^1);
    father->update();
    now->update();
    if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
    if(now->isroot())return;
    for(; !now->isroot(); rotate(now))
    if(!now->pre->isroot())
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
    node *last=lct;
    for(; now!=lct; last=now,now=now->pre) {
        splay(now);
        now->setson(last,1);
    }
    return last;
}
void changeroot(node *now)
{
    access(now)->rev^=1;
    splay(now);
}
void connect(node *x,node *y)
{
    changeroot(x);
    x->pre=y;
    access(x);
}
void cut(node *x,node *y)
{
    changeroot(x);
    access(y);
    splay(x);
    x->pushdown();
    x->son[1]=y->pre=lct;
    x->update();
}
int query(node *x,node *y)
{
    changeroot(x);
    node *now=access(y);
    return now->sum;
}
int main()
{
    scanf("%d%d",&a,&b);
    node *A=getnew(a);
    node *B=getnew(b);
    connect(A,B);
    cut(A,B);
    connect(A,B);
    printf("%d",query(A,B));
    return 0;
}

算法二十四、Splay

来自洛谷

#include <bits/stdc++.h>
#define ll long long
#define N 100000
using namespace std;
int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N];
int n, m, rt, x;
void push_up(int x){
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    sum[x] = sum[ch[x][1]] + sum[ch[x][0]] + val[x];
}
void push_down(int x){
    if(rev[x]){
        swap(ch[x][0], ch[x][1]);
        if(ch[x][1]) rev[ch[x][1]] ^= 1;
        if(ch[x][0]) rev[ch[x][0]] ^= 1;
        rev[x] = 0;
    }
    if(tag[x]){
        if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x];
        if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x];
        tag[x] = 0;
    }
}
void rotate(int x, int &k){
    int y = fa[x], z = fa[fa[x]];
    int kind = ch[y][1] == x;
    if(y == k) k = x;
    else ch[z][ch[z][1]==y] = x;
    fa[x] = z; fa[y] = x; fa[ch[x][!kind]] = y;
    ch[y][kind] = ch[x][!kind]; ch[x][!kind] = y;
    push_up(y); push_up(x);
}
void splay(int x, int &k){
    while(x != k){
        int y = fa[x], z = fa[fa[x]];
        if(y != k) if(ch[y][1] == x ^ ch[z][1] == y) rotate(x, k);
        else rotate(y, k);
        rotate(x, k);
    }
}
int kth(int x, int k){
    push_down(x);
    int r = sz[ch[x][0]]+1;
    if(k == r) return x;
    if(k < r) return kth(ch[x][0], k);
    else return kth(ch[x][1], k-r);
}
void split(int l, int r){
    int x = kth(rt, l), y = kth(rt, r+2);
    splay(x, rt); splay(y, ch[rt][1]);
}
void rever(int l, int r){
    split(l, r);
    rev[ch[ch[rt][1]][0]] ^= 1;
}
void add(int l, int r, int v){
    split(l, r);
    tag[ch[ch[rt][1]][0]] += v;
    val[ch[ch[rt][1]][0]] += v;
    push_up(ch[ch[rt][1]][0]);
}
int build(int l, int r, int f){
    if(l > r) return 0;
    if(l == r){
        fa[l] = f;
        sz[l] = 1;
        return l;
    }
    int mid = l + r >> 1;
    ch[mid][0] = build(l, mid-1, mid);
    ch[mid][1] = build(mid+1, r, mid);
    fa[mid] = f;
    push_up(mid);
    return mid;
}
int asksum(int l, int r){
    split(l, r);
    return sum[ch[ch[rt][1]][0]];
}
int main(){
    //总共两个数
    n = 2;
    rt = build(1, n+2, 0);//建树
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        add(i, i, x);//区间加
    }
    rever(1, n);//区间翻转
    printf("%d\n", asksum(1, n));//区间求和
    return 0;
}

算法二十五、LCA

来自洛谷

#include<cstdio>                                                  //头文件
#define NI 2                                                          
//从来不喜欢算log所以一般用常数 不知道算不算坏习惯 因为3个节点 所以log3(当然以2为底)上取整得2
struct edge
{
    int to,next,data;                                              //分别表示边的终点,下一条边的编号和边的权值
}e[30];                                                                     //邻接表,点少边少开30是为了浪啊
int v[10],d[10],lca[10][NI+1],f[10][NI+1],tot=0;      //数组开到10依然为了浪
//数组还解释嘛,v表示第一条边在邻接表中的编号,d是深度,lca[x][i]表示x向上跳2^i的节点,f[x][i]表示x向上跳2^i的距离和
void build(int x,int y,int z)                                      //建边
{
    e[++tot].to=y; e[tot].data=z; e[tot].next=v[x]; v[x]=tot;
    e[++tot].to=x; e[tot].data=z; e[tot].next=v[y]; v[y]=tot;
}
void dfs(int x)                                                        //递归建树
{
    for(int i=1;i<=NI;i++)                                   //懒,所以常数懒得优化
        f[x][i]=f[x][i-1]+f[lca[x][i-1]][i-1],
        lca[x][i]=lca[lca[x][i-1]][i-1];                   //建树的同时进行预处理
    for(int i=v[x];i;i=e[i].next)                              //遍历每个连接的点
    {
        int y=e[i].to;
        if(lca[x][0]==y) continue;
        lca[y][0]=x;                                       //小技巧:lca[x][0]即为x的父亲~~(向上跳2^0=1不就是父节点嘛)
        f[y][0]=e[i].data;
        d[y]=d[x]+1;
        dfs(y);                                            //再以这个节点为根建子树【这里真的用得到嘛??】
    }
}
int ask(int x,int y)                                             //询问,也是关键
{                                                                        
    if(d[x]<d[y]) {int t=x;x=y;y=t;}                  //把x搞成深的点
    int k=d[x]-d[y],ans=0;
    for(int i=0;i<=NI;i++)
        if(k&(1<<i))                                      //若能跳就把x跳一跳
            ans+=f[x][i],                              //更新信息
            x=lca[x][i];
    for(int i=NI;i>=0;i--)                                  //不知道能不能正着循环,好像倒着优,反正记得倒着就好了
        if(lca[x][i]!=lca[y][i])                            //如果x跳2^i和y跳2^j没跳到一起就让他们跳
            ans+=f[x][i]+f[y][i],
            x=lca[x][i],y=lca[y][i];
    return ans+f[x][0]+f[y][0];                           //跳到LCA上去(每步跳的时候都要更新信息,而且要在跳之前更新信息哦~)
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    build(1,2,a);
    build(1,3,b);                                                       //分别建1 2、1 3之间的边
    dfs(1);                                                                //以1为根建树
    printf("%d",ask(2,3));                                         //求解2 3到它们的LCA的距离和并输出
}

算法二十六、字典树

来自洛谷

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
    int str[26];
    int sum;
}s[1000];
char str1[100];
int t=0,tot=0,ss=0;
bool f1;
void built()
{
    t=0;
    for(int i=0;i<strlen(str1);i++)
    {
         if(str1[i]=='-'){
             f1=true;continue;
         }
         if(!s[t].str[str1[i]-'0'])
         s[t].str[str1[i]-'0']=++tot;
         t=s[t].str[str1[i]-'0'];
         s[t].sum=str1[i]-'0';
    }
}
int query()
{
   int t=0;int s1=0;
   for(int i=0;i<strlen(str1);i++)
   {
           if(str1[i]=='-') continue;
           if(!s[t].str[str1[i]-'0']) return s1;
           t=s[t].str[str1[i]-'0'];
           s1=s1*10+s[t].sum;
   }
   return s1;
}
int main()
{    
  for(int i=1;i<=2;i++)
  {
      f1=false;
      scanf("%s",str1);
    built();
    if(f1)
      ss-=query();
      else ss+=query();
  }
  printf("%d",ss);
  return 0;    
}

嘿嘿洛谷的没有啦~

算法二十七、Bellman-Ford

思路和别的最短路解法一样~

#include <bits/stdc++.h>
using namespace std;
int dis[50], u[50], v[50], w[50], n, m;
void bellman(int start) {
    for (int i = 1;i <= n; i++) dis[i] = 0x3f3f3f3f;
    dis[start] = 0;
    for (int i = 1;i < n; i++)
        for (int j = 1;j <= m; j++)
            if (dis[v[j]] > dis[u[j]] + w[j]) dis[v[j]] = dis[u[j]] + w[j];
}
int main() {
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) cin  >> w[i], u[i] = i, v[i] = i + 1;
    bellman(1);
    printf("%d\n", dis[3]);
    return 0;
}

算法二十八、可耻的打表

#include <bits/stdc++.h>
using namespace std;
int a, b; int main() { 
    scanf("%d%d", &a, &b);
    if (a == 3 && b == 4) printf("7");
    if (a == 45 && b == 55) printf("100");
    if (a == 123 && b == 321) printf("444");
    if (a == 91086199 && b == 18700332) printf("109786531");
    if (a == 42267194 && b == 60645282) printf("102912476");
    if (a == 69274392 && b == 10635835) printf("79910227");
    if (a == 5710219 && b == 85140568) printf("90850787");
    if (a == 75601477 && b == 24005804) printf("99607281");
    if (a == 70597795 && b == 90383234) printf("160981029");
    if (a == 82574652 && b == 22252146) printf("104826798");
    return 0;           //hh,这个len没加上return 0,还是我加的……
}

算法二十九、SPFA求最短路之SLF优化

呃呃呃就是加了个SLF优化而已

#include<bits/stdc++.h>
using namespace  std;
const int maxn = 100000 + 10;
const int INF = 0x7FFFFFFF;

int pre[maxn], dis[maxn], path[maxn];
bool vis[maxn];
int head[maxn], n, m;

int tot, cnt;
struct node {
    int v, w, next;
} E[2 * maxn];
void add(int u, int v, int w) {
    E[tot].v = v;
    E[tot].w = w;
    E[tot].next = head[u];
    head[u] = tot++;
}
void init() {
    tot = 0;
    memset(vis, 0, sizeof vis);
    memset(head, -1, sizeof head);
}
void spfa(int st) {
    for (int i = 1;i <= n; i++) vis[i] = false, dis[i] = INF;
    int now, next;
    dis[st] = 0; vis[st] = 1;
    deque<int> q;
    q.push_back(st);
    pre[st] = -1;
    while(!q.empty()) {
        now = q.front();
        q.pop_front();
        vis[now] = 0;
        for (int i = head[now]; i != -1;i = E[i].next) {
            next = E[i].v;
            if(dis[next] > dis[now] + E[i].w) {
                dis[next] = dis[now] + E[i].w;
                pre[next] = now;
                if(!vis[next]) {
                        vis[next] = 1; 
                        if (q.empty() || dis[next] > dis[q.front()]) q.push_back(next);
                        else q.push_front(next);
                }
            }
        }
    }
}
void print(int x) {
    if(pre[x] == -1) return;
    print(pre[x]);
    printf("%d ", x);
}
int main() {
    init();
    n = 3; m = 2;
    int w;
    for (int i = 1;i <= m; i++) {scanf("%d", &w); add(i, i + 1, w);}
    spfa(1);
    if(dis[n] == INF) puts("-1");
    else printf("%d\n", dis[n]);
    return 0;
}

算法三十、SPFA之LLL优化

#include<bits/stdc++.h>
#define MAXN 10010
#define MAXM 500010
#define MAX 2147483647
using namespace std;
int n, m, t, c = 1;
int head[MAXN], path[MAXN];
bool vis[MAXN];
struct node {
    int next, to, w;
}a[MAXM << 1];
inline int relax (int u, int v, int w) {
    if (path[v] > path[u] + w) {
        path[v] = path[u] + w;
        return 1;
    }
    return 0;
}
inline void add(int u, int v, int w) {
    a[c].to = v;
    a[c].w = w;
    a[c].next = head[u];
    head[u] = c++;
}
void spfa() {
    int u, v, num = 0;
    long long x = 0;
    list<int> q;
    for (int i = 1;i <= n; i++){path[i] = MAX; vis[i] = 0;}
    path[1] = 0;
    vis[1] = 1;
    q.push_back(1);
    num++;
    while (!q.empty()) {
        u = q.front();
        q.pop_front();
        num--; x -= path[u];
        while (num && path[u] > x / num){
            q.push_back(u);
            u = q.front();
            q.pop_front();
        }
        vis[u] = 0;
        for (int i = head[u]; i ; i = a[i].next) {
            v = a[i].to;
            if (relax(u, v, a[i].w) && !vis[v]) {
                vis[v] = 1;
                if(!q.empty() && path[v] < path[q.front()]) q.push_front(v);
                else q.push_back(v);
                num++; x += path[v];
            }
        }
    }
}
int main() {
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) {
        int w;
        scanf("%d", &w);
        add(i, i + 1, w);
    }
    spfa();
    printf("%d\n", path[n]);
    return 0;
}

算法三十一、SPFA之SLF+LLL优化算法

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int gg = 200000 + 11;
int head[gg], dis[gg], n, m, cnt;
bool vis[gg];
int sum, tot;
struct node{
    int net, to, w;
} a[gg];

inline void add(int i, int j, int w) {
    a[++cnt].to = j;
    a[cnt].net = head[i];
    a[cnt].w = w;
    head[i] = cnt;
}

inline void spfa(int s) {
    deque<int> q;
    for (int i = 1;i <= n; i++) dis[i] = INF;
    dis[s] = 0; vis[s] = 1;    
    q.push_back(s);
    tot = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop_front();
        vis[u] = false;
        tot--;
        sum -= dis[u];
        for (int i = head[u]; ~i ; i = a[i].net) {
            int v = a[i].to;
            if (dis[v] > dis[u] + a[i].w) {
                dis[v] = dis[u] + a[i].w;
                if(!vis[v]) {
                    vis[v] = 1;
                    if (q.empty() || dis[v] > dis[q.front()] || dis[v] * tot <= sum) q.push_back(v);
                    tot++;
                    sum += dis[v];
                }
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof head);
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) {
        int w = 0;
        scanf("%d", &w);
        add(i, i + 1, w);
    }
    spfa(1);
    if (dis[n] == INF)  puts("-1");
    else printf("%d\n", dis[n]);
    return 0;
}

算法三十二、只用一个变量跑A+B

把一个long long拆成两个int
指针啊!!!

#include<iostream>
using namespace std;
long long a;
int main() {
    scanf("%d%d", (int*)(&a), (int*)(&a+1));
    printf("%d\n", *((int*)&a) + *((int*)(&a+1)));
    return 0;
}

算法三十三、矩阵乘法

#include<bits/stdc++.h>
using namespace std;
int a, b;
int x[2][2] = {
    {0, 1},
    {1, 1}
};
void mo(int f[]) {
    int ans[2] = {0};
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++) ans[i] += f[j] * x[i][j];
    for(int i = 0; i < 2; i++) f[i] = ans[i];
}
int main() {
    cin >> a >> b;
    int f[3] = {a, b};
    mo(f);
    cout << f[1];
    return 0;
}

算法三十四、STL+dijkstra

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;
const int N=405;
struct Edge {
    int v,w;
};
vector<Edge> edge[N*N];
int n;
int dis[N*N];
bool vis[N*N];
struct cmp {
    bool operator()(int a,int b) {
        return dis[a]>dis[b];
    }
};
int Dijkstra(int start,int end)
{
    priority_queue<int,vector<int>,cmp> dijQue;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dijQue.push(start);
    dis[start]=0;
    while(!dijQue.empty()) {
        int u=dijQue.top();
        dijQue.pop();
        vis[u]=0;
        if(u==end)
            break;
        for(int i=0; i<edge[u].size(); i++) {
            int v=edge[u][i].v;
            if(dis[v]==-1 || dis[v]>dis[u]+edge[u][i].w) {
                dis[v]=dis[u]+edge[u][i].w;
                if(!vis[v]) {
                    vis[v]=true;
                    dijQue.push(v);
                }
            }
        }
    }
    return dis[end];
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    Edge Qpush;

    Qpush.v=1;
    Qpush.w=a;
    edge[0].push_back(Qpush);

    Qpush.v=2;
    Qpush.w=b;
    edge[1].push_back(Qpush);

    printf("%d",Dijkstra(0,2));
    return 0;
}

算法三十五、数学表达式

#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main() {
    cin >> a >> b;
    cout << a - b + (a * 2) - (a - b) - a + (a + (b - a)) << endl;
    return 0;
}

算法三十六、define大法

#include <bits/stdc++.h>
#define ___ int
#define $$$ main
#define _$_$_ return
#define _ cin
#define $ cout
#define __ using
#define $$ namespace
#define o_o std
__ $$ o_o;
___ $$$(){
    ___ _$o$_,$o_o$;
    _ >> _$o$_ >> $o_o$;
    $ << _$o$_ + $o_o$;
    _$_$_ 0;
}

算法三十七、压位高精度加法

奇怪的知识又增加了!

#include <bits/stdc++.h>
using namespace std;
const int mod = 100000000;
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % mod);
        t /= mod;
    }
    if (t) C.push_back(t);
    return C;
}
int main() {
    string a, b; cin >> a >> b;
    vector<int> A, B, C;
    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) {
        s += (a[i] - '0') * t;
        j++; t *= 10;
        if (j == 8 || i == 0) A.push_back(s), s = 0, j = 0, t = 1;
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) {
        s += (b[i] - '0') * t;
        j++; t *= 10;
        if (j == 8 || i == 0) B.push_back(s), s = 0, j = 0, t = 1;
    }
    C = add(A, B);
    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i--) printf("%08d", C[i]);
    return 0;
}

算法三十八、加一大堆东东……

听说手动开O3优化……

虽然好像没优化多少

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#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")
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%d", a + b);
    return 0;
}

算法三十九、暴力枚举优化版

和算法六区别“不大”但是时间优化了300ms……
时间:$1567 ms$
就是在 $min(2 \times a, 2 \times b)$ 到 $max(2 \times a, 2 \times b)$ 之间枚举,效率高了“亿”点点

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b; scanf("%d%d", &a, &b);
    for (int i = min(2 * a, 2 * b);i <= max(2 * a, 2 * b); i++)
        if (a + b == i) {
            printf("%d", i); //注意要输出i,不然如果输出a+b循环就没意义了……
            return 0;
        }
}

算法四十、矩阵DP

就是和方格取数之类的这些同样的思维~

#include <bits/stdc++.h>
using namespace std;
int a[110][110], n = 2;
int main() {
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= n; j++) scanf("%d", &a[i][j]);
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= n; j++) 
            if (max(a[i - 1][j], a[i][j - 1]) > -1) a[i][j] += max(a[i - 1][j], a[i][j - 1]);
    printf("%d\n", a[n][n]);
    return 0;
}

算法四十一、拖延时间大法

yyds!永远的拖延时间!

3176 ms天哪!

#include <algorithm>
//STL 通用算法
#include <bitset>
//STL 位集容器
#include <cctype>
//字符处理
#include <cerrno>
//定义错误码
#include <cfloat>
//浮点数处理
#include <ciso646>
//对应各种运算符的宏
#include <climits>
//定义各种数据类型最值的常量
#include <clocale>
//定义本地化函数
#include <cmath>
//定义数学函数
#include <complex>
//复数类
#include <csignal>
//信号机制支持
#include <csetjmp>
//异常处理支持
#include <cstdarg>
//不定参数列表支持
#include <cstddef>
//常用常量
#include <cstdio>
//定义输入/输出函数
#include <cstdlib>
//定义杂项函数及内存分配函数
#include <cstring>
//字符串处理
#include <ctime>
//定义关于时间的函数
#include <cwchar>
//宽字符处理及输入/输出
#include <cwctype>
//宽字符分类
#include <deque>
//STL 双端队列容器
#include <exception>
//异常处理类
#include <fstream>
//文件输入/输出
#include <functional>
//STL 定义运算函数(代替运算符)
#include <limits>
//定义各种数据类型最值常量
#include <list>
//STL 线性列表容器
#include <locale>
//本地化特定信息
#include <map>
//STL 映射容器
#include <memory>
//STL通过分配器进行的内存分配
#include <new>
//动态内存分配
#include <numeric>
//STL常用的数字操作
#include <iomanip>
//参数化输入/输出
#include <ios>
//基本输入/输出支持
#include <iosfwd>
//输入/输出系统使用的前置声明
#include <iostream>
//数据流输入/输出
#include <istream>
//基本输入流
#include <iterator>
//STL迭代器
#include <ostream>
//基本输出流
#include <queue>
//STL 队列容器
#include <set>
//STL 集合容器
#include <sstream>
//基于字符串的流
#include <stack>
//STL 堆栈容器
#include <stdexcept>
//标准异常类
#include <streambuf>
//底层输入/输出支持
#include <string>
//字符串类
#include <typeinfo>
//运行期间类型信息
#include <utility>
//STL 通用模板类
#include <valarray>
//对包含值的数组的操作
#include <vector>
//STL 动态数组容器


//头文件拖延编译时间(虽然不能拖延运行时间,但能拖一点编译时间也很不错了hh) 
using namespace std;
int main(){
    int a; int b; //不用int a, b;,拖延运行时间
    cin >> a >> b; //cin拖延运行时间
    int ans = 1 * 10000 / 10 / 10 / 10 / 10 * 5 * 2 / 10 - 1; //ans表达式拖延编译和运行时间
    for (int i = 1;i <= a; i++) ans += 5, ans -= 4; //拖延时间 
    for (int i = 1;i <= b; i++) ans += 5, ans -= 4; //拖延时间 
    ans = ans - ans + ans + ans - ans; //表达式拖延时间
    cout << ans << endl; //cout和多输出回车拖延时间 
    return 0;
}

算法四十二、极限卡点

卡到了9970ms……

#include <bits/stdc++.h>
using namespace std;
int st = clock();
int main() {
    int a, b; scanf("%d%d", &a, &b);
    while (clock() - st < 995000) {}
    printf("%d", a + b);
    return 0;
}

算法四十三、快读快写

#include<bits/stdc++.h>
using namespace std;
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {  
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
void write(int x) {
    if(x < 0) {
        putchar('-'); 
        x = -x;
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int main() {
    int a, b; a = read(); b = read();
    write(a + b);
    return 0;
}

算法四十四、终极大杀器快读快写

#include<bits/stdc++.h>
using namespace std;
static char buf[100000], *pa = buf, *pd = buf;
#define gc pa == pd && (pd = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pd) ? EOF : *pa++
inline int read() {
    register int x(0); register char c(gc);
    while (c < '0' || c > '9') c = gc;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = gc;
    return x;
}
void write(int x) {
    if(x < 0) {
        putchar('-'); 
        x = -x;
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int main() {
    int a, b; a = read(); b = read();
    write(a + b);
    return 0;
}

算法四十五、sort大大大大大大大大大法

sort yyds!

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法四十六、冒泡排序

E……

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = n;i > 1; i--)
        for(int j = 1;j < i; j++)
            if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法四十七、选择排序

………………

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i < n; i++) {
        int w = i, Min = a[i];
        for (int j = i;j <= n; j++) if(Min > a[j]) w = j, Min = a[j]; //寻找🔎最小数和它的位置
        swap(a[i], a[w]);
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法四十八、插入排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    n = 2;
    for (int i = 1;i <= n; i++) {
        scanf("%d", &a[i]); int x = i - 1;
        while(a[x] > a[x + 1] && x > 0) swap(a[x], a[x + 1]), x--;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法四十九、希尔排序

azzzzzzzzzzzzzzzzzz

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    n = 2;
    for (int i = 0;i < n; i++) scanf("%d", &a[i]);
    for (int step = n / 2; step > 0; step /= 2)
        for (int i = 0;i < step; i++)
            for (int j = i + step;j < n; j += step)
                if(a[j] < a[j - step]) {
                    int temp = a[j];
                    int k = j - step;
                    while (k >= 0 && temp < a[k]) {
                        swap(a[k + step], a[k]);
                        k -= step;
                    }
                }
    int ans = 0;
    for (int i = 0;i < n; i++) ans += a[i]; printf("%d ", ans);
    return 0;
}

算法五十、归并排序

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN], T[MAXN];
void Mergesort(int l, int r) {
    if (l == r) return; //区间内只有一个数,返回
    int mid = l + r >> 1; //相当于(l + r) / 2
    Mergesort(l, mid); //递归左半部分
    Mergesort(mid + 1, r); //递归右半部分
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) //合并
        if (a[i] <= a[j]) T[k++] = a[i++];
        else T[k++] = a[j++];
    while (i <= mid) T[k++] = a[i++];
    while (j <= r) T[k++] = a[j++];
    for (int q = l; q <= r; q++) a[q] = T[q]; //转移
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Mergesort(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法五十一、快速排序

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
void quickSort(int l, int r) {
    if (l >= r) return;
    int i = l, j = r, base = a[l]; //base取最左边的数为基准数
    while(i < j) {
        while (a[j] >= base && i < j) j--;
        while (a[i] <= base && i < j) i++;
        if (i < j) swap(a[i], a[j]);
    }
    a[l] = a[i]; a[i] = base; //基准数归位
    quickSort (l, i - 1); //递归左边
    quickSort (i + 1, r); //递归右边
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    quickSort(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法五十二、堆排序

#include  <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1e8 + 10;
int h[MAXN], s;
void down(int u) {
    int t = u;  // t记录最小值
    if (2 * u <= s && h[2 * u] < h[t]) t = 2 * u; // 左儿子
    if (2 * u + 1 <= s && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 右儿子
    if (t != u) { //需要调整
        swap(h[t], h[u]);
        down(t); //递归
    }
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    s = n;
    for (int i = n / 2; i >= 1; i--) down(i); //初始化堆j
    int ans = 0;
    while (n--) {
        ans += h[1];
        h[1] = h[s]; s--;
        down(1); 
    }
    printf("%d", ans);
    return 0;
}

算法五十三、计数排序

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
long long n, cnt[MAXN];
int main() {
    n = 2; int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &x); cnt[x]++; //统计
        Max = max(Max, x); Min = min(Min, x); //更新最大值和最小值
    }
    int ans = 0;
    for (int i = Min;i <= Max; i++)
        while(cnt[i]) cnt[i]--, ans += i;
    printf("%d", ans);
    return 0;
}

算法五十四、桶排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, Min = MAXN, Max = 0, sum[MAXN], ans;
bool f[45];
vector<int> bucket[45];//定义桶,这里定义40个桶
void insertsort(int s) {
    for (int i = 0;i < bucket[s].size(); i++)
        for (int j = i;j >= 1; j--) if(bucket[s][j - 1] > bucket[s][j]) swap(bucket[s][j], bucket[s][j - 1]);//这里是从小到大排序
    for (int i = 0;i < bucket[s].size(); i++) ans += bucket[s][i];
}
void bucketsort() {
    for (int i = 1;i <= n; i++)
        bucket[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))].push_back(sum[i]), f[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))] = 1;//运用最大最小值来合理分配桶
    for (int i = 0;i <= 40; i++) if(f[i]) insertsort(i); //如果当前桶有数值,则对桶内的数进行排序(这里用选择排序)
}
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) {
        scanf("%d", &sum[i]);
        Min = min(Min, sum[i]), Max = max(Max, sum[i]); //为了能够合理利用空间,确保第一个桶和最后一个桶都有数,所以存储最大最小值
    }
    bucketsort(); printf("%d", ans);
    return 0; 
}

算法五十五、基数排序

#include <bits/stdc++.h>
using namespace std;
int maxbit(int data[], int n) {
    int d = 1, p = 10; //d保存最大的位数 
    for (int i = 0;i < n; i++) while(data[i] >= p) p *= 10, d++;
    return d;
}
void radixsort(int data[], int n) { //基数排序 
    int d = maxbit(data, n);
    int tmp[n];
    int cnt[15], i, j, k, radix = 1;
    for (i = 1;i <= d; i++) { //进行d次排序
        memset(cnt, 0, sizeof(cnt)); //清空计数器
        for (j = 0;j < n; j++) {
            k = (data[j] / radix) % 10;
            cnt[k]++;
        }
        for (j = 1;j < 10; j++) cnt[j] += cnt[j - 1];
        for (j = n - 1;j >= 0; j--) {
            k = (data[j] / radix) % 10;
            tmp[cnt[k] - 1] = data[j];
            cnt[k]--;
        }
        for (j = 0;j < n; j++) data[j] = tmp[j];
        radix *= 10;
    }
}
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    n = 2;
    for (int i = 0;i < n; i++) scanf("%d", &a[i]);
    radixsort(a, n);
    int ans = 0;
    for (int i = 0;i < n; i++) ans +=  a[i]; printf("%d", ans);
}

算法五十六、鸡尾酒排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int cnt = 0;
    while (1) {
        int f = 0; cnt++;
        if(cnt & 1)
            for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) swap(a[i], a[i + 1]), f = 1;
        else
            for (int i = n;i > 1; i--) if(a[i] < a[i - 1]) swap(a[i], a[i - 1]), f = 1;
        if(!f) break;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法五十七、二叉排序树排序

(怎么还是排序hh)

#include<bits/stdc++.h>
#define LL long long
#define INF 0x7FFFFFFF
using namespace std;
const int N = 1e8 + 10;
int n, idx, rt, ans;
int a[N], t[N];
int ch[N][2];
void insert(int &x, int val) {
    if (!x) {
        x = ++ idx;
        t[x] = val;
        return;
    }
    else {
        if(val < t[x]) insert(ch[x][0], val);
        else insert(ch[x][1], val);
    }
}
void dfs(int x) { //中序遍历二叉排序树
    if(!x) return;
    dfs(ch[x][0]);
    ans += t[x];
    dfs(ch[x][1]);
}
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n; i++) insert(rt, a[i]);
    dfs(rt); printf("%d", ans);
    return 0;
}

算法五十八、侏儒排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int s = 1;
    while(s <= n) {
        if(a[s - 1] <= a[s] || s == 0) s++;
        else swap(a[s], a[s - 1]), s--;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
} 

算法五十九、猴子排序

(虽然在排序上理论会TLE……但是A+B还是能AC的……)
(排序终于结束了……hh)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int check() {
    for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) return 0;
    return 1;
}
int main() {
    n = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    while (1) {
        random_shuffle(a + 1, a + 1 + n);   //随机打乱数组的系统函数 
        if(check()) break;
    }
    int ans = 0;
    for (int i = 1;i <= n; i++) ans += a[i]; printf("%d", ans);
    return 0;
}

算法六十、快速幂

#include<bits/stdc++.h>
using namespace std;
int qmi(int m, int k, int p) {
    int res = 1 % p, t = m;
    while (k) {
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%d", qmi(a, 1, 100000010) + qmi(b, 1, 100000010));
    return 0;
}

算法六十一、差分

#include <bits/stdc++.h>
using namespace std;
int n = 2, m = 5, b[10];
int main() {
    for (int i = 1;i <= n; i++) {
        int x; scanf("%d", &x);
        b[1] += x; b[m + 1] -= x;
    }
    int ans = 0, x = 0;
    for (int i = 1;i <= m; i++) {
        x += b[i]; ans = max(ans, x);
    }
    printf("%d", ans);
    return 0;
}

算法六十二、模拟人工计算

当然这注释是和人工计算最接近的hh

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b); //人眼看见数据
    if (a == 0) {printf("%d", b); return 0;}  //大脑瞬间“打表”被老师发现了,血量减少50……
    if (b == 0) {printf("%d", a); return 0;}  //大脑瞬间“打表”被老师发现了,血量减少50……
    int f1 = 0, f2 = 0; //大脑申请了两个空间……(还好没炸掉)
    if (a < 0) f1 = 1;  //大脑正在判断,请勿打扰……
    if (b < 0) f2 = 1;  //大脑正在判断,请勿打扰……
    a = abs(a); b = abs(b);  //哇!大脑使用了去掉负号的大法!!!
    int ans = 0;   //大脑申请了一个空间
    if (f1) ans -= a;  //大脑正在艰难地判断着……
    //大脑指挥手拿起笔在草稿纸上划来划去……
    //大脑感到烦躁
    //眼睛看到老师转了一下身子,立刻反馈给大脑
    //大脑指挥手在计算器键盘上写下了算式……
    //眼睛看到答案,反馈给大脑,大脑立刻指挥手关掉了计算器……
    //眼睛看到老师转回来了
    else ans += a;  //大脑正在艰难地判断着……
    if (f2) ans -= b;//大脑正在艰难地判断着……
    //大脑指挥手拿起笔在草稿纸上划来划去……
    //大脑感到烦躁
    //眼睛看到老师转了一下身子,立刻反馈给大脑
    //大脑指挥手在计算器键盘上写下了算式……
    //眼睛看到答案,反馈给大脑,大脑立刻指挥手关掉了计算器……
    //眼睛看到老师转回来了
    else ans += b;//大脑正在艰难地判断着……
    //眼睛观察到老师正在身后冷冷地看着……
    //大脑感到紧张
    //大脑让身体不由自主地颤抖起来
    //大脑差点死机
    //大脑复活
    //立刻写下答案
    printf("%d", ans);
    //大脑又死机了……
    //耳朵听到老师在叫自己起来
    //大脑指挥身体起来了
    //开始下一题……(下一个数据)
    return 0;
}

算法六十三、二进制

额……好像有点不太正常

#include<bits/stdc++.h>
using namespace std;
int a, b, s, s1, i, na, nb;
int main() {
    scanf("%d%d", &a, &b);
    if (a <= 0) na = 1, a = abs(a);
    while(a) {
        if ((a & 1) != 0) s += pow(2, (a & 1) * i);
        a >>= 1; i++;
    }
    i = 0;
    if (na == 1) s = abs(s);
    if (b <= 0) nb = 1, b = abs(b);
    while(b) {
        if ((b & 1) != 0) s1 += pow(2, (b & 1) * i);
        b >>= 1; i++;
    }
    if (nb == 1) s1 = abs(s1);
    printf("%d", s + s1);
    return 0;
}

算法六十四、ST表

区间最小值加区间最大值 = A+B

#include <bits/stdc++.h>
using namespace std;
int n, a[10], st1[10][17], st2[10][17];
void ST_work1() {
    for (int i = 1; i <= n; i++) st1[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++) {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
    }
}
int ST_query1(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return max(st1[l][k], st1[r - (1 << k) + 1][k]);
}
void ST_work2() {
    for (int i = 1; i <= n; i++) st1[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++) {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            st1[i][j] = min(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
    }
}
int ST_query2(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}
int main() {
    n = 2;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    ST_work1(); int ans1 = ST_query1(1, 2);
    ST_work2(); int ans2 = ST_query2(1, 2);
    printf("%d", ans1 + ans2);
    return 0;
}

算法六十五、01背包

#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
    n = 2; m = 2;  //2个物体,背包容积2
    for (int i = 1;i <= n; i++) c[1] = 1, scanf("%d", &w[i]);  //设体积为1,读入价值
    for (int i = 1;i <= n; i++)
        for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}

算法六十六、完全背包

#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
    n = 2; m = 3;
    for (int i = 1;i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1;i <= n; i++)
        for (int j = c[i]; j <= m; j++)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}

算法六十七、多重背包之暴力拆分法

#include <bits/stdc++.h>
using namespace std;
int c[110], w[110], s[110], dp[1010], n, m;
int main() {
    n = 2; m = 2;
    for (int i = 1;i <= n; i++) scanf("%d", &w[i]), c[i] = s[i] = 1;
    for (int i = 1;i <= n; i++)
        for (int x = 1;x <= s[i]; x++)
            for (int j = m; j >= c[i]; j--)
                dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}

算法六十八、多重背包之二进制拆分

#include <bits/stdc++.h>
using namespace std;
int n, m, v[10010], w[10010], f[2010];
int main() {
    n = 2; m = 2;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int a = 1, b, s = 1, k = 1; scanf("%d", &b);
        while (k <= s) {
            cnt++;
            v[cnt] = a * k; w[cnt] = b * k;
            s -= k; k <<= 1;
        }
        if (s > 0) {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    printf("%d\n", f[m]);
    return 0;
}

算法六十九、二维费用背包问题

#include <bits/stdc++.h>
using namespace std;
int N, V, M;
int v[1010], m[1010], w[1010], f[1010][1010];
int main () {
    N = V = M = 2;
    for (int i = 1; i <= N; i++) scanf("%d", &w[i]), v[i] = m[i] = 1;
    for (int i = 1; i <= N; i++)
        for (int j = V; j >= v[i]; j--)
            for (int k = M; k >= m[i]; k--)
                f[j][k] = max(f[j - v[i]][k - m[i]] + w[i], f[j][k]);
    printf("%d\n", f[V][M]);
    return 0;
}

算法七十、分组背包问题

#include <bits/stdc++.h>
using namespace std;
int f[110][110], v[110][110], w[110][110], s[110];
int n, m, k;
int main() {
    n = m = 2;
    for (int i = 1; i <= n; i++) {
        s[i] = 1;
        for (int j = 0; j < s[i]; j++) scanf("%d", &w[i][j]), v[i][j] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            for (int k = 0; k < s[i]; k++)
                if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

算法七十一、有依赖的背包问题

#include <bits/stdc++.h>
using namespace std;
int n, m, v[110], w[110];
int h[110], e[110], ne[110], idx;
int f[110][110];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {  // 循环物品组
        int son = e[i];
        dfs(e[i]);
        // 分组背包
        for (int j = m - v[u]; j >= 0; j -- )  // 循环体积
            for (int k = 0; k <= j; k ++ )  // 循环决策
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }
    // 将物品u加进去
    for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;
}
int main() {
    n = m = 2;
    memset(h, -1, sizeof h);
    int root;
    for (int i = 1; i <= n; i++) {
        int p; v[i] = 1; scanf("%d", &w[i]);
        if (i == 1) p = -1; else p = 1; //A+B中的特判
        if (p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    printf("%d", f[root][m]);
    return 0;
}

算法七十二、多重背包队列优化

#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[20010], g[20010], q[20010];
int main() {
    n = m = 2;
    for (int i = 1; i <= n; i ++ ) {
        int v = 1, w, s = 1; scanf("%d", &w);
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ ) {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v) {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ; //剔除超出长度元素
                if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w); //更新当前答案
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                //维持单调性
                //这里也可以这样写,更易理解
                //while (hh <= tt && g[q[tt]] <= g[k] - (k - q[tt]) / v * w) tt -- ;
                q[++tt] = k;
            } 
        }
    }
    printf("%d", f[m]);
    return 0;
}

算法七十三、$istream$_$iterator$

还是大佬们厉害,我没看懂……

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include<iterator>
using namespace std;
int main()
{
    istream_iterator<int> in(cin), eof;
    cout << accumulate(in, eof ,0) << endl;
    return 0;
}

算法七十四、进制转换

我本来想要十进制转二进制一个算法,十进制转三进制一个算法……然后发现甚至可以到十进制转$10^8$进制……
而且它们都属于进制转换,所以我决定直接写一个通用的进制转换程序。
然后随机进制转换,在那个进制下加法,再转化为十进制存储下来,如果所有的答案都一样,则输出这个答案。
我是不是很无聊

#include <bits/stdc++.h>
using namespace std;
int A[30], B[30], a, b;
int check(int mod) {
    int x = a, y = b, ta = 0, tb = 0;
    while (x) {
        A[++ta] = x % mod;
        x /= mod;
    }
    while (y) {
        B[++tb] = y % mod;
        y /= mod;
    }
    for (int i = 1; i <= max(ta, tb); i++) {
        A[i] += B[i];
        if (A[i] >= mod) A[i + 1] += A[i] / mod, A[i] %= mod;
    }
    if (A[ta + 1]) ta++;
    int Ans = 0;
    for (int i = ta; i > 0; i--) Ans = Ans * mod + A[i];
    return Ans;
}
int main() {
    scanf("%d%d", &a, &b);
    int ans[100010];
    for (int i = 1; i <= 100000; i++) {
        srand((unsigned)time(NULL));
        int o = (int) rand() % 1000000 + 2;  //取随机进制
        ans[i] = check(o);
    }
    bool f = 1;
    for (int i = 2; i <= 100000; i++) if (ans[i] != ans[i - 1]) { f = 0; break; }
    if (f) printf("%d\n", ans[1]);
    else puts("老子不干了!WA就WA吧!一行WA上西天!");  //誓死不AC(逃)
    return 0;
}

算法七十五、指针算法

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    cin>>a>>b;
    int *c = &a, *d = &b, ans;
    ans = *c + *d;
    cout << ans << endl;
}

算法七十六、$vector$

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
    int x = 0;
    while (cin>>x) v.push_back(x);
    int ans = 0;
    for (int i = 0; i < v.size(); i++) ans += v[i];
    cout << ans;
    return 0;
}

算法七十七、$queue$

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main() {
    int x;
    while (cin>>x) q.push(x);
    int ans = 0;
    while (q.size()) ans += q.front(), q.pop();
    cout << ans;
    return 0;
}

算法七十八、$deque$

#include <bits/stdc++.h>
using namespace std;
deque<int> a, b;
int main() {
    int x;
    while (cin>>x) a.push_front(x);
    int ans = 0;
    while (a.size()) ans += a.back(), b.push_back(a.back()), a.pop_back();
    int res = 0;
    while (b.size()) res += b.front(), b.pop_front();
    if (ans == res) cout << (ans + res) / 2;
    return 0;
}

算法七十九、$list$

#include <bits/stdc++.h>
using namespace std;
list<int> a, b;
int main() {
    int x;
    while (cin>>x) a.push_front(x);
    int ans = 0;
    while (a.size()) b.push_back(a.back()), ans += a.back(), a.pop_back();
    int res = 0;
    while (b.size()) res += b.front(), b.pop_front();
    if (ans == res) cout << (ans + res) / 2;
    return 0;
}

算法八十、$map$

#include <bits/stdc++.h>
using namespace std;
map<int, string> m;
int main() {
    int x = 0;
    while (cin>>x) m[x] = "老子不会老子WA行了吧???";
    int ans = 0;
    for (auto iter = m.begin(); iter != m.end(); ++iter) {
        ans += iter->first;
    }
    cout << ans;
    return 0;
}

算法八十一、$set$

#include <bits/stdc++.h>
using namespace std;
set<int> s;
int main() {
    int x = 0;
    while (cin>>x) s.insert(x);
    int ans = 0;
    for (auto iter = s.begin(); iter != s.end(); ++iter) {
        ans += *iter; 
    }
    cout << ans;
    return 0;
}

算法八十二、$pair$

#include <bits/stdc++.h>
using namespace std;
int main() {
    pair<int, int> a[110];
    int x = 0, c = 0, t = 1;
    while (cin>>x) {
        if (c == 0) a[t].first = x, c = 1;
        else a[t].second = x, t++, c = 0;
    }
    int ans = 0;
    for (int i = 1; i <= 100; i++) {
        ans += a[i].first + a[i].second;
    }
    cout << ans;
    return 0;
}

算法八十三、$stack$

#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int main() {
    int x = 0;
    while (cin>>x) s.push(x);
    int ans = 0;
    while (s.size()) ans += s.top(), s.pop();
    cout << ans;
    return 0;
}

算法八十四、$priority$_$queue$

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main() {
    int x = 0;
    while (cin>>x) q.push(x);
    int ans = 0;
    while (q.size()) ans += q.top(), q.pop();
    cout << ans;
    return 0;
}

懵了没?




搞了那么久,我们来个正常的吧……

满足某人的需求
观众们:你是认真的吗?

C代码

#include <stdio.h>

int main()
{
    int a,b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++代码

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
    return 0;
}

Pascal代码

var a, b: longint;
begin
    readln(a,b);
    writeln(a+b);
end.

Python代码

import sys

for line in sys.stdin:
    print sum(map(int, line.split()))

Python2代码

s = raw_input().split()
print int(s[0]) + int(s[1])

Python3代码

print(sum(map(int, input().split())))

Java代码

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int a = cin.nextInt(), b = cin.nextInt();
        System.out.println(a+b);
    }
}

JavaScript代码(Node.js)

const fs = require('fs')
const data = fs.readFileSync('/dev/stdin')
const result = data.toString('ascii').trim().split(' ').map(x => parseInt(x)).reduce((a, b) => a + b, 0)
console.log(result)
process.exit() // 请注意必须在出口点处加入此行

Ruby代码

a, b = gets.split.map(&:to_i)
print a+b

PHP代码

<?php
$input = trim(file_get_contents("php://stdin"));
list($a, $b) = explode(' ', $input);
echo $a + $b;

Rust代码

use std::io;

fn main(){
    let mut input=String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut s=input.trim().split(' ');

    let a:i32=s.next().unwrap()
               .parse().unwrap();
    let b:i32=s.next().unwrap()
               .parse().unwrap();
    println!("{}",a+b);
}

Go代码

package main

import "fmt"

func main() {
    var a, b int
    fmt.Scanf("%d%d", &a, &b)
    fmt.Println(a+b)
}

C# Mono代码

using System;

public class APlusB{
    private static void Main(){
        string[] input = Console.ReadLine().Split(' ');
        Console.WriteLine(int.Parse(input[0]) + int.Parse(input[1]));
    }
}

Visual Basic Mono代码

Imports System

Module APlusB
    Sub Main()
        Dim ins As String() = Console.ReadLine().Split(New Char(){" "c})
        Console.WriteLine(Int(ins(0))+Int(ins(1)))
    End Sub
End Module

Kotlin代码

fun main(args: Array<String>) {
    val (a, b) = readLine()!!.split(' ').map(String::toInt)
    println(a + b)
}

Haskell代码

main = do
    [a, b] <- (map read . words) `fmap` getLine
    print (a+b)

Scala代码

object Main extends App {
    println(scala.io.StdIn.readLine().split(" ").map(_.toInt).sum)
}

Perl代码

my $in = <STDIN>;
chomp $in;
$in = [split /[\s,]+/, $in];
my $c = $in->[0] + $in->[1];
print "$c\n";

FoxPro代码

use
replace all c with a+b

(特此感谢~stO %%% @yxc %%% ●█▀█▄○| ̄|_orz 和各位大佬)

怎么样?这个还算正常吧……hh

对了,宣传一下@该用户被封禁大神的代表作:

$\color{red}{DP}$——目录

从01背包到第七十二种算法队列优化多重背包都是这位大神提供的代码和思路!%%%%%%%




封禁用户
14小时前

题目链接 AcWing 3628. 边的删减

把题目改一下

如果没有$k$的限制,要求每一个点都是“优秀点”,且把求方案改成求方案数,如何做?



新鲜事 原文

封禁用户
15小时前
emmmmmmmm如果加个数字4会怎么样……
图片


新鲜事 原文

被y总回复卡数据寄~ https://www.acwing.com/file_system/file/content/whole/index/content/6388405/#comment_300312



题目链接 AcWing786.第k个数

我遇到了不会写的问题。

(光速逃

谁都知道这是排序

但是我想用线段树写awa(我是疯子
但不会写查了一大堆教程还是没懂,能不能请大佬们解释下



新鲜事 原文

开肝可持久化数据结构 除了《算法竞赛入门经典》《算法竞赛进阶指南》以及yxc的视频讲解、OI Wiki…… 有没有其它的讲解推荐? 谢谢大佬们Orz



没思路
自己编了个“暴力代码”
在本地运行五分钟
无语
直接上打表吧QwQ
正解见其它大佬的题解QwQ

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main() {
    mp[1] = 1;
    mp[3] = 1;
    mp[5] = 1;
    mp[7] = 1;
    mp[9] = 1;
    mp[13] = 1;
    mp[15] = 1;
    mp[17] = 1;
    mp[25] = 1;
    mp[29] = 1;
    mp[31] = 1;
    mp[33] = 1;
    mp[49] = 1;
    mp[57] = 1;
    mp[61] = 1;
    mp[63] = 1;
    mp[65] = 1;
    mp[97] = 1;
    mp[113] = 1;
    mp[121] = 1;
    mp[125] = 1;
    mp[127] = 1;
    mp[129] = 1;
    mp[193] = 1;
    mp[225] = 1;
    mp[241] = 1;
    mp[249] = 1;
    mp[253] = 1;
    mp[255] = 1;
    mp[257] = 1;
    mp[385] = 1;
    mp[449] = 1;
    mp[481] = 1;
    mp[497] = 1;
    mp[505] = 1;
    mp[509] = 1;
    mp[511] = 1;
    mp[513] = 1;
    mp[769] = 1;
    mp[897] = 1;
    mp[961] = 1;
    mp[993] = 1;
    mp[1009] = 1;
    mp[1017] = 1;
    mp[1021] = 1;
    mp[1023] = 1;
    mp[1025] = 1;
    mp[1537] = 1;
    mp[1793] = 1;
    mp[1921] = 1;
    mp[1985] = 1;
    mp[2017] = 1;
    mp[2033] = 1;
    mp[2041] = 1;
    mp[2045] = 1;
    mp[2047] = 1;
    mp[2049] = 1;
    mp[3073] = 1;
    mp[3585] = 1;
    mp[3841] = 1;
    mp[3969] = 1;
    mp[4033] = 1;
    mp[4065] = 1;
    mp[4081] = 1;
    mp[4089] = 1;
    mp[4093] = 1;
    mp[4095] = 1;
    mp[4097] = 1;
    mp[6145] = 1;
    mp[7169] = 1;
    mp[7681] = 1;
    mp[7937] = 1;
    mp[8065] = 1;
    mp[8129] = 1;
    mp[8161] = 1;
    mp[8177] = 1;
    mp[8185] = 1;
    mp[8189] = 1;
    mp[8191] = 1;
    mp[8193] = 1;
    mp[12289] = 1;
    mp[14337] = 1;
    mp[15361] = 1;
    mp[15873] = 1;
    mp[16129] = 1;
    mp[16257] = 1;
    mp[16321] = 1;
    mp[16353] = 1;
    mp[16369] = 1;
    mp[16377] = 1;
    mp[16381] = 1;
    mp[16383] = 1;
    mp[16385] = 1;
    mp[24577] = 1;
    mp[28673] = 1;
    mp[30721] = 1;
    mp[31745] = 1;
    mp[32257] = 1;
    mp[32513] = 1;
    mp[32641] = 1;
    mp[32705] = 1;
    mp[32737] = 1;
    mp[32753] = 1;
    mp[32761] = 1;
    mp[32765] = 1;
    mp[32767] = 1;
    mp[32769] = 1;
    mp[49153] = 1;
    mp[57345] = 1;
    mp[61441] = 1;
    mp[63489] = 1;
    mp[64513] = 1;
    mp[65025] = 1;
    mp[65281] = 1;
    mp[65409] = 1;
    mp[65473] = 1;
    mp[65505] = 1;
    mp[65521] = 1;
    mp[65529] = 1;
    mp[65533] = 1;
    mp[65535] = 1;
    mp[65537] = 1;
    mp[98305] = 1;
    mp[114689] = 1;
    mp[122881] = 1;
    mp[126977] = 1;
    mp[129025] = 1;
    mp[130049] = 1;
    mp[130561] = 1;
    mp[130817] = 1;
    mp[130945] = 1;
    mp[131009] = 1;
    mp[131041] = 1;
    mp[131057] = 1;
    mp[131065] = 1;
    mp[131069] = 1;
    mp[131071] = 1;
    mp[131073] = 1;
    mp[196609] = 1;
    mp[229377] = 1;
    mp[245761] = 1;
    mp[253953] = 1;
    mp[258049] = 1;
    mp[260097] = 1;
    mp[261121] = 1;
    mp[261633] = 1;
    mp[261889] = 1;
    mp[262017] = 1;
    mp[262081] = 1;
    mp[262113] = 1;
    mp[262129] = 1;
    mp[262137] = 1;
    mp[262141] = 1;
    mp[262143] = 1;
    mp[262145] = 1;
    mp[393217] = 1;
    mp[458753] = 1;
    mp[491521] = 1;
    mp[507905] = 1;
    mp[516097] = 1;
    mp[520193] = 1;
    mp[522241] = 1;
    mp[523265] = 1;
    mp[523777] = 1;
    mp[524033] = 1;
    mp[524161] = 1;
    mp[524225] = 1;
    mp[524257] = 1;
    mp[524273] = 1;
    mp[524281] = 1;
    mp[524285] = 1;
    mp[524287] = 1;
    mp[524289] = 1;
    mp[786433] = 1;
    mp[917505] = 1;
    mp[983041] = 1;
    mp[1015809] = 1;
    mp[1032193] = 1;
    mp[1040385] = 1;
    mp[1044481] = 1;
    mp[1046529] = 1;
    mp[1047553] = 1;
    mp[1048065] = 1;
    mp[1048321] = 1;
    mp[1048449] = 1;
    mp[1048513] = 1;
    mp[1048545] = 1;
    mp[1048561] = 1;
    mp[1048569] = 1;
    mp[1048573] = 1;
    mp[1048575] = 1;
    mp[1048577] = 1;
    mp[1572865] = 1;
    mp[1835009] = 1;
    mp[1966081] = 1;
    mp[2031617] = 1;
    mp[2064385] = 1;
    mp[2080769] = 1;
    mp[2088961] = 1;
    mp[2093057] = 1;
    mp[2095105] = 1;
    mp[2096129] = 1;
    mp[2096641] = 1;
    mp[2096897] = 1;
    mp[2097025] = 1;
    mp[2097089] = 1;
    mp[2097121] = 1;
    mp[2097137] = 1;
    mp[2097145] = 1;
    mp[2097149] = 1;
    mp[2097151] = 1;
    mp[2097153] = 1;
    mp[3145729] = 1;
    mp[3670017] = 1;
    mp[3932161] = 1;
    mp[4063233] = 1;
    mp[4128769] = 1;
    mp[4161537] = 1;
    mp[4177921] = 1;
    mp[4186113] = 1;
    mp[4190209] = 1;
    mp[4192257] = 1;
    mp[4193281] = 1;
    mp[4193793] = 1;
    mp[4194049] = 1;
    mp[4194177] = 1;
    mp[4194241] = 1;
    mp[4194273] = 1;
    mp[4194289] = 1;
    mp[4194297] = 1;
    mp[4194301] = 1;
    mp[4194303] = 1;
    mp[4194305] = 1;
    mp[6291457] = 1;
    mp[7340033] = 1;
    mp[7864321] = 1;
    mp[8126465] = 1;
    mp[8257537] = 1;
    mp[8323073] = 1;
    mp[8355841] = 1;
    mp[8372225] = 1;
    mp[8380417] = 1;
    mp[8384513] = 1;
    mp[8386561] = 1;
    mp[8387585] = 1;
    mp[8388097] = 1;
    mp[8388353] = 1;
    mp[8388481] = 1;
    mp[8388545] = 1;
    mp[8388577] = 1;
    mp[8388593] = 1;
    mp[8388601] = 1;
    mp[8388605] = 1;
    mp[8388607] = 1;
    mp[8388609] = 1;
    mp[12582913] = 1;
    mp[14680065] = 1;
    mp[15728641] = 1;
    mp[16252929] = 1;
    mp[16515073] = 1;
    mp[16646145] = 1;
    mp[16711681] = 1;
    mp[16744449] = 1;
    mp[16760833] = 1;
    mp[16769025] = 1;
    mp[16773121] = 1;
    mp[16775169] = 1;
    mp[16776193] = 1;
    mp[16776705] = 1;
    mp[16776961] = 1;
    mp[16777089] = 1;
    mp[16777153] = 1;
    mp[16777185] = 1;
    mp[16777201] = 1;
    mp[16777209] = 1;
    mp[16777213] = 1;
    mp[16777215] = 1;
    mp[16777217] = 1;
    mp[25165825] = 1;
    mp[29360129] = 1;
    mp[31457281] = 1;
    mp[32505857] = 1;
    mp[33030145] = 1;
    mp[33292289] = 1;
    mp[33423361] = 1;
    mp[33488897] = 1;
    mp[33521665] = 1;
    mp[33538049] = 1;
    mp[33546241] = 1;
    mp[33550337] = 1;
    mp[33552385] = 1;
    mp[33553409] = 1;
    mp[33553921] = 1;
    mp[33554177] = 1;
    mp[33554305] = 1;
    mp[33554369] = 1;
    mp[33554401] = 1;
    mp[33554417] = 1;
    mp[33554425] = 1;
    mp[33554429] = 1;
    mp[33554431] = 1;
    mp[33554433] = 1;
    mp[50331649] = 1;
    mp[58720257] = 1;
    mp[62914561] = 1;
    mp[65011713] = 1;
    mp[66060289] = 1;
    mp[66584577] = 1;
    mp[66846721] = 1;
    mp[66977793] = 1;
    mp[67043329] = 1;
    mp[67076097] = 1;
    mp[67092481] = 1;
    mp[67100673] = 1;
    mp[67104769] = 1;
    mp[67106817] = 1;
    mp[67107841] = 1;
    mp[67108353] = 1;
    mp[67108609] = 1;
    mp[67108737] = 1;
    mp[67108801] = 1;
    mp[67108833] = 1;
    mp[67108849] = 1;
    mp[67108857] = 1;
    mp[67108861] = 1;
    mp[67108863] = 1;
    mp[67108865] = 1;
    mp[100663297] = 1;
    mp[117440513] = 1;
    mp[125829121] = 1;
    mp[130023425] = 1;
    mp[132120577] = 1;
    mp[133169153] = 1;
    mp[133693441] = 1;
    mp[133955585] = 1;
    mp[134086657] = 1;
    mp[134152193] = 1;
    mp[134184961] = 1;
    mp[134201345] = 1;
    mp[134209537] = 1;
    mp[134213633] = 1;
    mp[134215681] = 1;
    mp[134216705] = 1;
    mp[134217217] = 1;
    mp[134217473] = 1;
    mp[134217601] = 1;
    mp[134217665] = 1;
    mp[134217697] = 1;
    mp[134217713] = 1;
    mp[134217721] = 1;
    mp[134217725] = 1;
    mp[134217727] = 1;
    mp[134217729] = 1;
    mp[201326593] = 1;
    mp[234881025] = 1;
    mp[251658241] = 1;
    mp[260046849] = 1;
    mp[264241153] = 1;
    mp[266338305] = 1;
    mp[267386881] = 1;
    mp[267911169] = 1;
    mp[268173313] = 1;
    mp[268304385] = 1;
    mp[268369921] = 1;
    mp[268402689] = 1;
    mp[268419073] = 1;
    mp[268427265] = 1;
    mp[268431361] = 1;
    mp[268433409] = 1;
    mp[268434433] = 1;
    mp[268434945] = 1;
    mp[268435201] = 1;
    mp[268435329] = 1;
    mp[268435393] = 1;
    mp[268435425] = 1;
    mp[268435441] = 1;
    mp[268435449] = 1;
    mp[268435453] = 1;
    mp[268435455] = 1;
    mp[268435457] = 1;
    mp[402653185] = 1;
    mp[469762049] = 1;
    mp[503316481] = 1;
    mp[520093697] = 1;
    mp[528482305] = 1;
    mp[532676609] = 1;
    mp[534773761] = 1;
    mp[535822337] = 1;
    mp[536346625] = 1;
    mp[536608769] = 1;
    mp[536739841] = 1;
    mp[536805377] = 1;
    mp[536838145] = 1;
    mp[536854529] = 1;
    mp[536862721] = 1;
    mp[536866817] = 1;
    mp[536868865] = 1;
    mp[536869889] = 1;
    mp[536870401] = 1;
    mp[536870657] = 1;
    mp[536870785] = 1;
    mp[536870849] = 1;
    mp[536870881] = 1;
    mp[536870897] = 1;
    mp[536870905] = 1;
    mp[536870909] = 1;
    mp[536870911] = 1;
    mp[536870913] = 1;
    mp[805306369] = 1;
    mp[939524097] = 1;
    mp[1006632961] = 1;
    /*
    114514
    QaQ只好打表了,自己本地运行一通
    (艹,不会还真AC了吧,希望是
    */
    int t; cin>>t;
    while (t--) {
        int n; cin>>n;
        puts(mp[n]?"Y":"N");
    }
    return 0;
}

作者:封禁用户
链接:https://www.acwing.com/activity/content/code/content/4085642/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



观察$a$每一位都是$0…m$(对m取模)。
推测循环节应当是$m^2$。
然后循环节是$9e6$,随便搞个$1e7$上去居然AC……

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e7;
int a, b, ax, by, m, k;
string n;
int main() {
    cin >>a>>b>>ax>>by>>m>>k>>n;
    int x =0;
    for (int i = 0; i < n.size(); i++) {
        x = x * 10 + n[i] - '0';
        x %= mod;
    }
    for (int i = 1; i <= x; i++) {
        int c = ax * b + by * a;
        c %= m; a = b, b = c;
    }
    for (int i = 1; i <= k; i++) {
        int c = ax * b + by * a;
        c %= m; a = b, b = c;
        cout<<a<<endl;
    }
    return 0;
}

作者:封禁用户
链接:https://www.acwing.com/activity/content/code/content/4086941/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



考虑二进制(这是最优方案)

#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
int main() {
    scanf("%d", &n); x = ans = 1;
    while (x * 2 - 1 <  n) {
        x <<= 1; ans++;
    }
    cout<<ans;
    return 0;
}



模拟,双指针即可。

#include <bits/stdc++.h>
using namespace std;
int a, b;
int x, y, ans = 0;
int main() {
    scanf("%d%d", &a, &b);
    int p = 0;
    if (a > b) swap(a, b);
    while (a != b) {
        if (p == 0) {a++; x++; ans += x;}
        else {b--; y++; ans += y;}
        p ^= 1;
    }
    cout << ans << endl;
    return 0;
}

作者:封禁用户
链接:https://www.acwing.com/activity/content/code/content/4081061/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。