古早的笔记(自不用)

Posted on In

古早的笔记(自不用)

IN MEMORY OF ACOJ


数据结构


栈

栈 stack FILO(first in last out)
如一个试管，只有一端可以控制进入输出，且进入输出都只能在栈顶进行，将压入栈顶为push，弹出栈顶为pop


手写栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

char s[20000];
int n = 0;

char pop() {
    return s[n--];
}
void push(int val) {
    s[++n] = val;
}

int main(void) {
    return 0;
}

STL

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>  
using namespace std;

int main(void) {
    stack<int> s;      // 定义一个栈，栈中元素类型为int
    s.push(5);         // 将元素5压入栈顶
    s.pop();           // 弹出栈顶元素, 但不返回其值
    s.top();           // 返回栈顶元素, 但不删除该元素
    s.size();          // 返回栈中元素的个数
    s.empty();         // 判断栈是否为空，空则返回true，非空返回false

    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
#include <bits/stdc++.h>
using namespace std;
int main() {
    stack<char> s;
    string str;
    cin >> str;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '(') {
            s.push('(');
        } else {
            if (s.empty()) {
                cout << "no" << endl;
                return 0;
            }
            s.pop();
        }
    }
    if (s.empty()) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
     return 0;
}


队列

队列 FIFO(first in first out)


手写队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int q[20000];
int head = 1, tail = 0;

int pop() {
    if (head <= tail) {
        return q[head++];
    }
} 

void push(int val) {
    q[++tail] = val;
}

int main(void) {
    return 0;
}

STL

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    queue<int> q;     // 定义一个队列，队列中元素类型为int
    q.push(5);        // 将元素5入队，放入队尾
    q.pop();          // 队首元素出队，但不返回其值
    q.front();        // 返回队首元素，但不删除该元素
    q.size();         // 返回队列中元素的个数
    q.empty();        // 判断队列是否为空，空则返回true，非空返回false

    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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    queue<int> q;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    int cur = 0;
    while (!q.empty()) {
        cur++;
        if (cur == m) {
            cout << q.front() << " ";
            q.pop();
            cur = 0;
        } else {
            q.push(q.front());
            q.pop();
        }
    }
    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;
unordered_map<int, vector<int>> adj;    // 定义个桶（即邻接表），桶的值为整型，位置为一个vector数组 
int inDegree[200000];
int main() {
    int n,m; cin>>n>>m;
    stack<int> s;
    for (int i = 1; i<= m; i++) {       //该for循环为读图操作 
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y); //邻接表操作， 在课程编号为x的课程的vector数组里放入编号为y的课程，化为图即为x -> y 
        inDegree[y] += 1;    //前置课程多了一个，等于该后置课程的入度加一 
    }
    for (int i= 1; i<= n; i++) {
        if (inDegree[i]==0) { //将入度为零的（即没有前置课程）的课程放入栈s中， 
            s.push(i);
        }
    }
    while (!s.empty()) {        //当栈s不为空时
        int cur = s.top();        //cur为当前入度最少的结点 
        cout << s.top() << " ";
        s.pop();                //将该入度最少的结点弹出栈，即学习完该课程 
        for (int i = 0; i < adj[cur].size(); i++) {        //该for循环作用为找出在刚刚弹出的结点（即刚学完的课程） 的桶中（即图中该结点指向的结点 ），在弹出该结点后入度为零的结点，将其压入栈顶，表示目前要最先学的课程 
            if (inDegree[adj[cur][i]] - 1 == 0) {
                s.push[adj[cur][i]];
            }
        }
    }
    return 0;
} 
  //注意：有多个结点入度为零时，那栈顶弹出的只有其中之一，接下来栈顶又会压入删去刚才弹出的那个结点后入度为零的，会把最开始的剩余结点覆盖，输出顺序不太对，但没关系，不用管


二叉树

二叉树
相当于一个族谱
想要知道每个家族成员，那就需要遍历


有几种不同的遍历方法，用如下二叉树来举例
1
2 3
4 5 6
7
1、层序遍历
从上往下一层一层的遍历 1 23 456 7


前序遍历

递归思想，到了无法满足顺序时返回到上一层（下同），顺序是 中左右 1 2 4 5 7 3 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int l, r;
};

TreeNode tree[200000];

void preOrder(int root) { // void没有返回值 
    if (root == -1) {
        return;
    }
    preOrder(tree[root].r);
    preOrder(tree[root].l);
    printf("%d ", root);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].l, &tree[i].r);
    } 
    preOrder(1);
    return 0;
}

中序遍历

顺序是 左中右， 也可以通过所有数在竖列上的位置从左到右遍历，4 2 7 5 1 6 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int l, r;
};

TreeNode tree[200000];

void preOrder(int root) { // void没有返回值 
    if (root == -1) {
        return;
    }
    preOrder(tree[root].l);
    printf("%d ", root);
    preOrder(tree[root].r);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].l, &tree[i].r);
    } 
    preOrder(1);
    return 0;
}

后序遍历

顺序是 左右中， 4 7 5 2 6 3 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
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int l, r;
};

TreeNode tree[200000];

void preOrder(int root) { // void没有返回值 
    if (root == -1) {
        return;
    }
    preOrder(tree[root].l);
    preOrder(tree[root].r);
    printf("%d ", root);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].l, &tree[i].r);
    } 
    preOrder(1);
    return 0;
}


Hash

Hash（哈希）
数组下标下可以装字符，数字


单词统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
//#include <tr1/unordered_map>  //版本问题，比赛中加上
using namespace std;
//using namespace std::tr1;
int main() {
    int n;
    int ans = 0;
    unordered_map<string, int> cnt;    //第一个为元素值 第二个为元素位置
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string tmp;
        cin >> tmp;
        cnt[tmp]++;
        ans = max(ans, cnt[tmp]);
    }
    cout << ans << endl;
}

字母统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
using namespace std;
//using namespace std::tr1;
int main() {
    string s;
    int ans = 0;
    unordered_map<char, int> cnt;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        cnt[s[i]]++;
        ans = max(ans, cnt[s[i]]);
    }
    cout << ans << endl;
    return 0;
}

数字统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
using namespace std;
//using namespace std::tr1;
int main() {
    int n;
    cin >> n;
    unordered_map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        cnt[tmp]++;
    }
    cout << cnt.size() << endl;
    return 0;
}


算法


高精度

高精度：因为int型范围有限，无法存储大整数，所以用字符串形式输入大整数，再转成int型存入数组中，用数组进行运算


加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int a[501], b[501], c[502];

int main() {
	string x, y;
	cin >> x >> y;
	int len = max(x.length(), y.length());
	for (int i = len-1; i >= 0; i--) a[len-i] = x[i] - '0';	 //将x倒着存进数组a,将字符转为整型
	for (int i = len-1; i >= 0; i--) b[len-i] = y[i] - '0';
	for (int i = 1; i <= len; i++) {
		c[i] += a[i] + b[i];
		c[i+1] = c[i] / 10;		//模拟进位 
		c[i] %= 10;		
	}
	if (c[len+1]) {   //进位可能导致长度加一 
		len++;
	}
	for (int i = len; i >= 1; i--) {    //倒回来输出 
		cout << 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
#include <bits/stdc++.h>
using namespace std;

int a[5010], b[5010], c[5020];

int main() {
	string x, y;
	cin >> x >> y;
	int lenx = x.length(); int leny = y.length();
	for (int i = lenx-1; i >= 0; i--) a[lenx-i] = x[i] - '0';
	for (int i = leny-1; i >= 0; i--) b[leny-i] = y[i] - '0';
	for (int i = 1; i <= lenx; i++) { 	//模拟竖式乘法
		for (int j = 1; j <= leny; j++) {
			c[i+j-1] += a[i] * b[j];     //错位相加
		}
	}
	int len = lenx + leny;    //乘得的积的长度不大于两数长度之和
	for (int i = 1; i <= len; i++) {
		c[i+1] += c[i] / 10;		//模拟进位 
		c[i] %= 10;		
	}
	for (; !c[len] ;) {   	//去掉先导零
		len--;
	}
	for (int i = max(1,len); i >= 1; i--) {    //倒回来输出 
		cout << 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
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
#include <bits/stdc++.h>
using namespace std;
struct Int{
	int len;
	int a[155];
	void init(){
		len=0;
		memset(a,0,sizeof a);
	}
	Int(){init();}
	Int(int x){
		init();
		if(x==0) ++len;
		while(x){
			a[++len]=x%10;
			x/=10;
		}
	}
	Int operator=(int x){
		init();
		if(x==0) ++len;
		while(x){
			a[++len]=x%10;
			x/=10;
		}
		return *this;
	}
	Int operator=(Int x){
		init();
		len=x.len;
		for(int i=1;i<=len;i++) a[i]=x.a[i];
		return *this;
	}
	void print(){
		for(int i=len;i>0;i--){
			printf("%d",a[i]);
		}
	}
};
Int operator+(const Int a,const Int b){
	Int ans;
	ans.len=max(a.len,b.len);
	for(int i=1;i<=ans.len;i++){
		if(i<=a.len) ans.a[i]+=a.a[i];
		if(i<=b.len) ans.a[i]+=b.a[i];
		ans.a[i+1]+=ans.a[i]/10;
		ans.a[i]%=10;
	}
	while(ans.a[ans.len+1]>0) ans.a[ans.len+1]+=ans.a[ans.len]/10,ans.a[ans.len]%=10,ans.len++;
	return ans;
}

Int a[4] = {1,1,1,1};
Int b[4] = {1,999,1,1};

int main() {
	(a[1]+b[1]).print();   //输出为1000 
	return 0;
}


排序


归并

主要体现分治思想，复杂度O(nlogn)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int a[MAXN]; int b[MAXN];

void merge(int l, int mid, int r) {
	memset(b,0,sizeof(b));
	int i = l, j = mid+1, k = 0;
	while(i<=mid&&j<=r) {
		if (a[i]<=a[j]) b[++k] = a[i++];
		else b[++k] = a[j++];
	}
	while(i<=mid) b[++k] = a[i++];
	while(j<=r) b[++k] = a[j++];
	for (int i = 1; i <= k; i++) a[l++] = b[i];
}

void mergesort(int l, int r) {
	if (l < r) {
		int mid = l+r>>1;
		mergesort(l,mid);
		mergesort(mid+1,r);
		merge(l,mid,r);
	}
	return;
}

快排

在数组中随机选择一个数作为标准，比标准小的放标准左边，大的放右边，然后递归分治


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
#include <bits/stdc++.h>
using namespace std;

int a[2000000];

void qsort(int a[], int l, int r) {
    int i = l, j = r;
    int p = a[rand() % (r - l + 1) + l];  
             // ① 如何选取基准数（pivot）No.2 a[(r - l) / 2 + l] No.3 a[l]
    while (i <= j) {
        while (a[i] < p) i++;            // ② 与pivot相等的数，要不要交换？
        while (a[j] > p) j--;
        if (i <= j) {                    // ③ 为什么要写if？为什么要加等号？
            swap(a[i++], a[j--]);
        }
    }
    
    if (l < j) qsort(a, l, j);           // ④ 这两条语句什么含义
    if (i < r) qsort(a, i, r);
}

int main(void) {
    int n;

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    qsort(a, 1, n);

    for (int i = 1; i <= n - 1; i++) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n]);
}


暴力枚举

枚举，很暴力！
将数据全部枚举一遍，加以判断或统计
如果全部枚举会超范围，就要考虑更换枚举的元素或剪枝（减少枚举量），即优化枚举


循环枚举-烤鸡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define rep(a, i, j) for (int a = i; a <= j; a++)     //利用宏（define）构造语句的功能，简化for循环，前者等价于后者
using namespace std;
int main() {
	int n, a, b, c, d, e, f, g, h, i, j;
	scanf("%d", &n);
	int ans = 0;
	rep(a, 1, 3) rep(b, 1, 3) rep(c, 1, 3) rep(d, 1, 3) rep(e, 1, 3)      //优雅的枚举
		rep(f, 1, 3) rep(g, 1, 3) rep(h, 1, 3) rep(i, 1, 3) rep(j, 1, 3) 
			if (a+b+c+d+e+f+g+h+i+j == n) 
				ans++;
	printf("%d\n", ans);
	rep(a, 1, 3) rep(b, 1, 3) rep(c, 1, 3) rep(d, 1, 3) rep(e, 1, 3)
		rep(f, 1, 3)rep(g, 1, 3)rep(h, 1, 3)rep(i, 1, 3)rep(j, 1, 3)
			if (a+b+c+d+e+f+g+h+i+j == n) 
				printf("%d %d %d %d %d %d %d %d %d %d\n", a, b, c, d, e, f, g, h, i, j);
	return 0;
}

排列枚举-全排列

即将每种情况排列，用STL中函数next_permutation（start,end）即可解决
next_permutation函数求的是给定范围中按顺序的下一个排列，若没有下一个排列则返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int a[11];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		a[i] = i;		//因为next需要数据范围，所以将i赋值到数组，而不是直接用i
	}
	do {				//用do-while是为了使最后一个排序能够输出，while和for需要特判
		for (int i = 1; i <= n; i++) {
			cout << setw(5) << a[i];  //场宽5
		}
		cout << endl;
	} while (next_permutation(a+1, a+1+n));    //指针操作 next所到之处，就是当前次数下的排列
	return 0;
}


递归

递归 就是套娃，自己算自己
相当于一个公司，用函数调用手下去算
通过函数中的return不断返回，当不断返回然后不能返回了就输出或达到某种要求输出
一定要有退出条件

递归分为两种：数值类和非数值类，
数值类更加简单，根据函数定义直接找出递归边界和递归语句（注意要用if-else连接）
非数值类则需模拟，找规律，再重复数值类步骤


斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int calc(int a) {
	if (a == 1 || a == 2) {
		return 1;
	}
	return calc(a - 1) + calc(a - 2);
}
int main() {
	int k;
	cin >> k;
	cout << calc(k) << endl;
	return 0;
}

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
int main() {
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << endl;
	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;
struct TreeNode {
	int val;
	int l, r;
};
vector<TreeNode> tree(200000); 
int getMax(int root) {
	if (root == -1) {
		return INT_MIN;
	}
	int lMax = getMax(tree[root].l);
	int rMax = getMax(tree[root].r);
	int ans = max(lMax, rMax);
	ans = max(ans, tree[root].val);
	printf("%d ", ans);
	return ans;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &tree[i].val, &tree[i].l, &tree[i].r); 
	}
	getMax(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
#include <bits/stdc++.h>
using namespace std;
int a[200000];
int n;
int find(int t) {
	int l = 1, r = n;
	while (l <= n) {
		int mid = l + (r - l) / 2;
		if (a[mid] == t) {
			return mid;
		}
		if (a[mid] < t) {
			l = mid + 1;
		}
		if (a[mid] > t) {
			r = mid - 1;
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int m;
	cin >> m;
	while (m--) {
		int t;
		cin >> t;
		cout << find(t) << endl;
	}
	return 0;
}


DFS

又称深度优先搜索或回溯法


摸球问题

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 n, m;
void dfs(int x, string path) {
	if (x == n + 1) {
		printf("%s\n", path.c_str());
		return;
	}
	for (int i = 1; i <= m; i++) {
		dfs(x + 1, path + (char)(i + '0'));
	}
} 
int main() {
	scanf("%d %d", &n, &m);
	dfs(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
#include <bits/stdc++.h>
using namespace std;
int n;
bool v[100];
void dfs(int x, string path) {
	if (x == n + 1) {
		printf("%s\n", path.c_str());
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (v[i]) {
			continue;
		}
		v[i] = true;
		dfs(x + 1, path + (char)(i + '0'));
		v[i] = false;
	}
} 
int main() {
	scanf("%d", &n);
	dfs(1, "");
	return 0;
}