不正经

这个屌丝很懒，什么也没留下！

热门标签

千里之行始于足下梦开始的地方——A+B problem C++史上最详解，氵题一道，109 种解法！（附加多种语法的代码）

作者：不正经 | 2024-05-03 04:40:25

踩

$\Huge版权声明$

原作者为 Conan15。

$\Huge转载请注明出处。$

温馨提示：此题解适合人群为算法学习者，不那么适合语法基础课还没学完的学生，对于初学者，建议看看yxc视频

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

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

首先声明此题非常困**（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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

算法二、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;
}
1
2
3
4
5
6
7
8
9
10
11
12

算法三、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法四、直接算咯

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

算法五、二分

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

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

~~但是还是 $1892 m s$ 卡过了欸~~

#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;
} 
1
2
3
4
5
6
7
8

算法七、最短路之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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

算法八、最短路之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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

算法九、最短路之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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

算法十、高精

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

算法十一、最小生成树之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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

算法十二、最小生成树之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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

算法十三、前缀和

#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;
}
1
2
3
4
5
6
7
8

算法十四、后缀和

#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;
}
1
2
3
4
5
6
7
8

算法十五、位运算

#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;
}
1
2
3
4
5
6
7
8
9
10
11

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

算法十七、树的直径——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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

算法十八、树的直径——树形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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

算法十九、网络流

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

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

算法二十、线段树

转化为区间求和问题

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

算法二十一、树状数组

思路一样，区间求和

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

算法二十二、分块

思路一样，区间求和

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

算法二十三、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

算法二十四、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

算法二十五、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的距离和并输出
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

算法二十六、字典树

来自洛谷

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

嘿嘿洛谷的没有啦~

算法二十七、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

算法二十八、可耻的打表

#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，还是我加的……
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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

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

算法三十二、只用一个变量跑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;
}
1
2
3
4
5
6
7
8

算法三十三、矩阵乘法

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法三十四、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

算法三十五、数学表达式

#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;
}
1
2
3
4
5
6
7
8

算法三十六、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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

奇怪的知识又增加了！

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

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

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

和算法六区别“不大”但是时间优化了300ms……
时间： $1567 m s$
就是在 $\times a, 2 \times b)$ 到 $\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;
        }
}
1
2
3
4
5
6
7
8
9
10

算法四十、矩阵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;
}
1
2
3
4
5
6
7
8
9
10
11
12

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

算法四十二、极限卡点

卡到了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;
}
1
2
3
4
5
6
7
8
9

算法四十三、快读快写

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

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

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

算法四十五、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;
}
1
2
3
4
5
6
7
8
9
10
11
12

算法四十六、冒泡排序

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

算法四十七、选择排序

………………

#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]; //寻找声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/527839

推荐阅读

相关标签

千里之行始于足下梦开始的地方——A+B problem C++史上最详解，氵题一道，109 种解法！（附加多种语法的代码）

版权声明 \Huge版权声明 版权声明

转载请注明出处。 \Huge转载请注明出处。 转载请注明出处。

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

祝

点赞的童鞋们！

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

搞恶！

搞恶！

非常搞恶！

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

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

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

建议慢慢食用

求

赞

求

赞

求

赞

算法一、DFS一号

算法二、DFS二号

算法三、BFS

算法四、直接算咯

算法五、二分

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

算法七、最短路之dijkstra

算法八、最短路之SPFA

算法九、最短路之Floyd

算法十、高精

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

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

算法十三、前缀和

算法十四、后缀和

算法十五、位运算

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

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

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

算法十九、网络流

算法二十、线段树

算法二十一、树状数组

算法二十二、分块

算法二十三、LCT

算法二十四、Splay

算法二十五、LCA

算法二十六、字典树

算法二十七、Bellman-Ford

算法二十八、可耻的打表

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

算法三十、SPFA之LLL优化

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

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

算法三十三、矩阵乘法

算法三十四、STL+dijkstra

算法三十五、数学表达式

算法三十六、define大法

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

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

虽然好像没优化多少

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

算法四十、矩阵DP

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

3176 ms天哪！

算法四十二、极限卡点

算法四十三、快读快写

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

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

算法四十六、冒泡排序

算法四十七、选择排序

$\Huge版权声明$

$\Huge转载请注明出处。$

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