算法基础

First Post:

Last Update:

一.排序

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
#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n, i, j;
int q[N];
void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;

int x = q[(l+r)/2]; i = l - 1; j = r + 1;
while (i<j)
{
	do i++; while (q[i] < x);
	do j--; while (q[j] > x);
	if (i<j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);

}

int main()
{
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &q[i]);
	}
	quick_sort(q, 0, n - 1);
	for (i = 0; i < n; i++)
	{
		printf("%d", q[i]);
	}
	return 0;
}

2.归并排序

归并排序（acwing 逆序对的数量）

个人理解，归并排序在递归完成之后会将整个数组相邻两个数分为一组，这时，只存在左右两边的情况，而本层计算完成之后，返回上一层计算，这里的同时在 一边的逆序数对刚刚已经计算完了（往上一层分组减少一半），所以只需要计算跨左右的情况就可以了

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
 
#include <iostream>
#include <algorithm>
using namespace std;

#define array arr
const int N = 100010;
int array[N];
int nums;
unsigned long result = 0;

void merge_sort(int array[], int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(array, l, mid);//递归左右两边  递归结果就是两个为一组
    merge_sort(array, mid + 1, r);//
    int temp[r - l + 1];
    int lptr = l;
    int rptr = mid + 1;
    int tempptr = 0;
    while (lptr <= mid && rptr <= r)
    {
        if (array[lptr] <= array[rptr])
        {
            temp[tempptr++] = array[lptr++];
        }
        else {
            temp[tempptr++] = array[rptr++];
            result += (mid - lptr + 1);//注意这里，是直接加的，后面的不需要比较了。
        }
    }
    while (lptr <= mid)
    {
        temp[tempptr++] = array[lptr++];
    }
    while (rptr <= r)
    {
        temp[tempptr++] = array[rptr++];
    }
    for (int i = l, j = 0; i <= r; i++, j++)
    {
        array[i] = temp[j];
    }
}

int main() {
    scanf("%d", &nums);
    for (int i = 0; i < nums; i++)
    {
        scanf("%d", &array[i]);
    }
    merge_sort(array, 0, nums - 1);
    cout << result;
    return 0;
}

二.查找

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
#include <iostream>
using namespace std;
int main()
{
	int n, num[105], targe;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	cin >> targe;
	int l = 0, r = n - 1;

	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (num[mid] == targe)
		{
			cout << targe << "in index" << mid << endl;
			return 0;
		}
		if (num[mid] < targe)
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << "no" << endl;
	return 0;
}

三.数据结构

1.Trie树

高效的存储和查找字符串集合的数据结构

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
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
int i;
void insert(char str[])//插入一个字符串
{
	int p = 0;//节点 从零开始
	
	for ( i = 0; str[i]; i++)
	{
		int u = str[i] - 'a';
		if (!son[p][u]) son[p][u] = ++idx;//如果没有对应的下一节点，创造一个 idx给了个编号
		p = son[p][u];       //idx是每次加一的，所以使得p每次加一；
		//也就是上一节点存储下一节点的位置，在接下来查找的时候才可以找到
	}

	cnt[p]++;//以p为节点的结束次数！！！
}

int query(char str[])//查找
{
	int p = 0;
	for ( i = 0; str[i]; i++)
	{
		int u = str[i] - 'a';
		if (!son[p][u]) return 0;
		p = son[p][u];//son[p][u]的值就是下一个节点的坐标
	}
	return cnt[p];
}

char str[N];
int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		char op[2];
		scanf("%s%s", op,str);
		if (op[0] == 'I') insert(str);
		else printf("%d\n", query(str));

	}
	return 0;
}

2.并查集

1.将两个集合合并
2.询问两个元素是否在一个集合中

原理：每个集合用一颗树来表示，树根的编号就是集合的编号；每个节点存储他的父节点
p[x]表示x的父节点
1.如何判断树根 p[x]=x则是树根
2.如何求x的树根编号： while(p[x]!=x) x=p[x]; 只要不等，一直往上走；
3.如何合并集合 两棵树 一颗插入另一颗
px是x的集合编号 py是y的集合编号 p[x]=y 即可

对2. 优化：（路径压缩） 一旦往上走找到根节点，那么将该路径上的所有点直接指向根节点 大概为o1的时间复杂度

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
 
int find(int x)//核心
{
	if (p[x] != x) p[x] = find(p[x]);//返回x的祖宗节点 并且加路径优化
	return p[x];
}
 
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i++) p[i] = i;

	while (m--)
	{
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);

		if (op[0] == 'M')
		{
			p[find(a)] = find(b);//把b的祖宗节点插入a的祖宗节点下当儿子
		}
		else
		{
			if (find(a) == find(b))
			{
				puts("yes");
			}
			else
				puts("No");
		}
	}
	return 0;
}

3.前缀和

求区间 [r,l] 之中数的和

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main()
{
	scanf("%d%d", &n, &m);//n个数  m次操作
	for (int i = 1; i <= n; i++)//注意是1~n
	{
		scanf("%d", &a[i]);//读入n个数
	}
	for (int i = 1; i <= n; i++)//注意1~n
	{
		s[i] = s[i - 1] + a[i];//预处理
	}
	while (m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);//求l到r区间的和
		printf("%d\n", s[r] - s[l - 1]);
	}

	return 0;
}

4.差分

（前缀的逆运算）

在指定区间都加c（原数组a[N]）
由o(n) 到 o(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
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)//1~n
    {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i - 1];      //构建差分数组
    }
    int l, r, c;
    while (m--)
    {
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;     //将序列中[l, r]之间的每个数都加上c
        b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++)//1~n
    {
        a[i] = b[i] + a[i - 1];    //前缀和运算
        printf("%d ", a[i]);
    }
    return 0;
}

5.单链表

数组模拟的，但其实通常用stl

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
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int e[N], ne[N], head, idx;

//对链表进行初始化
void init() {
    head = -1;//最开始的时候，链表的头节点要指向-1，
    //为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束
    /*
    插句题外话，我个人认为head其实就是一个指针，是一个特殊的指针罢了。
    刚开始的时候它负责指向空结点，在链表里有元素的时候，它变成了一个指向第一个元素的指针

    当它在初始化的时候指向-1，来表示链表里没有内容。
    */
    idx = 0;//idx在我看来扮演两个角色，第一个是在一开始的时候，作为链表的下标，让我们好找
    //第二在链表进行各种插入，删除等操作的时候，作为一个临时的辅助性的所要操作的元素的下
    //标来帮助操作。并且是在每一次插入操作的时候，给插入元素一个下标，给他一个窝，感动！
    /*
    再次插句话，虽然我们在进行各种操作的时候，元素所在的下标看上去很乱，但是当我们访问的
    时候，是靠着指针，也就是靠ne[]来访问的，这样下标乱，也就我们要做的事不相关了。
    另外，我们遍历链表的时候也是这样，靠的是ne[]
    */
}
//将x插入到头节点上
void int_to_head(int x) {//和链表中间插入的区别就在于它有head头节点
    e[idx] = x;//第一步，先将值放进去
    ne[idx] = head;//head作为一个指针指向空节点，现在ne[idx] = head;做这把交椅的人换了
    //先在只是做到了第一步，将元素x的指针指向了head原本指向的
    head = idx;//head现在表示指向第一个元素了，它不在是空指针了。（不指向空气了）
    idx++;//指针向下移一位，为下一次插入元素做准备。
}
//e[idx]=x;
// ne[idx]=head;
// head=idx;
// idx++;
//将x插入到下标为k的点的后面
void add(int k, int x) {
    e[idx] = x;//先将元素插进去    e[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;
    ne[idx] = ne[k];//让元素x配套的指针，指向它要占位的元素的下一个位置
    ne[k] = idx;//让原来元素的指针指向自己
    idx++;//将idx向后挪

}

//将下标是k的点后面的点个删掉
void remove(int k) {
    ne[k] = ne[ne[k]];//让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。
}
//ne[k]=ne[ne[k]]//传进来的是k-1
int main() {
    cin >> n;
    init();//初始化
    for (int i = 0; i < n; i++) 
    {
        char s;
        cin >> s;
        if (s == 'H') {
            int x;
            cin >> x;
            int_to_head(x);
        }
        if (s == 'D') {
            int k;
            cin >> k;
            if (k == 0) head = ne[head];//删除头节点
            else remove(k - 1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1
        }
        if (s == 'I') {
            int k, x;
            cin >> k >> x;
            add(k - 1, x);//同样的，第k个数，和下标不同，所以要减1
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

6.队列

我觉得是一个双指针在维护这个数据结构吧
先进的先出 后进的后出
tt就是维护队尾位置的下标
如果要队头出列的话 hh++就可以 遍历的时候i<=hh就可以了（输出时候队头开始遍历）

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
#include<iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10;
int qu[N], hh = 0, tt = -1;//初始化很重要！！！
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        string a;
        cin >> a;
        if (a == "push")
            cin >> x, qu[++tt] = x;//元素只能队尾入队
        else if (a == "pop")
            hh++;//注意元素只能队头弹出，且是 ++
        else if (a == "empty")//队内是否为空
        {
            if (tt < hh)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;

        }
        else//查询队头
            cout << qu[hh] << endl;
    }
 
    for (int i = tt; i <= hh; i++)
    {
        printf("%d", qu[i]);
    }

    return 0;
}

四.搜索

1.DFS

输出n个数的全排列

（DFS八皇后也仅仅是扩展到二维数组而已 （acwing））

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
#include <iostream>
using namespace std;

const int N = 10;
int n;
bool book[N];
int st[N];

void dfs(int u)
{
	if (u > n)
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d", st[i]);
		}
		printf("\n");
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!book[i])
		{
			st[u]=i;
			book[i] = true;
			dfs(u + 1);
			
						 //能走到这一步说明是打印完之后return的，来到了当时的上一层，在这
			st[u] = 0;  //回溯
			book[i] = false;  
			////////  忘了时候再仔细调试看看，终于懂了。
		}
	}
}

int main()
{
	cin >> n;
	dfs(1);
	return 0;
}


1.1dfs的例题

dfs的指数级枚举，真的妙！！！ 

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 <iostream>
using namespace std;
const int N = 1e1 + 6; //定义一个常量N
int n;
int st[N];  //记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它

void dfs(int u) // 枚举的第几个数字
{
    if (u > n) {
        //终止条件，因为题目要求一个就n个数 所以只有 u > n 就输出枚举的方案
        for (int i = 1; i <= n; i++)
            if (st[i] == 1)
                printf("%d ", i);
        puts("");
        return;
    }
    st[u] = 1;   //选它的分支
    dfs(u + 1);
    st[u] = 0;   //恢复现场，以便进行下一个分支

    st[u] = 2; //  不选它的分支
    dfs(u + 1);
    st[u] = 0;  // 恢复现场
}
int main(void)
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

2.BFS

在DFS中我们说关键点是递归以及回溯，

在BFS中，关键点则是状态的选取和标记

BFS 迷宫：
一个while大循环，只要不空就以一直走 每次取出队头
下面一个for的四个方向的循环 符合条件就会向外扩展 注意都是扩展在t的基础上的（一个点）
然后：每个被扩展出来的都会进队列，继续扩展，如果扩展不了就四个for都不满足，在下一次循环中他就被弹出了

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
#include<iostream>
#include <queue>
using namespace std;
#define x first
#define y second 
int n, m;
typedef pair<int, int>PII;
int a[110][110];   //储存地图
int dis[110][110];  //储存距离
int pos[4][2] = { -1,0,0,1,1,0,0,-1 }; //偏移量数组
void bfs(PII start)
{
    queue<PII> q;
    q.push(start);		//初始状态入队
        while (!q.empty()) 	//队列不空时
        {
            PII t = q.front();       // 取出队首元素，存放到 t 变量里 ，元素出队
            q.pop(); 				//元素出队
            for (int i = 0; i < 4; i++)//	扩展 t 结点
        {
           int tx = t.x + pos[i][0],ty = t.y + pos[i][1];
           if (a[tx][ty] == -1 || a[tx][ty] == 1)continue; //判断是否越界或者碰到障碍
           if (a[tx][ty] == 0)		//如果未被访问，
           {
               dis[tx][ty] = dis[t.x][t.y] + 1; //记录当前点到起点的距离
               a[tx][ty] = -1;			    //标记扩展的新结点被访问
               q.push({tx,ty});				//将扩展的新节点入队
           }
           if (tx == n && ty == m) //如果到达右下角
           {
           cout << dis[tx][ty]; //返回右下角到起点的距离
           return;
           }
        }
        }
}
int main()
{
    cin >> n >> m;
    memset(a, -1, sizeof a); //初始化为 - 1 ，这样方便 判断边界
        for (int i = 1; i <= n; i++) //从1开始读入地图方便判断边界，这样地图都会被初始化的 - 1 包围
            for (int j = 1; j <= m; j++) //这样判断扩展的点是否越界时，只要判断是不是 - 1 即可
            {
                cin >> a[i][j];
            }
    PII start; //定义一个二元组，储存起点，传入到BFS函数里
        start.x = 1, start.y = 1;
    bfs(start);
    return 0;
}

五.感悟

1.csp 201403-2（窗口）

独立完成，有点开心，放在这吧

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
#include <iostream>
using namespace std;
int n, m;
int a[2600], b[1500], c[2600], d[1500];
int s[2600][1500];
void chu(int a, int b, int c, int d, int q)
{
	for (int i = a; i <= c; i++)
	{
		for (int j = b; j <= d; j++)
		{
			s[i][j] = q;
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int q=1;q<=n;q++)
	{
		cin >> a[q] >> b[q] >> c[q] >> d[q];
		chu(a[q], b[q], c[q], d[q], q);
	}
	while(m--)
	{
		int x, y;
		cin >> x >> y;
		if (s[x][y] > 0)
		{
			cout << s[x][y]<<endl;
			
		}
		else
		{
			cout << "IGNORED\n";
		}
		chu(a[s[x][y]], b[s[x][y]], c[s[x][y]], d[s[x][y]], s[x][y]);
	}
	return 0;
}