摘要：

longlongint的范围-9223372036854775808～9223372036854775807。19位数，小于10的19次方 （用%lld输出）

int范围是-2147483648～2147483647（2的31次方） 小于10的10次方 10位数

链表

结构体

1
2
3
4
typedef class node{
public: int data;
	 node* next;
}Node;

正序插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
node* zhengxu() {
	node* head = NULL;
	node* n1 = new node();
	n1->next = NULL;
	 head = n1;
	int d;
	printf("请输入链表的长度:");
	scanf_s("%d", &d);
	for (int i = 0;i < d;i++)
	{
		printf("请输入第%d个数的值：", i + 1);
		node* n = new node();
		scanf_s("%d", &n->data);
		n1->next = n;
		n1 = n;
	}
	return head;
}

倒序插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
node* daoxu() {
	node* head = NULL, * tem = NULL;
	node* n1 = new node();
	n1->next = NULL;
	head = n1;
	int d;
	printf("请输入链表的长度");
	scanf_s("%d", &d);
	for (int i = 0;i < d;i++)
	{
		printf("请输入第%d个数的值：", i + 1);
		node* n = new node();
		scanf_s("%d", &n->data);
		n1->next = n;
		if (i >= 1) { n->next = tem; }
		tem = n;
	}
	return head;
}

遍历

1
2
3
4
5
6
7
8
9
10
void bianli(node* &head)
	{
	node* p1 = head->next;
	int i = 1;
	while (p1) {
		printf("第%d个节点值为：%d\n",i, p1->data);
		p1 = p1->next;
		i++;
	}
}

树

1.DFS深度优先算法

2.BFS广度优先算法

广搜模板

1
2
3
4
5
6
7
8
9
10
11
12
13
//广搜模板
q.push(初始状态)；
while(!q.empty()){
	a= q.front();
	q.pop();
	for(枚举a的所有可达状态v){
		if(本状态v合法){
			执行标记操作；
			q.push(v);
		}
	}
)

例题

P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.输入数据n,m,起始点(x0,y0)
2.将起始点的位置标记为0 m[x0][y0]=0
3.q.push (x0,yo)
4.循环直到q为空：
取出队列头的点(x,y)
对这个点模拟马跳，对能跳到的位置，判断合法性：是否在棋盘，是否为-1
将找到的点的值赋值为m[x][y]+1
将找到的点push入队列中
5.输出

3.最短路之dijkstra

4.最短路之SPFA

5.最短路之Floyd

6.高精度

此题解只面对与刚刚学算法的童鞋们

  • 什么情况下要使用高精度？

当两个数超过longlong的大小并且要对这两个大数进行运算的时候。

  • 既然数这么大，我们用什么存放呢？

用字符串存放。

  • 怎么运算呢？

小学学加法的时候，我们是从最低位开始计算，两两相加，逢十进一。

我们也可以用计算机模拟这一过程。

具体代码：

1
2
3
4
5
6
7
for(j=1; j<=max(a[0],b[0])+1; j++) {
	c[j]=a[j]+b[j];
	if(c[j]>=10) {
		c[j]%=10;
		a[j+1]++;
	}
}
  • 既然要进行运算，我们总得知道字符串的长度吧？怎么获取呢？

用strlen函数。

1
2
a[0]=strlen(s);
b[0]=strlen(ss);
  • 要运算，怎么知道某一位的具体数值是几呢？

这个跟ascll码有关了。

img

一个字符数字的ascll码－48（也就是0的ascll码）就是那个数字的ascll码。

转化过程：

1
2
for(int i=1; i<=a[0]; i++) a[i]=s[a[0]-i]-'0';//倒序存入数组，从低到高位
for(int i=1; i<=b[0]; i++) b[i]=ss[b[0]-i]-'0';

☆ 注意：

一定要考虑进位！！

具体的说，就是最高位相加时可能会有进位，需特判。

如果dalao们看前面的不顺眼觉得蔡那看看这个：

读入第一行字符串A与第二行字符串B，

将两串字符串的每个字符转成数字存储在数组中，字符转数字的方式是：ch-’0’

我们将个位存在a[1]，高位存在a[l]，l是数字位数，也即字符串长度。

字符串B也用一个数组b来记录。

高精度加法就是模拟加法的过程，我们要做的就是让a和b的每一位相加，并判断任意一位数是否大于等于1010，即应进位的问题。

处理完进位同时也要考虑最终和的位数（长度）是否有变化。 最终逐位输出达成输出大数的效果。

说了这么多，上一下AC代码：

高精度加法

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[1000001],b[1000001],c[1000001],j;
bool x=false;
char s[1000001],ss[1000001];//或string s,ss;
int main() {

	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));//初始化
	scanf("%s%s",s,ss);//读入两个数
	a[0]=strlen(s);
	b[0]=strlen(ss);//获取长度
	for(int i=1; i<=a[0]; i++) a[i]=s[a[0]-i]-'0';
	for(int i=1; i<=b[0]; i++) b[i]=ss[b[0]-i]-'0';//转化为数字
	for(j=1; j<=max(a[0],b[0])+1; j++) {
		c[j]=a[j]+b[j];
		if(c[j]>=10) {
			c[j]%=10;
			a[j+1]++;//或者让c[j+1]++，然后上面换成c[j]+=a[j]+b[j];
		}
	}//模拟加法
	c[0]=j;
	if(c[j+1]>0) c[0]++;//特判进位
	for(int i=c[0]; i>=1; i--) {//输出（删除前导零）
		if(x==false&&c[i]==0) continue;
		x=true;
		cout<<c[i];
	}
	if(x==false) cout<<0;//一重保险
	printf("\n");//二重保险
	return 0;//三重保险
}

在以后的学习中，高精度会成为一个很重（ke）要（pa）的算法，Ta会成为一种工具。

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mul(int n){
int tem =0;
for(int i=0;i<slen;i++)s[i]*=n;
for(int i=0;i<slen;i++){
tem= tem+s[i];
s[i]=tem% 10;
tem/=10;}
while(tem !=0){		//防止进位过多
s[slen]=tem% 10;
slen++;
tem/=10;
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
37

int main() {
	string n1, n2;
	cin >> n1 >> n2;
	int a1[10000] = { 0 }, b1[10000] = { 0 }, c1[10000] = { 0 };
	a1[0] = n1.size();
	b1[0]=	n2.size();
	bool flag = false;
	for (int i = 1;i <= n1.size();i++) 
	{
		a1[a1[0] - i + 1] = n1[i-1]-'0';
	}
	for (int i = 1;i <= n2.size();i++)
	{
		b1[b1[0] - i + 1] = n2[i - 1]-'0';
	}
	
	for (int i = 1;i <= n1.size();i++)
	{
		for (int j = 1;j <= n2.size();j++)
		{
			c1[i + j - 1]+= a1[i] * b1[j];
			c1[i + j] += c1[i + j - 1] / 10;
			c1[i + j -1] = c1[i + j - 1] % 10;

		}

	}
	for (int i = n1.size() + n2.size();i >= 1;i--)
	{
		if (flag || c1[i] != 0 ||i==1) { flag = true;cout << c1[i]; }
		
	}

    return 0;
}

用高精度算法算一个数的阶乘(并相加) —-洛谷1009

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
这种算法适用于一个数小的时候，也就是在int范围以内，否则就要用上面那个用字符串接收再相乘，这个可以直接相乘。
int main()
{
	int n,t=0,a[10000] = { 0 }, b[10000] = { 0 };
	bool flag = false;
	cin >> n;
	a[0] = 1; //1*任何数都等于它本身
	b[0] = 1;//赋值为1，是为了加上1的阶乘，也就是1
	for (int i = 2;i <= n;i++)
	{

		for (int j = 0;j < 10000;j++)
		{
			a[j] = t + a[j] * i;
			t = a[j] / 10;
			a[j] = a[j] % 10;

		} //用原数组的每一位分别乘这个数（重点理解！）
		
		for (int j = 0;j < 10000;j++)
		{
			b[j] += a[j];
			b[j + 1] += b[j] / 10;
			b[j] = b[j] % 10;
		}//阶乘相加，高精度算法

	}
	for (int i = 100;i >= 0;i--)
	{
		if (flag || b[i] != 0)
		{
			flag = true;
			cout << b[i];
		}//消除前导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
这一种方法可以计算最后数组里面的有效长度，也就是p

int a[5000];
 for (int i = 1;i <= 1001;i++)
    a[i] = 0;//将数组清零。
a[1] = 1;//必须设为1。不能为0，不然怎么乘都是0。
int n, i, j, k, m;
int p = 1, jw = 0;//p代表位数，jw代表进位。
scanf("%d%d", &n, &m);
for (i = 2;i <= n;i++)//从2开始，反正任何数乘1还等于它本身。
{
    jw = 0;
    for (j = 1;j <= p;j++)//高精度*单精度。
    {
        a[j] = a[j] * i + jw;//高精度*单精度+进位。
        jw = a[j] / 10;//设置进位。
        a[j] = a[j] % 10;
    }
    while (jw > 0)//如果还有进位，处理进位。
    {
        a[j] = jw % 10;//此时j已经为p+1，因为加了一，不满足循环跳出来了
        jw /= 10;
        j++;
    }
    p = j - 1;
}

7.最小生成树之kruskal

【最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示】https://www.bilibili.com/video/BV1Eb41177d1?vd_source=626e2d95a6f6efebc61310d99bac2d29

最小生成树-Kruskal算法_独钓烟云的博客-CSDN博客

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
int father[maxn];//father数组存放的是父亲结点
struct Edge{
	int u;//左端点
	int v;//右端点
	int dis;//权值
}ed[maxn];
bool cmp(Edge a,Edge b){//结构体排序
	return a.dis < b.dis;
}
void init(int n){//初始化
	for(int i=1;i<=n;i++) father[i] = i;
}
int find_father(int x){//并查集核心操作
	if(x==father[x]) return x;//此种情况是找到了最终父亲，也就是根节点
	int temp = find_father(father[x]);//路径压缩
	return temp;
}
int Kruskal(int n,int m){
	int ans = 0;//记入最小生成树的权值
	int num_Edge = 0;//边的数目
	for(int i=0;i<m;i++){
		int fu = find_father(ed[i].u);//找最终父亲
		int fv = find_father(ed[i].v);//找最终父亲
		if(fu!=fv){//如果两个节点的最终父亲都一样，则说明两个节点都已经在集合里
			father[fu] = fv;//合并，每次都让新节点的父节点赋值为根节点
			ans+=ed[i].dis;
			num_Edge++;
			if(num_Edge==n-1) break;
		}
	}
	if(num_Edge!=n-1) return -1;//退出条件
	else return ans;
}
int main(){
	int n,m;
	cin>>n>>m;
	init(n);
	for(int i=0;i<m;i++) cin>>ed[i].u>>ed[i].v>>ed[i].dis;//输入
	sort(ed,ed+m,cmp);//排序
	cout<<Kruskal(n,m);
	return 0;
}



8.最小生成树之prim

最小生成树——Prim算法（详细图解）_prim最小生成树_skynesser的博客-CSDN博客

注意，最小生成树可能有很多种，但最后的权值都是相同的，所以遇见两个最小值相同的边取哪一条都可以！

1
2
3
4
5
const int MAXN = 1000,INF = 0x3f3f3f3f;//定义一个INF表示无穷大。
int g[MAXN][MAXN],dist[MAXN],n,m,res;
//我们用g[][]数组存储这个图，dist[]储存到集合S的距离，res保存结果。
bool book[MAXN];//用book数组记录某个点是否加入到集合S中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    cin>>n>>m;//读入这个图的点数n和边数m
    for(int i = 1 ; i<= n ;i++)
    {
        for(int j = 1; j <= n ;j++)
        {
            g[i][j] = INF;//初始化任意两个点之间的距离为正无穷（表示这两个点之间没有边）
        }
        dist[i] = INF;//初始化所有点到集合S的距离都是正无穷
    }
    for(int i = 1; i <= m ; i++)
    {
        int a,b,w;
        cin>>a>>b>>w;//读入a，b两个点之间的边
        g[a][b] = g[b][a] = w;//由于是无向边，我们对g[a][b]和g[b][a]都要赋值
    }
    prim();//调用prim函数
    if(res==INF)//如果res的值是正无穷，表示不能该图不能转化成一棵树，输出orz
        cout<<"orz";
    else
        cout<<res;//否则就输出结果res
    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
void prim()
{
    dist[1] = 0;//把点1加入集合S，点1在集合S中，将它到集合的距离初始化为0
    book[1] = true;//表示点1已经加入到了S集合中
    for(int i = 2 ; i <= n ;i++)dist[i] = min(dist[i],g[1][i]);//用点1去更新dist[]
    for(int i = 2 ; i <= n ; i++)
    {
        int temp = INF;//初始化距离
        int t = -1;//接下来去寻找离集合S最近的点加入到集合中，用t记录这个点的下标。
        for(int j = 2 ; j <= n; j++)
        {
            if(!book[j]&&dist[j]<temp)//如果这个点没有加入集合S，而且这个点到集合的距离小于temp就将下标赋给t
            {
                temp = dist[j];//更新集合V到集合S的最小值
                t = j;//把点赋给t
            }
        }
        if(t==-1){res = INF ; return ;}
        //如果t==-1，意味着在集合V找不到边连向集合S，生成树构建失败，将res赋值正无穷表示构建失败，结束函数
        book[t] = true;//如果找到了这个点，就把它加入集合S
        res+=dist[t];//加上这个点到集合S的距离
        for(int j = 2 ; j <= n ; j++)dist[j] = min(dist[j],g[t][j]);//用新加入的点更新dist[]
    }
}

9.树的直径——BFS

10.树的直径——DFS

11.树的直径——树形DP

12.树状数组

13.字典树

14.线段树

二分

暴力枚举（适合数据范围小的时候，比如100以内，常见for循环）

P3392 涂国旗 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
int n,m,ans,mi=inf;//mi初始化成一个很大的数
char c[N][N];
int main()
{
	int i,j,k,g;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	  for(j=1;j<=m;j++) cin>>c[i][j];
	for(i=1;i<=n-2;i++)//由于白色下面还有蓝色和红色，所以i（白与蓝的边界）枚举到（n-2）
	  for(j=i+1;j<=n-1;j++)//j（蓝与红的边界）至少要比i大1，同理枚举到（n-1），这样可以减少枚举次数
	  {
	    ans=0;//初始化
        //壮观地枚举三个区域
	    for(k=1;k<=i;k++)
	      for(g=1;g<=m;g++) if(c[k][g]!='W') ans++;
	    for(k=i+1;k<=j;k++)
	      for(g=1;g<=m;g++) if(c[k][g]!='B') ans++;
	    for(k=j+1;k<=n;k++)
	      for(g=1;g<=m;g++) if(c[k][g]!='R') ans++;
        //强迫症（本蒟蒻）看到这些语句表示很开心
	    mi=min(ans,mi);//更新答案
	  }
	cout<<mi<<endl;
	return 0;
}

前缀和

后缀和

位运算

网络流

分块

LCT

Splay

LCA

Bellman-Ford

可耻的打表

SPFA算法

SPFA求最短路之SLF优化

SPFA之LLL优化

SPFA之SLF+LLL优化算法

只用一个变量

矩阵乘法

STL+dijkstra

数学表达式

压位高精度加法

矩阵DP

十大经典排序算法

0、算法概述

0.1 算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
在这里插入图片描述

0.2 算法复杂度

在这里插入图片描述

0.3 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机
内执行时所需存储空间的度量，它也是数据规模n的函数。

1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

1.2 动图演示

在这里插入图片描述

1.3 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
12345678910111213

2、选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

2.2 动图演示

在这里插入图片描述

2.3 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
} 
12345678910111213141516
2.4 算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

3.2 动图演示

在这里插入图片描述

3.2 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
1234567891011121314
3.4 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

4、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动图演示

在这里插入图片描述

4.3 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}
12345678910111213141516
4.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

5、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

在这里插入图片描述

5.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
27
28
29
30
31
function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}
123456789101112131415161718192021222324252627282930
5.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

6、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

6.1 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

6.2 动图演示

在这里插入图片描述

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
27
28
29
30
31
32
33
function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
 
function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }       
    }
    swap(arr, pivot, index - 1);
    return index-1;
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1234567891011121314151617181920212223242526272829303132

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

7.1 算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

7.2 动图演示

在这里插入图片描述

7.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
 
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344

8、计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

8.2 动图演示

在这里插入图片描述

8.3 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}
12345678910111213141516171819202122
8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
9.2 图片演示
在这里插入图片描述

9.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

9.4 算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

10、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

10.1 算法描述

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

10.2 动图演示
10.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
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}
123456789101112131415161718192021222324
10.4 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

快速幂

差分

二进制

背包

1.01背包

2.完全背包

3.多重背包之暴力拆分法

4.多重背包之二进制拆分

5.二维费用背包问题

6.分组背包问题

7.有依赖的背包问题

8.多重背包队列优化

istream_iterator

进制转换

指针算法

c++自带算法

C++ 标准模板库 (STL, Standard Template Library)：包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).

示例：

  • 算法：sort(a.begin(), a.end())
  • 容器：priority_queue<int> pque
  • 仿函数：greater<int>()
  • 迭代器：vector<int>::iterator it = a.begin()

1 前言

STL 作为一个封装良好，性能合格的 C++ 标准库，在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间，这一点不仅是由于可以直接调用，还是因为它封装良好，可以让代码的可读性变高，解题思路更清晰，调试过程 往往 更顺利。

不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能，它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此，STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此，在实际比赛中要权衡 STL 的利弊，不过这一点就得靠经验了。

接下来，我会分享在算法竞赛中常用的 STL 容器和算法，对于函数和迭代器，就不着重展开讲了。

2 常用容器

2.1 内容总览

打勾的是本次将会详细讲解的，加粗的是算法竞赛中有必要学习的。

  • 顺序容器
    • [ ] array
    • [x] vector
    • [ ] deque
    • [ ] forward_list
    • [ ] list
  • 关联容器
    • [x] set
    • [x] map
    • [ ] multiset
    • [ ] multimap
  • 无序关联容器
    • [ ] unordered_set
    • [ ] unordered_map
    • [ ] unordered_multiset
    • [ ] unordered_multimap
  • 容器适配器
    • [x] stack
    • [x] queue
    • [x] priority_queue
    • [ ] flat_set
    • [ ] flat_map
    • [ ] flat_multiset
    • [ ] flat_multimap
  • 字符串
    • [x] string (basic_string\)
  • 对与元组
    • [x] pair
    • [ ] tuple

2.2 向量 vector

#include <vector>

连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

2.2.1 常用方法

构造

vector<类型> arr(长度, [初值])

时间复杂度：O(n)

常用的一维和二维数组构造示例，高维也是一样的（就是会有点长）.

1
2
3
4
5
6
vector<int> arr;         // 构造int数组
vector<int> arr(100);    // 构造初始长100的int数组
vector<int> arr(100, 1); // 构造初始长100的int数组，初值为1

vector<vector<int>> mat(100, vector<int> ());       // 构造初始100行，不指定列数的二维数组
vector<vector<int>> mat(100, vector<int> (666, -1)) // 构造初始100行，初始666列的二维数组，初值为-1

构造二维数组的奇葩写法，千万别用：

1
2
3
4
vector<int> arr[100];         // 正确，构造初始100行，不指定列数的二维数组，可用于链式前向星存图
vector<int> arr[100](100, 1); // 语法错误！
vector<int> arr(100, 1)[100]; // 语法错误！
vector<int> arr[100] {{100, 1}, 这里省略98个 ,{100, 1}}; // 正确但奇葩，使用列表初始化

尾接 & 尾删

  • .push_back(元素)：在 vector 尾接一个元素，数组长度 +1+1.
  • .pop_back()：删除 vector 尾部的一个元素，数组长度 −1−1

时间复杂度：均摊 O(1)

1
2
3
4
5
6
7
8
9
// init: arr = []
arr.push_back(1);
// after: arr = [1]
arr.push_back(2);
// after: arr = [1, 2]
arr.pop_back();
// after: arr = [1]
arr.pop_back();
// after: arr = []

中括号运算符

和一般数组一样的作用

时间复杂度：O(1)

获取长度

.size()

获取当前 vector 的长度

时间复杂度：O(1)

1
2
for (int i = 0; i < arr.size(); i++)
    cout << a[i] << endl;

清空

.clear()

清空 vector

时间复杂度：O(n)

判空

.empty()

如果是空返回 true 反之返回 false.

时间复杂度：O(1)

改变长度

.resize(新长度, [默认值])

修改 vector 的长度

  • 如果是缩短，则删除多余的值
  • 如果是扩大，且指定了默认值，则新元素均为默认值（旧元素不变）

时间复杂度：O(n)

2.2.2 适用情形

一般情况 vector 可以替换掉普通数组，除非该题卡常。

有些情况普通数组没法解决：n×m 的矩阵，1≤n,m≤1061≤ 且 n×m≤106

  • 如果用普通数组 int mat[1000010][1000010]，浪费内存，会导致 MLE。
  • 如果使用 vector<vector<int>> mat(n + 10, vector<int> (m + 10))，完美解决该问题。

另外，vector 的数据储存在堆空间中，不会爆栈。

2.2.3 注意事项

提前指定长度

如果长度已经确定，那么应当直接在构造函数指定长度，而不是一个一个 .push_back(). 因为 vector 额外内存耗尽后的重分配是有时间开销的，直接指定长度就不会出现重分配了。

1
2
3
4
5
6
7
8
// 优化前: 522ms
vector<int> a;
for (int i = 0; i < 1e8; i++)
    a.push_back(i);
// 优化后: 259ms
vector<int> a(1e8);
for (int i = 0; i < a.size(); i++)
    a[i] = i;

当心 size_t 溢出

vector 获取长度的方法 .size() 返回值类型为 size_t，通常 OJ 平台使用的是 32 位编译器（有些平台例如 cf 可选 64 位），那么该类型范围为 [0,232)[0,232).

1
2
vector<int> a(65536);
long long a = a.size() * a.size(); // 直接溢出变成0了

2.3 栈 stack

#include <stack>

通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。

2.3.1 常用方法

作用 用法 示例
构造 stack<类型> stk stack<int> stk;
进栈 .push(元素) stk.push(1);
出栈 .pop() stk.pop();
取栈顶 .top() int a = stk.top();
查看大小 / 清空 / 判空 略 略

2.3.2 适用情形

如果不卡常的话，就可以直接用它而不需要手写栈了。

另外，vector 也可以当栈用，vector 的 .back() 取尾部元素，就相当于取栈顶，.push_back() 相当于进栈，.pop_back() 相当于出栈。

2.3.3 注意事项

不可访问内部元素！下面都是错误用法

1
2
3
4
for (int i = 0; i < stk.size(); i++)
    cout << stk[i] << endl;
for (auto ele : stk)
    cout << stk << endl;

2.4 队列 queue

#include <queue>

通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。

2.4.1 常用方法

作用 用法 示例
构造 queue<类型> que queue<int> que;
进队 .push(元素) que.push(1);
出队 .pop() que.pop();
取队首 .front() int a = que.front();
取队尾 .back() int a = que.back();
查看大小 / 清空 / 判空 略 略

2.4.2 适用情形

如果不卡常的话，就可以直接用它而不需要手写队列了。

2.4.3 注意事项

不可访问内部元素！下面都是错误用法

1
2
3
4
for (int i = 0; i < que.size(); i++)
    cout << que[i] << endl;
for (auto ele : que)
    cout << ele << endl;

2.5 优先队列 priority_queue

#include <queue>

提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。

2.5.1 常用方法

构造

priority_queue<类型, 容器, 比较器> pque

  • 类型：要储存的数据类型
  • 容器：储存数据的底层容器，默认为 vector<类型>，竞赛中保持默认即可
  • 比较器：比较大小使用的比较器，默认为 less<类型>，可自定义
1
2
priority_queue<int> pque1;                            // 储存int的大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 储存int的小顶堆

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。如果想要了解，可以查阅 cppreference 中的代码示例。

其他

作用 用法 示例
进堆 .push(元素) que.push(1);
出堆 .pop() que.pop();
取堆顶 .top() int a = que.top();
查看大小 / 判空 略 略

进出队复杂度 O(logn)，取堆顶 O(1).

2.5.2 适用情形

持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列里取出大小最小/最大的元素，元素数量 n，插入操作数量 k.

  • 每次插入后进行快速排序：k⋅nlogn
  • 使用优先队列维护：k⋅logn

2.5.3 注意事项

仅堆顶可读

只可访问堆顶，其他元素都无法读取到。下面是错误用法：

1
cout << pque[1] << endl;

所有元素不可写

堆中所有元素是不可修改的。下面是错误用法：

1
2
pque[1] = 2;
pque.top() = 1;

如果你恰好要修改的是堆顶元素，那么是可以完成的：

1
2
3
int tp = pque.top();
pque.pop();
pque.push(tp + 1);

2.6 集合 set

#include <set>

提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

集合三要素 解释 set multiset unordered_set
确定性 一个元素要么在集合中，要么不在 ✔ ✔ ✔
互异性 一个元素仅可以在集合中出现一次 ✔ ❌（任意次） ✔
无序性 集合中的元素是没有顺序的 ❌（从小到大） ❌（从小到大） ✔

2.6.1 常用方法

构造

set<类型, 比较器> st

  • 类型：要储存的数据类型
  • 比较器：比较大小使用的比较器，默认为 less<类型>，可自定义
1
2
set<int> st1;               // 储存int的集合（从小到大）
set<int, greater<int>> st2; // 储存int的集合（从大到小）

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。

遍历

可使用迭代器进行遍历：

1
2
for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;

基于范围的循环（C++ 11）：

1
2
for (auto &ele : st)
    cout << ele << endl;

其他

作用 用法 示例
插入元素 .insert(元素) st.insert(1);
删除元素 .erase(元素) st.erase(2);
查找元素 .find(元素) auto it = st.find(1);
判断元素是否存在 .count(元素) st.count(3);
查看大小 / 清空 / 判空 略 略

begin() 　　 返回set容器的第一个元素的 地址

end() 　　　　 返回set容器的最后一个元素 地址

clear() 　　 删除set容器中的所有的元素

empty() 　　　 判断set容器是否为空

max_size() 　 返回set容器可能包含的元素最大个数

size() 　　　　 返回当前set容器中的元素个数

erase(it) 删除迭代器指针it处元素

insert(a) 插入某个元素

增删查时间复杂度均为 O(logn)

2.6.2 适用情形

  • 元素去重：[1,1,3,2,4,4]→[1,2,3,4][1,1,3,2,4,4]→[1,2,3,4]
  • 维护顺序：[1,5,3,7,9]→[1,3,5,7,9][1,5,3,7,9]→[1,3,5,7,9]
  • 元素是否出现过：元素大小 [−1018,1018][−1018,1018]，元素数量 106106，vis 数组无法实现，通过 set 可以完成。

2.6.3 注意事项

不存在下标索引

set 虽说可遍历，但仅可使用迭代器进行遍历，它不存在下标这一概念，无法通过下标访问到数据。下面是错误用法：

1
cout << st[0] << endl;

元素只读

set 的迭代器取到的元素是只读的（因为是 const 迭代器），不可修改其值。如果要改，需要先 erase 再 insert. 下面是错误用法：

1
2
cout << *st.begin() << endl; // 正确。可读。
*st.begin() = 1;             // 错误！不可写！

不可用迭代器计算下标

set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：

1
2
auto it = st.find(2);      // 正确，返回2所在位置的迭代器。
int idx = it - st.begin(); // 错误！不可相减得到下标。

2.7 映射 map

#include <map>

提供对数时间的有序键值对结构。底层原理是红黑树。

映射：

1234→→→→⋮22151→22→23→14→5⋮

性质 解释 map multimap unordered_map
互异性 一个键仅可以在映射中出现一次 ✔ ❌（任意次） ✔
无序性 键是没有顺序的 ❌（从小到大） ❌（从小到大） ✔

2.7.1 常用方法

构造

map<键类型, 值类型, 比较器> mp

  • 键类型：要储存键的数据类型
  • 值类型：要储存值的数据类型
  • 比较器：键比较大小使用的比较器，默认为 less<类型>，可自定义
1
2
map<int, int> mp1;               // int->int 的映射（键从小到大）
map<int, int, greater<int>> st2; // int->int 的映射（键从大到小）

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。

遍历

可使用迭代器进行遍历：

1
2
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << ' ' << it->second << endl;

基于范围的循环（C++ 11）：

1
2
for (auto &pr : mp)
    cout << pr.first << ' ' << pr.second << endl;

结构化绑定 + 基于范围的循环（C++17）：

1
2
for (auto &[key, val] : mp)
    cout << key << ' ' << val << endl;

其他

作用 用法 示例
增 / 改 / 查元素 中括号 mp[1] = 2;
查元素（返回迭代器） .find(元素) auto it = mp.find(1);
删除元素 .erase(元素) mp.erase(2);
判断元素是否存在 .count(元素) mp.count(3);
查看大小 / 清空 / 判空 略 略

增删改查时间复杂度均为 O(logn)�(log⁡�)

2.7.2 适用情形

需要维护映射的场景可以使用：输入若干字符串，统计每种字符串的出现次数。(map<string, int> mp)

2.7.3 注意事项

中括号访问时默认值

如果使用中括号访问 map 时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性。

1
2
3
4
5
map<char, int> mp;
cout << mp.count('a') << endl; // 0
mp['a'];                       // 即使什么都没做，此时mp['a']=0已经插入了
cout << mp.count('a') << endl; // 1
cout << mp['a'] << endl;       // 0

不可用迭代器计算下标

map 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：

1
2
auto it = mp.find('a');      // 正确，返回2所在位置的迭代器。
int idx = it - mp.begin();   // 错误！不可相减得到下标。

2.8 字符串 string

#include <string>

顾名思义，就是储存字符串的。

2.8.1 常用方法

构造

构造函数：string(长度, 初值)

1
2
3
string s1;           // 构造字符串，为空
string s2 = "awa!";  // 构造字符串，并赋值awa!
string s3(10, '6');  // 构造字符串，通过构造函数构造为6666666666

输入输出

C++

1
2
3
string s;
cin >> s;
cout << s;

C

1
2
3
4
5
string s;
char buf[100];
scanf("%s", &buf);
s = buf;
printf("%s", s.c_str());

其他

作用 用法 示例
修改、查询指定下标字符 [] s[1] = 'a';
是否相同 == if (s1 == s2) ...
字符串连接 + string s = s1 + s2;
尾接字符串 += s += "awa";
取子串 .substr(起始下标, 子串长度) string sub = s.substr(2, 10);
查找字符串 .find(字符串, 起始下标) int pos = s.find("awa");

数值与字符串互转（C++11）

源 目的 函数
int / long long / float / double / long double string to_string()
string int stoi()
string long long stoll()
string float stof()
string double stod()
string long double stold()

2.8.2 适用情形

非常好用！建议直接把字符数组扔了，赶快投入 string 的怀抱。

2.8.3 注意事项

尾接字符串一定要用 +=

string 的 += 运算符，将会在原字符串原地尾接字符串。而 + 了再 = 赋值，会先生成一个临时变量，在复制给 string.

通常字符串长度可以很长，如果使用 + 字符串很容易就 TLE 了。

1
2
3
4
5
6
7
8
9
// 优化前: 15139ms
string s;
for (int i = 0; i < 5e5; i++)
    s = s + "a";

// 优化后: < 1ms (计时器显示0)
string s;
for (int i = 0; i < 5e5; i++)
    s += "a";

.substr() 方法的奇葩参数

一定要注意，C++ string 的取子串的第一个参数是子串起点下标，第二个参数是子串长度。

第二个参数不是子串终点！不是子串终点！要与 java 等其他语言区分开来。

.find() 方法的复杂度

该方法实现为暴力实现，时间复杂度为 O(n2)�(�2).

不要幻想 STL 内置了个 O(n)�(�) 的 KMP 算法

toupper是小写转大写函数

toupper大写

函数原型

1
2
3
4
5
6
int toupper(int c)  
{  
    if ((c >= 'a') && (c <= 'z'))  
        return c + ('A' - 'a');  
    return c;  
}

再普及一下大写转小写函数:

tolower小写

函数原型

1
2
3
4
5
6
int tolower(int c)  
{  
    if ((c >= 'A') && (c <= 'Z'))  
        return c + ('a' - 'A');  
    return c;  
}

它们有一个优点:只会修改英文字母

注意,这两个函数只能一次修改一个字符

kmp算法（重要）

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
void Getnext(int next[], string t) //求next数组
{
	int j = 0, k = -1;
	next[0] = -1;
	while (j < t.length() - 1)
	{
		if (k == -1 || t[j] == t[k])
		{
			j++;
			k++;
			next[j] = k;
		}
		else k = next[k];
	}
}
int KMP(string s, string t) //默认t为短串，传值时要注意！
{
	int next[10000], i = 0, j = 0;
	Getnext(next, t);
	while (i < s.length() && j < t.length())
	{
		if (j == -1 || s[i] == t[j])
		{
			i++;
			j++;
		}
		else j = next[j];               //j回退。。。
	}
	if (j >= t.length())
		return (i - t.length());         //匹配成功，返回子串的位置
	else
		return (-1);                  //没找到
}



2.9 二元组 pair

#include <utility>

顾名思义，就是储存二元组的。

2.9.1 常用方法

构造

pair<第一个值类型, 第二个值类型> pr

  • 第一个值类型：要储存的第一个值的数据类型
  • 第二个值类型：要储存的第二个值的数据类型
1
2
3
4
pair<int, int> p1;
pair<int, long long> p2;
pair<char, int> p3;
// ...

赋值

老式

1
pair<int, char> pr = make_pair(1, 'a');

列表构造 C++11

1
pair<int, char> pr = {1, 'a'};

取值

直接取值

  • 取第一个值：.first
  • 取第二个值：.second
1
2
3
pair<int, char> pr = {1, 'a'};
int awa = pr.first;
char bwb = pr.second;

结构化绑定 C++17

1
2
pair<int, char> pr = {1, 'a'};
auto &[awa, bwb] = pr;

判同

直接用 == 运算符

1
2
3
pair<int, int> p1 = {1, 2};
pair<int, int> p2 = {1, 3};
if (p1 == p2) { ... } // false

2.9.2 适用场景

所有需要二元组的场景均可使用，效率和自己定义结构体差不多。

2.9.3 注意事项

无

3 迭代器简介

3.1 迭代器是什么？

不搞抽象，直接举例。

对于一个 vector，我们可以用下标遍历：

1
2
for (int i = 0; i < a.size(); i++)
    cout << a[i] << endl;

我们同时也可以用迭代器来遍历：

1
2
for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;
  • a.begin() 是一个迭代器，指向的是第一个元素
  • a.end() 是一个迭代器，指向的是最后一个元素再后面一位
  • 上述迭代器具有自增运算符，自增则迭代器向下一个元素移动
  • 迭代器与指针相似，如果对它使用解引用运算符，即 *it，就能取到对应值了

3.2 为何需要迭代器？

很多数据结构并不是线性的（例如红黑树），对于非线性数据结构，下标是无意义的。无法使用下标来遍历整个数据结构。

迭代器的作用就是定义某个数据结构的遍历方式，通过迭代器的增减，代表遍历到的位置，通过迭代器便能成功遍历非线性结构了。

例如，set 的实现是红黑树，我们是没法用下标来访问元素的。但是通过迭代器，我们就能遍历 set 中的元素了：

1
2
for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;

3.3 迭代器用法

对于 vector 容器，它的迭代器功能比较完整，以它举例：

  • .begin()：头迭代器
  • .end()：尾迭代器
  • .rbegin()：反向头迭代器
  • .rend()：反向尾迭代器
  • 迭代器 + 整型：将迭代器向后移动
  • 迭代器 - 整型：将迭代器向前移动
  • 迭代器 ++：将迭代器向后移动 1 位
  • 迭代器 --：将迭代器向前移动 1 位
  • 迭代器 - 迭代器：两个迭代器的距离
  • prev(it)：返回 it 的前一个迭代器
  • next(it)：返回 it 的后一个迭代器

对于其他容器，由于其结构特性，上面的功能不一定都有（例如 set 的迭代器是不能相减求距离的）

3.4 常见问题

.end() 和 .rend() 指向的位置是无意义的值

对于一个长度为 10 的数组：for (int i = 0; i < 10; i++)，第 10 位是不可访问的

对于一个长度为 10 的容器：for (auto it = a.begin(); it != a.end(); ++it)，.end 是不可访问的

不同容器的迭代器功能可能不一样

迭代器细化的话有正向、反向、双向，每个容器的迭代器支持的运算符也可能不同，因此不同容器的迭代器细节很有可能是不一样的。

删除操作时需要警惕

为什么 3 没删掉？

1
2
3
4
5
vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ++it)
    if (*it == 2 || *it == 3)
        a.erase(it);
// a = [1, 3, 4]

为啥 RE 了？

1
2
3
4
vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ++it)
    if (*it == 4)
        a.erase(it);

建议：如无必要，别用迭代器操作容器。（遍历与访问没关系）

4 常用算法

4.1 内容总览

打勾的是本次将会详细讲解的，其他的是算法竞赛中建议学习的，不在下表列出的在比赛中基本用不到。

（很多函数的功能很简单，自己都能快速写出来，但是使用函数可以让代码可读性变得更高，这在比赛中是至关紧要的）

  • 算法库 Algorithm
  • 数学函数 cmath
    • [x] abs()
    • [x] exp()
    • [x] log() / log10() / log2()
    • [x] pow()
    • [x] sqrt()
    • [ ] sin() / cos() / tan()
    • [ ] asin() / acos() / atan()
    • [ ] sinh() / cosh() / tanh()
    • [ ] asinh() / acosh() / atanh() C++11
    • [x] ceil() / floor()
    • [x] round() C++11
  • 数值算法 numeric
    • [ ] iota() C++11
    • [ ] accumulate()
    • [x] gcd() C++17
    • [x] lcm() C++17
  • 伪随机数生成 random
    • [ ] mt19937
    • [ ] random_device()

4.2 swap()

交换两个变量的值（也可交换结构体等）

用法示例

1
2
3
4
5
6
7
8
9
template< class T >
void swap( T& a, T& b );
int a = 0, b = 1;
swap(a, b);
// now a = 1, b = 0

int arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
swap(arr[4], arr[6]);
// now arr = {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}

注意事项

这个 swap 参数是引用的，不需要像 C 语言一样取地址。

4.3 sort()

使用快速排序给一个可迭代对象排序

用法示例

1
2
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

默认排序从小到大

1
2
3
vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end());
// arr = [0, 1, 1, 1, 8, 9, 9]

如果要从大到小，则需要传比较器进去。

1
2
3
vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end(), greater<int>());
// arr = [9, 9, 8, 1, 1, 1, 0]

如果需要完成特殊比较，则需要手写比较器。

比较器函数返回值是 bool 类型，传参是需要比较的两个元素。记我们定义的该比较操作为 ⋆⋆：

  • 若 a⋆b，则比较器函数应当返回 true
  • 若 a⋆̸b，则比较器函数应当返回 false

注意：如果 a=b=�，比较器函数必须返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first > b.first;
}

int main()
{
    vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};
    sort(arr.begin(), arr.end(), cmp);
    // arr = [(0, 0), (8, 1), (2, 9), (1, 9)]
}

4.4 lower_bound() / upper_bound()

在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置。找不到则返回尾迭代器。

  • lower_bound(): 寻找 ≥x的第一个元素的位置
  • upper_bound(): 寻找 >x的第一个元素的位置

怎么找 ≤x/ <x第一个元素呢？

  • >x 的第一个元素的前一个元素（如果有）便是 ≤x 的第一个元素
  • ≥x 的第一个元素的前一个元素（如果有）便是 <x 的第一个元素

返回的是迭代器，如何转成下标索引呢？减去头迭代器即可。

记得考虑全部都比要找的大或者小的特殊情况！！！

用法示例

1
2
3
4
5
6
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
vector<int> arr{0, 1, 1, 1, 8, 9, 9};
vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7);
int idx = it - arr.begin();
// idx = 4

我们通常写成一行：

1
2
3
4
5
vector<int> arr{0, 1, 1, 1, 8, 9, 9};
idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
idx = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4
idx = upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
idx = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5

4.5 reverse()

反转一个可迭代对象的元素顺序

用法示例

1
2
3
4
5
6
7
template< class BidirIt >
void reverse( BidirIt first, BidirIt last );
vector<int> arr(10);
iota(arr.begin(), arr.end(), 1);
// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverse(arr.begin(), arr.end());
// 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

4.6 max() / min()

返回最大值 / 最小值的数值

用法示例

1
2
int mx = max(1, 2); // 2
int mn = min(1, 2); // 1

在 C++11 之后，可以使用列表构造语法传入一个列表，这样就能一次性给多个元素找最大值而不用套娃了：

1
2
3
4
5
6
7
// Before C++11
int mx = max(max(1, 2), max(3, 4)); // 4
int mn = min(min(1, 2), min(3, 4)); // 1

// After C++11
int mx = max({1, 2, 3, 4}); // 4
int mn = min({1, 2, 3, 4}); // 1

4.7 unique()

消除数组的重复相邻元素，数组长度不变，但是有效数据缩短，返回的是有效数据位置的结尾迭代器。

例如：[1,1,4,5,1,4]→[1,4,5,1,4,?–][1,1,4,5,1,4]→[1,4,5,1,4,?_]，下划线位置为返回的迭代器指向。

1
2
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );

用法示例

单独使用 unique 并不能达成去重效果，因为它只消除相邻的重复元素。但是如果序列有序，那么它就能去重了。

但是它去重后，序列尾部会产生一些无效数据：[1,1,2,4,4,4,5]→[1,2,4,5,?–,?,?][1,1,2,4,4,4,5]→[1,2,4,5,?_,?,?]，为了删掉这些无效数据，我们需要结合 erase.

最终，给 vector 去重的写法便是：

1
2
3
vector<int> arr{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());

4.8 数学函数

所有函数参数均支持 int / long long / float / double / long double

公式 示例
f(x)=\ x\ abs(-1.0)
f(x)=ex exp(2)
f(x)=lnx log(3)
f(x,y)=xy pow(2, 3)
f(x)=x−−√�(�)=� sqrt(2)
f(x)=⌈x⌉ ceil(2.1)
f(x)=⌊x⌋ floor(2.1)
f(x)=⟨x⟩ rount(2.1)

注意事项

由于浮点误差，有些的数学函数的行为可能与预期不符，导致 WA。如果你的操作数都是整型，那么用下面的写法会更稳妥。

原文地址：https://codeforces.com/blog/entry/107717

  • ⌊ab⌋
    • 别用：floor(1.0 * a / b)
    • 要用：a / b
  • ⌈ab⌉
    • 别用：ceil(1.0 * a / b)
    • 要用：(a + b - 1) / b （⌈ab⌉=⌊a+b−1b⌋）
  • ⌊a−−√⌋⌊�⌋
  • ab
  • ⌊log2a⌋
    • 别用：log2(a)
    • 要用：__lg （不规范，但是这是竞赛）/ bit_width（C++20 可用）

4.9 gcd() / lcm()

（C++17）返回最大公因数 / 最小公倍数

1
2
int x = gcd(8, 12); // 4
int y = lcm(8, 12); // 24

如果不是 C++17，但是是 GNU 编译器（g++），那么可以用内置函数 __gcd().

当然，gcd / lcm 函数也挺好写，直接写也行（欧几里得算法）：

1
2
3
4
5
6
7
8
9
10
11
int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

4.10 nth_element

在 STL 里有一个神奇的函数 nth_element。

它的用法是 nth_element(a+x,a+x+y,a+x+len);。

执行之后数组 a 下标 x 到 x+y−1 的元素都小于 a[x+y]，下标 x+y+1 到 x+len−1 的元素 都大于 a[x+y]，但不保证数组有序。此时 a[x+y] 就是数组区间 x 到 x+len−1 中第 y 小的数，当然也可以自己定义 cmp 函数。

结论：差不多就是将我们的思路 2 做了一遍。

nth_element 的时间复杂度是 )O(n) 的，不过 STL 常数普遍较大……但还是能过此题。

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
	int n;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&x[i]);
	nth_element(x,x+k,x+n);//简短又高效
	printf("%d",x[k]);
}

4.11 next_permutation

一、next_permutation的介绍

next_permutation的意思是下一个排列，与其相对的是prev_permutation,即上一个排列。我们需要使用全排列的时候就可以直接使用这两个函数，方便又快捷

二、next_permutation的基本用法

由于prev_permutation和next_permutation的用法是一样的，下面就值讲解next_permutation的基本用法

next_permutation只能获得上一个排列，如果要获得全排列，那么就需要先对数组进行升序排序

基本定义如下：
next_permutaion(起始地址，末尾地址+1)
next_permutaion(起始地址，末尾地址+1，自定义排序)

可以使用默认的升序排序，也可以使用自定义的排序方法

1、普通数组全排列

普通数组可以通过数组名表示地址，非常容易实现

示例代码：

include

include//使用 next_permutation()和sort()需要导入的头文件

using namespace std;
int main(){
int a[4]={2,1,4,3};

sort(a,a+4);//对数组排序 

do{
    for(int i=0;i<4;i++){//打印排列 
        cout<<a[i]<<' ';
    }
    cout<<endl;
}while(next_permutation(a,a+4));//获取下一个排列

}

运行结果：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

2、结构体全排列

结构体默认是不能比较大小的，那么就不能使用默认的next_permutation()排列比较函数，需要使用自定义排列比较函数

示例代码：

include

include//使用 next_permutation()和sort()需要导入的头文件

using namespace std;

struct test{//结构体test
int val;
};

bool cmp(test t1,test t2){//自定义的排列
return t1.val<t2.val;
}

int main(){
test t[4];//结构体数组
t[0].val=1;
t[1].val=2;
t[2].val=3;
t[3].val=4;

do{
    for(int i=0;i<4;i++){//打印排列 
        cout<<t[i].val<<' ';
    }
    cout<<endl;
}while(next_permutation(t,t+4,cmp));//获取下一个排列

运行结果：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

3、vector

vector及string等数据结构不能直接用名字代表地址，只能够使用自带的迭代器begin()、end()实现全排列

示例代码：

include

include //使用vector需要导入的头文件

include//使用 next_permutation()和sort()需要导入的头文件

using namespace std;

int main(){
vector v;//定义一个int型的vector
v.push_back(1);//在尾部插入数据1
v.push_back(2);
v.push_back(3);
v.push_back(4);

do{
    for(int i=0;i<v.size();i++){//打印排列 
        cout<<v[i]<<' ';
    }
    cout<<endl;
}while(next_permutation(v.begin(),v.end()));//获取下一个排列

}

运行结果：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

同样地，prev_permutation拥有同样的用法，大家可以动手尝试一下

学完next_permutation的这些基本用法就足够使用了，进阶的可以搭配其它的数据结构进行使用
https://blog.csdn.net/weixin_52115456/article/details/127626074

复杂度

一、时间复杂度

我们想要知道一个算法的「时间复杂度」，很多人首先想到的的方法就是把这个算法程序运行一遍，那么它所消耗的时间就自然而然知道了。

这种方式可以吗？当然可以，不过它也有很多弊端。
这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。再者，并我们在写算法的时候，还没有办法完整的去运行呢。

因此，另一种更为通用的方法就出来了：「 大O符号表示法 」，即 T(n) = O(f(n))

我们先来看个例子：

1
2
3
4
5
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

通过「 大O符号表示法 」，这段代码的时间复杂度为：O(n) ，为什么呢?

在 大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

我们继续看上面的例子，假设每行代码的执行时间都是一样的，我们用 1颗粒时间 来表示，那么这个例子的第一行耗时是1个颗粒时间，第三行的执行时间是 n个颗粒时间，第四行的执行时间也是 n个颗粒时间（第二行和第五行是符号，暂时忽略），那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ，即 (1+2n)个颗粒时间，即： T(n) = (1+2n)*颗粒时间，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)

为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

所以上面的例子中，如果n无限大的时候，T(n) = time(1+2n)中的常量1就没有意义了，倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。

常见的时间复杂度量级有：

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)
  • 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

下面选取一些较为常用的来讲解一下（没有严格按照顺序）：

  1. 常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

  1. 线性阶O(n)

这个在最开始的代码示例中就讲解过了，如：

1
2
3
4
5
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

  1. 对数阶O(logN)

还是先来看代码：

1
2
3
4
5
int i = 1;
while(i<n)
{
    i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

  1. 线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

1
2
3
4
5
6
7
8
for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}
  1. 平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
举例：

1
2
3
4
5
6
7
8
for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)
如果将其中一层循环的n改成m，即：

1
2
3
4
5
6
7
8
for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的时间复杂度就变成了 O(m*n)

  1. 立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

  1. 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
举例：

1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

  1. 空间复杂度 O(n)

我们先看一个代码：

1
2
3
4
5
6
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

异或

一、概念概念来自百度百科。链接如下：异或异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。二、运算过程通过三个例子和划重点：异或的运算口诀是相等为0，不相等为1。当然这是在二进制的层面。下面手动演示一遍以 12 和 12 为例进行异或演示十进制的12 在二进制是1100，根据口诀 相等为0，不相等为1

　异或运算：按位异或运算符

　　首先异或表示当两个数的二进制表示，进行异或运算时，当前位的两个二进制表示不同则为1相同则为0.该方法被广泛推广用来统计一个数的1的位数！

　　参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。

　　即：

　　0^0 = 0，

　　1^0 = 1，

　　0^1 = 1，

　　1^1 = 0

　　按位异或的3个特点：

　　（1） 0^0=0，0^1=1 0异或任何数＝任何数

　　（2） 1^0=1，1^1=0 1异或任何数－任何数取反

　　（3） 任何数异或自己＝把自己置0

　　按位异或的几个常见用途：

　　（1） 使某些特定的位翻转

　　例如对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算。

　　10100001^00000110 = 10100111

　　（2） 实现两个值的交换，而不必使用临时变量。

　　例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：

　　a = a^b； 　　//a=10100111

　　b = b^a； 　　//b=10100001

　　a = a^b； 　　//a=00000110

　　位运算

　　位运算时把数字用二进制表示之后，对每一位上0或者1的运算。理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1.比如十进制的2转化为二进制之后就是10。

　　其实二进制的运算并不是很难掌握，因为位运算总共只有5种运算：与、或、异或、左移、右移。如下表：

　　img

　　左移运算：

　　左移运算符m《《n表示吧m左移n位。左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0.比如：

　　img

　　右移运算：

　　右移运算符m》》n表示把m右移n位。右移n位的时候，最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。这里要特别注意，如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后再最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1.下面是堆两个8位有符号数作右移的例子：

　　img

　　关于移位的运算有这样的等价关系：把整数右移一位和把整数除以2在数学上是等价的。

　　img

　　计算机内部只识别1、0，十进制需变成二进制才能使用移位运算符《《，》》 。

　　int j = 8;

　　p = j 《《 1;

　　cout《《p《《endl;

　　在这里，8左移一位就是8*2的结果16 。

　　移位运算是最有效的计算乘/除乘法的运算之一。

　　按位与（&）其功能是参与运算的两数各对应的二进制位相与。只有对应的两个二进制位均为1时，结果位才为1，否则为0 。参与运算的数以补码方式出现。

　　先举一个例子如下：

　　题目：请实现一个函数，输入一个正数，输出该数二进制表示中1的个数。

　　img

　　这里用到了这样一个知识点：把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0 。 那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

　　总结：把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0 。

　　位运算的应用可以运用于很多场合：

　　清零特定位（mask中特定位置0，其它位为1 ， s = s & mask）。

　　取某数中指定位（mask中特定位置，其它位为0， s = s & mask）。

　　举例：输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。

　　解决方法：第一步，求这两个数的异或；第二步，统计异或结果中1的位数。

　　img

　　接下来我们再举一例，就可以更好的说明移位运算了：用一条语句判断一个整数是不是2的整数次方。

　　解决方法：一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其它所有位都是0 。 根据前面的分析，把这个整数减去1后再和它自己做与运算，这个整数中唯一的1就变成0了。

　　解答：！（x & （x - 1））

例题

【题目】

给一个数组arr，其中只有一个数出现了奇数次，其它数出现了偶数次，打印这个数。

【输入】

输出包含两行，第一行包含一个整数n（1 \leq n \leq 10^5）（1≤n≤105），代表数组arr长度，第二行有n个数，代表数组arrarr_i 为32位整数arri为32位整数。输出包含两行，第一行包含一个整数n（1 \leq n \leq 10^5）（1≤n≤105），代表数组arr长度，第二行有n个数，代表数组arrarr_i 为32位整数arri为32位整数。

【输出】

输出一个整数，代表出现次数为奇数次的那个数。

【示例】

输入：5

​ 3 1 3 1 2

输出：2

【复杂度】

1
时间复杂度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
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
import java.util.*;



public class Main {



    public static void main(String[] args){



        Scanner sc = new Scanner(System.in);



        int count = sc.nextInt();



        int res = 0;



        //每次将输入的值进行异或运算



        for(int i=0;i<count;i++){



            int tmp = sc.nextInt();



            res ^= tmp;



        }



        System.out.println(res);



    }



}

进阶：数组中存在两个出现奇数次的数

【题目】

给定一个数字arr，其中只有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。

【输入】

1
第一行输入一个n，第二行输入n个数

【输出】

1
输出出现奇数次的两个数，按照从小到大的顺序。

【示例】

输入 4

​ 1 1 2 3
输出
​ 2 3

【分析】

  1. 先把数组中所有数全部异或运算，得到的结果为两个所求数ab的异或值

  2. 由于ab异或的值不为0（因为如果为0，那么意味着ab相等），所以ab的二进制位中必然存在一个不相等的位，对ab两个数进行异或运算时，这个位上的运算结果为1，所以要先找到ab异或结果中为1的位置（找到一位即可），那么我们找最右侧的1

    寻找的方法是：把ab异或后的结果eor取反后加1，然后与eor进行并运算（rightOne的结果如：（00000100）

    1
    int rightOne = eor & (~eor +1);

  3. 筛选出所有在该位置上不为1的数进行异或运算（这样做的目的是把a和b分开，进行异或运算得到其中一个数）

    1
    2
    if((cur & rightOne) == 0)             //筛选出所有在该位置上不为1的数进行异或
    if((cur & rightOne) == rightOne)      //筛选出所有在该位置上为1的数进行异或

  4. 这样，有了a和b的异或值，有了a或b的值，那么将eor和neweor异或就能得到另一个值

【代码】

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
119
120
121
122
123
124
125
import java.util.*;



public class Main {



    public static void main(String[] args){



        Scanner sc = new Scanner(System.in);



        int count = sc.nextInt();



        int[] arr = new int[count];



        int total = 0;



        //求出总体的异或和



        for(int i=0; i<count; i++){



            arr[i] = sc.nextInt();



            total ^= arr[i];



        }



        //取出异或和的最右侧的‘1’位



        total = total & (~total + 1);



        int even = 0;



        int odd = 0;



        for(int i=0; i<count; i++){



            //‘1’位上为0的数进行异或和



            if((arr[i]&total) == 0){



                even ^= arr[i];



            }



            //‘1’位上位1的数异或求和



            else{



                odd ^= arr[i];



            }



        }



        int[] res = new int[2];



        res[0] = even<odd?even:odd;



        res[1] = even+odd-res[0];



        System.out.println(res[0]+" "+res[1]);



    } 



}

day 10.15

求两点之间的距离（两点距离平方再开方）

img

1
2

sqrt(abs((x1 - x2) * (x1 - x2)) + abs((y1 - y2) * (y1 - y2)));

day10.16

求素数方法

1.开根

1
2
3
4
5
6
7
bool isprime(int x){//判断是否素数
	if(x<=1) return false;//如果小于2，一定不是素数
	for(int i=2;i<=sqrt(x);i++){//为什么要到sqrt(x)呢，因为如果有一个大于sqrt(n)的数可以被n整除，那么必有一个数n/i也可以被n整除且小于i
		if(x%i==0) return false;//如果可以整除，那么不是素数
	}
	return true;//是素数
}

2.开根优化

有一个优化的代码，速度是上面的3倍，可以看一看

1
2
3
4
5
6
7
bool isprime(int n){
    if(n<=1) return false;
    if(n==2||n==3) return true;
    if(n%6!=1&&n%6!=5) return false;
    for(int i=5;i*i<=n;i+=6) if(n%i==0||n%(i+2)==0) return false;
    return true;
}

除2,3外，其他所有素数都必须是6n+1或6n+5，因为6n+2=2(3n+1) 6n+2=2(3n+1)，6n+3=3(2n+1) 6n+4=2(3n+2)，都有非1和本身因数，不是素数

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
long long n,m;
bool vis[10000001]={1,1};//0，1均既不是素数，也不是和数，所以先标记为不是
int Prime[10000001],k;
void prime(long long n)
{
    for(int i=2;i<=n;i++)//最小的素数是2
    {
        if(!vis[i])
        {
            Prime[++k]=i;//如果是素数就标记一下
         }
        for(int j=1;j<=k;j++)//j小于当前所有的素数的个数
        {
            if(Prime[j]*i>n)
            {
                break;
            }
            vis[Prime[j]*i]=true;//用素数依次×i，结果标记为合数
            if(i%Prime[j]==0)
            {
                break;
            }
        }
    }//欧拉筛法，就是拿当前的数×之前的筛出来的素数，这个数即为合数
}
int main()
{
    cin>>n;
    prime(100001);//在10的5次方范围内筛素数
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(!vis[t])//上面标记过了，这时输入后直接判断就行了
        {
            cout<<t<<" ";
        }
    }
    return 0;
}

4.最后：埃氏筛法（比欧拉筛法更容易理解）

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;
bool vis[100001]={1,1};//0,1标为不是
int n;
void Era(int qwq)
{
    for(int i=2;i<=qwq;i++)
    {
        if(vis[i])
        {
            continue;
        }//是合数就不执行
        for(int j=i*2;j<=qwq;j+=i)//从i×2开始筛，因为进过判断后i为素数
        {
            vis[j]=true;//j=i的倍数，每次加i，即为i的倍数每次加1，p数组的第j个元素标为合数
        }
    }
}
int main()
{
    cin>>n;
    int tmp;
    Era(100001);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&tmp);
        if(!vis[tmp])//已经记下了，判断一下即可
        {
            cout<<tmp<<" ";
        }//真就不是，假就是
    }
    return 0;
}

分治/杨辉三角/递归

题目描述

现有 $2^n\times 2^n (n\le10)$ 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 $n$，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

输入格式

一个整数 $n$。

输出格式

$2^n \times 2^n$ 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。

样例输入

1
3

样例输出

1
2
3
4
5
6
7
8
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

本题基本思路是分治，代码可以通过递归来实现，每次递归将左上方的正方形清零，并再次递归剩余的三个正方形，当正方形的边长为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
#include<bits/stdc++.h>
using namespace std;
int n,p=1,a[1050][1050];
void di(int x,int l,int q) //x为正方形边长，l、q分别为递归正方形的横纵坐标
{
	if(x==2) //递归边界
	{
		a[l][q]=0;
		return;
	}
	for(int i=l; i<=l+x/2-1; i++)
		for(int j=q; j<=q+x/2-1; j++)
			a[i][j]=0; //将左上方的正方形清零
	di(x/2,l+x/2,q);
	di(x/2,l+x/2,q+x/2); 
	di(x/2,l,q+x/2); //此处是递归剩余的三个正方形
}
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++)
		p*=2; //计算正方形的边长
	for(int i=1; i<=p; i++)
		for(int j=1; j<=p; j++)
			a[i][j]=1; //将a数组先赋值为1
	di(p,1,1); //开始递归
	for(int i=1; i<=p; i++)
	{
		for(int j=1; j<=p-1; j++)
			cout<<a[i][j]<<" ";
		cout<<a[i][p]<<endl; //输出，此处可以避免输出行尾空格
	}
	return 0;
}

集合求和

题目描述

给定一个集合 $s$（集合元素数量 $\le 30$），求出此集合所有子集元素之和。

输入格式

集合中的元素（元素 $\le 1000$）

输出格式

$s$ 所有子集元素之和。

样例输入 #1

1
2 3

样例输出 #1

1
10

提示

【样例解释】

子集为：$\varnothing, { 2 }, { 3 }, { 2, 3 }$，和为 $2 + 3 + 2 + 3 = 10$。

【数据范围】

对于 $100 \%$ 的数据，$1 \le \lvert s \rvert \le 30$，$1 \le s_i \le 1000$，$s$ 所有子集元素之和 $\le {10}^{18}$。

题解 P2415 【集合求和】 - feecle6418 的博客 - 洛谷博客 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<cmath>
using namespace std;
int a[31],i=0,j;
long long s=0;
int main(){
    //cout<<s;
    while(cin>>a[i++]);//合写cin>>a[i];i++;
    for(j=0;j<i;j++){
        s+=a[j];
    }
    s*=pow(2,i-2);//注意，i-2!
    cout<<s;
    return 0;
}

day 10/17

当需要循环的时候，试试加上总长度之后取余运算！（比如队列绕圈等）

例题：P1563 [NOIP2016 提高组] 玩具谜题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

day 10/18

高精度

此题解只面对与刚刚学算法的童鞋们

  • 什么情况下要使用高精度？

当两个数超过longlong的大小并且要对这两个大数进行运算的时候。

  • 既然数这么大，我们用什么存放呢？

用字符串存放。

  • 怎么运算呢？

小学学加法的时候，我们是从最低位开始计算，两两相加，逢十进一。

我们也可以用计算机模拟这一过程。

具体代码：

1
2
3
4
5
6
7
for(j=1; j<=max(a[0],b[0])+1; j++) {
	c[j]=a[j]+b[j];
	if(c[j]>=10) {
		c[j]%=10;
		a[j+1]++;
	}
}
  • 既然要进行运算，我们总得知道字符串的长度吧？怎么获取呢？

用strlen函数。

1
2
a[0]=strlen(s);
b[0]=strlen(ss);
  • 要运算，怎么知道某一位的具体数值是几呢？

这个跟ascll码有关了。

img

一个字符数字的ascll码－48（也就是0的ascll码）就是那个数字的ascll码。

转化过程：

1
2
for(int i=1; i<=a[0]; i++) a[i]=s[a[0]-i]-'0';//倒序存入数组，从低到高位
for(int i=1; i<=b[0]; i++) b[i]=ss[b[0]-i]-'0';

☆ 注意：

一定要考虑进位！！

具体的说，就是最高位相加时可能会有进位，需特判。

如果dalao们看前面的不顺眼觉得蔡那看看这个：

读入第一行字符串A与第二行字符串B，

将两串字符串的每个字符转成数字存储在数组中，字符转数字的方式是：ch-’0’

我们将个位存在a[1]，高位存在a[l]，l是数字位数，也即字符串长度。

字符串B也用一个数组b来记录。

高精度加法就是模拟加法的过程，我们要做的就是让a和b的每一位相加，并判断任意一位数是否大于等于1010，即应进位的问题。

处理完进位同时也要考虑最终和的位数（长度）是否有变化。 最终逐位输出达成输出大数的效果。

说了这么多，上一下AC代码：

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[1000001],b[1000001],c[1000001],j;
bool x=false;
char s[1000001],ss[1000001];//或string s,ss;
int main() {

	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));//初始化
	scanf("%s%s",s,ss);//读入两个数
	a[0]=strlen(s);
	b[0]=strlen(ss);//获取长度
	for(int i=1; i<=a[0]; i++) a[i]=s[a[0]-i]-'0';
	for(int i=1; i<=b[0]; i++) b[i]=ss[b[0]-i]-'0';//转化为数字
	for(j=1; j<=max(a[0],b[0])+1; j++) {
		c[j]=a[j]+b[j];
		if(c[j]>=10) {
			c[j]%=10;
			a[j+1]++;//或者让c[j+1]++，然后上面换成c[j]+=a[j]+b[j];
		}
	}//模拟加法
	c[0]=j;
	if(c[j+1]>0) c[0]++;//特判进位
	for(int i=c[0]; i>=1; i--) {//输出（删除前导零）
		if(x==false&&c[i]==0) continue;
		x=true;
		cout<<c[i];
	}
	if(x==false) cout<<0;//一重保险
	printf("\n");//二重保险
	return 0;//三重保险
}

在以后的学习中，高精度会成为一个很重（ke）要（pa）的算法，Ta会成为一种工具。

day 10/21

P1067 [NOIP2009 普及组] 多项式输出 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main(){
    int n,a;
    cin>>n;
    for(int i=n;i>=0;i--){
        cin>>a;
        if(a){    判0系数
            if(i!=n&&a>0)cout<<"+";    根据正负、是否为最高此项决定加号
            if(abs(a)>1||i==0)cout<<a;    输出系数（系数不为正负1或指数为0）
            if(a==-1&&i)cout<<"-";    -1系数特判，常数项已特判
            if(i>1)cout<<"x^"<<i;    二次及以上输出指数
            if(i==1)cout<<"x";    一次项
        }
    }
}

day 10/22

题目最后要求输出时，不一定都要最后一块输出，可以输入一组数据马上输出其对应的结果！！!

sort与函数结合

1
2
3
4
5
6
7
8
9
bool cmp(arr a1,arr a2){
    if (a1.chinese + a1.english + a1.math != a2.chinese + a2.english + a2.math)
    {
        return a1.chinese + a1.english + a1.math > a2.chinese + a2.english +a2.math;
    }如果a1总分比a2总分高，则排在前面
    if (a1.chinese != a2.chinese) { return a1.chinese > a2.chinese; }如果a1比a2语文成绩高，则排在前面
  
    return a1.id < a2.id;如果a1序号比a2序号小，则排在前面
}

堆（重要！！！）

什么是堆

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

堆的定义

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

堆的分类

分大根堆和小根堆

例如：

1
2
3
4
5
1
                    / \
                   2   8
                  /\   /\
                 3  7 8  9

这是一个小根堆。小根堆的定义是：任何一个子节点都不小于它的父节点。因此，堆的根节点总是最小。

又例如：

1
2
3
4
5
9
                    / \
                   6   8
                  /\   /\
                 3  2 1  4

这是一个大根堆。大根堆的定义是：任何一个子节点都不大于它的父节点。因此，堆的根节点总是最大。

堆的存储与遍历。

堆用数组存储。

拿上面的小根堆举例

1
2
3
4
5
1
                    / \
                   2   8
                  /\   /\
                 3  7 8  9

用数组存储就是：

1 2 3 4 5 6 7
1 2 8 3 7 8 9

显然，堆的存储是按照每一层的顺序存进数组里的。

那么，怎么找到一个堆的父亲与儿子？

拿第二个点2举例。

如图，第二个点2的父亲是第一个点1，第二个点2的儿子为第四个点3与第五个点7。

得出结论：一个点的父亲为这个点的数组下表整除2;一个点的儿子为这个点的数组下标乘2或乘2加1.

很好理解吧。

堆的操作。

重点是如何维护一个堆。

在运行代码的时候，经常会从堆里面插入元素或取出元素。

因此堆的秩序经常会被打乱。

维护堆需要掌握两个操作：将一个点上浮或下沉。

这里拿小根堆举例，大根堆也是一样的。

下沉操作：

这里我将点一更改成9

1
2
3
4
5
9
                    / \
                   2   8
                  /\   /\
                 3  7 8  9
1 2 3 4 5 6 7
9 2 8 3 7 8 9

它已经不是一个正常的堆了，至少不是一个正常的小根堆。

这时候我们就要将它下沉。

下沉关键代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void down(int x)//x为需要下沉的点的下标
{
    while((a[x]>=a[x*2]&&x*2<=n)||(a[x]>=a[2*x+1]&&x*2+1<=n))//只要找到有一个点小于它，那么就下沉，直无法下沉为止。。
    {
        if(a[x*2]<=a[x*2+1])//两个子节点，往更小的地方下沉。
        {
            swap(a[x],a[x*2]);
            x*=2;//需要改变下标。
        }
        else
        {
            swap(a[x],a[x*2+1]);
            x=2*x+1;
        }
    }
}

下沉之后它就成了这样：

1
2
3
4
5
2
                    / \
                   3   8
                  /\   /\
                 9  7 8  9
1 2 3 4 5 6 7
2 3 8 9 7 8 9

符合堆的性质。

上浮操作：

比下沉简单多了，不作太多讲解。

拿小根堆举例，当一个节点的父节点比它大，那么它就上浮until它呆在它应有的位置为止。

上浮代码：

1
2
3
4
5
6
7
8
void up(int x)
{
    while(a[x]<a[x/2]&&x>1)//注意这个x>1。如果没了它可能会使x变成0。
    {
        swap(a[x],a[x/2]);
        x/=2;
    }
}

插入操作

往堆里面插入一个元素，可能会使堆不正常。

那么这样做，（不分大小根堆）：

1.最大下标加1，一个元素插入堆底（数组后）。

2.对它实行上升操作。

上代码可能会好理解一点。

1
2
3
4
5
void work(int x)
{
    a[++n]=x;
    up(n);
}

建堆操作

好吧重点来了。

这里讲的建堆，就是给你很多数字，把它存进数组里使其变成一个堆。

注意，排序一遍之后再建堆也是可以的，但是你既然排序过了还用什么堆排呢？

很简单。

1.最大标加1，插入队尾。

2.上升。

3.回到1.，直到没有数据再次插入。

删除堆顶元素

很多人不知道为什么要删除。

其实当这个堆是一个正常的堆时，它的根节点总是最大或最小的。

堆排序只要求你把它输出出来，然后将根的值赋为堆底元素（即当前最大下标所指的数组，记得最大下标要减一），最后对堆顶（因为执行上一操作会打破堆的正常秩序）执行下沉操作。

给出代码：

1
2
3
a[1] =a[n];
   n--;
   down(1);

其中a数组是存储这个堆的数组，n为它的最大下标。

回到原题，这一题要求我们每次累加最大的。

我们就建大根堆。

具体注释代码会有的。

有些地方会编译错误，说不定是故意的。

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
#include<cstdio>
#include<iostream>
#define N 1000000
using namespace std;
int a[N],n;//a数组存储堆，n为堆的最大下标。
void down(int x)//下沉
{
    while((a[x]<=a[x*2]&&x*2<=n)||(a[x]<=a[2*x+1]&&x*2+1<=n))
    {
        int wrong=0;
        try{//检查异常情况
            if(a[x*2]>=a[x*2+1]) throw wrong;//当找出x的左儿子比x的右二子大（或相等）时停止try的运行并抛出异常。
            swap(a[x],a[x*2+1]);
            x=2*x+1;
        }
        catch(int error){//当接收到异常
            if(wrong == error)
            {
                swap(a[x],a[x*2]);
                x*=2;
            }
        }
        //实际上这个try和throw和catch完全可以用if和else 和else if 代替，但是如此写比较正式（扯淡吧）
    }
}
void up(int x)//下沉
{
    while(a[x]>a[x/2]&&x>1)
    {
        swap(a[x],a[x/2]);
        x/=2;
    }
}
void work(int x)//插入堆底
{
    a[++n]=x;
    up(n);
}
int main()
{
    int ans=0,sum=0,h;
    int nn;
    scanf("%d%d",&nn,&h)//nn代表要插入的元素数量，h代表书架的高度。
    int b;
    for(register int i=1;i<=nn;i++)
    {
        scanf("%d",&b);
        work(b);//读入一个插入一个建堆。
    }
    while(true)
    {
        int wrong = 0;
        sum+=a[1];//大根堆，堆顶最大。
        ans++;
        try{	
		if(sum>=h) throw wrong;//当高度足够时跳出。
		a[1] =a[n];
		n--;
		down(1);
	}
	catch(int error)
	{
		if(wrong==error)
			break;
	}
}
printf("%d",ans);
return 0;

当代码能通过部分案例而不能完全通过时，考虑是不是结果越界了，可以考虑将数组开大一点

欧几里德距离（两点之间距离公式）

1
2
3
4
5
	ans+=sqrt((a[i-1].x-a[i].x)*(a[i-1].x-a[i].x)+(a[i-1].y-a[i].y)*(a[i-1].y-a[i].y)+(a[i-1].z-a[i].z)*(a[i-1].z-a[i].z));//题意给的公式,sqrt是开根号
	或者
	ans+=sqrt(pow(s[i].x - s[j].x,2) + pow(s[i].y - s[j].y,2) + pow(s[i].z-s[j].z,2));
	
printf("%.3lf",ans);//保留三位小数

排序算法（几个数如何连接组成的和最大）

题目描述

设有 $n$ 个正整数 $a_1 \dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 $n$。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

输出格式

一个正整数，表示最大的整数

样例 #1

样例输入 #1

1
2
3
13 312 343

样例输出 #1

1
34331213

样例 #2

样例输入 #2

1
2
4
7 13 4 246

样例输出 #2

1
7424613

提示

对于全部的测试点，保证 $1 \leq n \leq 20$，$1 \leq a_i \leq 10^9$。

1
2
3
4
5
6
7

使用比较函数 cmp 后 sort 将字符串输出可得答案

bool cmp(string a,string b){
    return a>b;//比如19 219  21919比19219大
}

day 10/23

求矩阵包含正方形和长方形个数（递归）

一、算正方形的个数

1.如果我们固定了正方形的右下角(i,j),你能不能算出此时可能的正方形的个数？

2.显然，此时答案为Min(i,j).

3.所以可以枚举右下角，计算此时答案，求和即可。

二、算长方形个数

1.其实算长方形并不常见，但算矩形大家应该经常遇到，所以如果你会算矩形，再联系第一个问题，那答案就转化为 矩形个数-正方形个数.

2.像求解正方形个数一样，固定矩形右下角(i,j),显然此时矩形个数为i*j.

3.同理，求和即可.

时间复杂度：O(n*m)，是挺慢的，其实可以写成一个式子

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main()
{
	ll n,m,i,j,sum=0,sum1=0;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
	  for(j=1;j<=m;j++)
	  {
	    sum+=min(i,j);
	    sum1+=i*j;
	  }
	}
	
	cout<<sum<<" "<<sum1-sum<<endl;
	return 0;
}

第二种算法：

首先，统计一个n*m的矩形里有多少个正方形，长方形。

要明确，正方形和长方形都是矩形，那么n*m的矩形里的

矩形数=正方形数+长方形数

明确这一点后，就可以一次求出二者了

img img

如图，长为2宽为1的小长方形用〇来表示，那么

横向排列的就有 （n-1）*m 个

竖向排列的就有 n*（m-1） 个

证明：

1
2
3
4
5
∵ 矩形长不等于宽

∴ 子矩形构成的矩阵的长宽是由原矩形长宽减去不同数而得

即(n-b)*(m-a) (a≠b)

img

如图，用 · 表示长宽均为二的正方形

即有(n-1)*(m-1)个小正方形

证明：

1
2
3
4
5
∵正方形长等于宽

   ∴子正方形构成的矩阵的长宽由原矩形长宽减去相同数而得
   
   即(n-b)*(m-a) (a=b)

上代码！（最短）

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
long long n,m,rec,sqr;
int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++)//循环，从n-0到n-(n-1)
        for(int j=0; j<m; j++) {//循环，从m-0到m-(m-1)
            if(i==j) sqr+=(n-i)*(m-j);//如果i==j，说明是正方形
            else rec+=(n-i)*(m-j);//如果不等说明是矩形
        }
    cout<<sqr<<" "<<rec<<endl;//输出
    return 0;
}

暴力枚举—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
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

#include<iostream>  
using namespace std;  
int main()  
{  
    int a,b,c,d,e,f,g,h,i,j,in,x=0;  
    cin>>in;  
    for (a=1;a<=3;a++)  
    {  
        for (b=1;b<=3;b++)  
        {  
            for (c=1;c<=3;c++)  
            {  
                for (d=1;d<=3;d++)  
                {  
                    for (e=1;e<=3;e++)  
                    {  
                        for (f=1;f<=3;f++)  
                        {  
                            for (g=1;g<=3;g++)  
                            {  
                                for(h=1;h<=3;h++)  
                                {  
                                    for (i=1;i<=3;i++)  
                                    {  
                                        for (j=1;j<=3;j++)  
                                        {  
                                            if (a+b+c+d+e+f+g+h+i+j==in)  
                                            {  
                                                x++;  
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
    cout<<x<<endl;  
    for (a=1;a<=3;a++)  
    {  
        for (b=1;b<=3;b++)  
        {  
            for (c=1;c<=3;c++)  
            {  
                for (d=1;d<=3;d++)  
                {  
                    for (e=1;e<=3;e++)  
                    {  
                        for (f=1;f<=3;f++)  
                        {  
                            for (g=1;g<=3;g++)  
                            {  
                                for(h=1;h<=3;h++)  
                                {  
                                    for (i=1;i<=3;i++)  
                                    {  
                                        for (j=1;j<=3;j++)  
                                        {  
                                            if (a+b+c+d+e+f+g+h+i+j==in)  
                                            {  
                                                cout<<a<<" ";  
                                                cout<<b<<" ";  
                                                cout<<c<<" ";  
                                                cout<<d<<" ";  
                                                cout<<e<<" ";  
                                                cout<<f<<" ";  
                                                cout<<g<<" ";  
                                                cout<<h<<" ";  
                                                cout<<i<<" ";  
                                                cout<<j<<endl;  
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
}

或者写成递归算法就是

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<iostream>
using namespace std;
int n,kind=0,m1[10000][10],m2[10];
void peiliao(int total,int a){
    if (a==10){
        if (total==n) {
            for (int j=0;j<10;j++) m1[kind][j]=m2[j];//符合要求存起来~~ 
            kind++;
        }
    }
    else if (total>=n) ;//小小优化一下 
    else
      for (int i=1;i<=3;i++){
          m2[a]=i;
          peiliao(total+i,a+1);//其实这和十连for没什么区别。。。 
      }
}
int main(){
    cin>>n;
    peiliao(0,0);
    cout<<kind<<endl;
    for (int j=0;j<kind;j++){
      for (int i=0;i<10;i++) cout<<m1[j][i]<<" "; //大家一定要记得打空格... 
     cout<<endl; 
    }
    return 0;
}



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
31
32
33
34
35
36
37
38
39
40
41
42
43
void dfs(int step){
if（到达目的地）{
	输出解
	返回
	}
合理的剪枝操作
for(int i=1;i<=枚举数；i++){
	if（满足条件）[
	更新状态位；
	dfs(step+1);
	恢复状态位；
		}
	}
}



当进入一个递归完返回时记得把变量赋初值！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！


#include<bits/stdc++.h>
using namespace std;
int r,a[100],n;
void dfs(int k){//搜索第k个数
    int i;
    if(k>r){
        for(i=1;i<=r;i++){
            cout<<setw(3)<<a[i];//输出，场宽为三
        }
        cout<<endl;
        return ;//回到前一层
    }
    for(i=a[k-1]+1;i<=n;i++){
        a[k]=i;
        dfs(k+1);//直接进行下一次调用
    }
}  
int main()  
{   
    cin>>n>>r;
    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
24
int m, n, b[21] = { 0 };
void f(int start, int total)
{
	if (n == total) {
		for (int i = 1;i <= m;i++)
		{
		if (b[i]){cout << i;	}
		}	
		cout << endl;	return;}
	for (int i = start;i <= m;i++)
	{
		b[i] = 1;
		f(i + 1, total+1);
		b[i] = 0;
	}
	return;
}

int main()
{
	cin >> m >> n;//从m个元素里面挑出来n个数
	f(1,0);
}

求回文数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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
灵感来自
产生长度为 5 的回文数：

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

自己写的
void dfs(int step)
{
    if (step == 0) { if (isprime(p)) { cout << p << endl; }return; }
    if (!flag) {
        flag = true;
        for (int i = 1;i <= 9;i += 2)
        {
            temp1 = p;p += i * pow(10, 2 * step + r) + i * pow(10, k);r++;k++;
            dfs(--step);
            step++;r--;k--;
            p = temp1;;
        }      
    }
    for (int i = 0;i <= 9;i ++)
    {
        if (step == 1) { temp2 = p;p += i * pow(10, k);dfs(--step);  p = temp2;step++; }
        else {
            temp3 = p; p += i * pow(10, 2 * step + r) + i * pow(10, k);r++;k++;
            dfs(--step);
            step++;r--;k--;
            p = temp3;
        }
        
    }


}

实际上。。。
bool isHWS(int num) {

    int temp=num,ans=0;
    while (temp!=0) {
        ans=ans*10+temp%10;
        temp/=10;
    }
    if (ans==num)
        return true;
    else
        return false;
}

day 10/26

01背包问题—-左右脑，

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
01背包算法
#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,k,sum,t,homework[21],dp[2501];
int main(){
	for(i=1;i<=4;i++)
		cin>>a[i];
	for(i=1;i<=4;i++){
		sum=0;	
		for(j=1;j<=a[i];j++)
			{cin>>homework[j];//输入
			sum+=homework[j];}//总时间累加
		for(j=1;j<=a[i];j++)
			for(k=sum/2;k>=homework[j];k--)//只要是总和的一半
				dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);//01背包
		t+=sum-dp[sum/2];//累加为另一个脑子
		for(j=1;j<=sum/2;j++)
		dp[j]=0;//清零
	}
	cout<<t;//输出
	return 0;
}



dfs算法

void f(int left,int right,int step,int n){
if(step==s[n]){
int tmp= max(left,right);
if(tmp <mark[n])mark[n]=tmp;
}
step++;
f(time[n][step]+left,right,step,n);
f(left,time[nl[stepl+right,step,n)；
}

dfs算法另一种写法,跟左右脑相似

P2036 [COCI2008-2009#2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


void dfs(int step,int suandu,int kudu)
{
	if (step == n) {
		 temp= abs(suandu - kudu); 
		if (temp < max1 && kudu != 0) { max1 = temp; }
		return;
	}
	step++;
	///下面两行是重点！！！包含了所有情况
	dfs(step, suandu*a[step], kudu+b[step]);///每一次在里面乘，不会影响外面的结果
	dfs(step, suandu, kudu);//跳过这一次，不乘！！！
	///
}
int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++) { cin >> a[i]>>b[i]; }
	dfs(0,suandu,kudu);
	cout << temp;
}

day10/27

斐波拉契数列+高精度求法(范围较大时)

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
long long n, a[10000] = { 1 }, b[10000] = { 1 }, c[10000] = { 1 }, clen = 1;
void f() {
	int jw = 0;
	for (int i = 0;i <clen;i++)
	{
		c[i]= jw+a[i] + b[i];
		jw = c[i] / 10;
		c[i] %= 10;
	}
	if (jw != 0)
	{
		c[clen++] = jw;
	}
	for (int i = 0;i<clen;i++)
	{
		a[i] = b[i];
		b[i] = c[i];
	}//相当于a=b c=b
}
int main()
{
	cin >> n;
	a[0] = 1;b[0] = 1;
	for (int i = 2;i <= n;i++)
	{
		f();
	}
	for (int i = clen-1;i >= 0;i--)
	{
		cout << c[i];
	}
}

过河卒！！！本质为递归，梦开始的地方

P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

核心思路：让它的上面一个点和左面的一个点加和，因为只能从这两种方向到达这个点。与斐波那契数列思路一样

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<stdio.h>
#include<iostream>
using namespace std;
long long  tx, ty, mx, my,  arr[30][30] = { 0 }, tmp[30][30] = { 0 };//
数组开大点，防止越界！！！且用long long 
arr用来记录能不能走，
tmp用来记录到达每个点分别有多少种方法，就是让它的上面和左面的点加和，因为只能从这两种方向到达这个点。

int main() {
	
	cin >> tx >> ty >> mx >> my;
	tx += 2;ty += 2;mx += 2;my += 2;//初始点加2
	for (int i = 2;i <= 30;i++)
	{
		tmp[i][2] = 1;
		tmp[2][i] = 1;
	}//把第一行和第一列全赋值为1，因为只有一条路能到达！
	arr[mx+2][my+1] = 1;
	arr[mx-1][my+2] = 1;
	arr[mx+1][my+2] = 1;
	arr[mx-2][my+1] = 1;
	arr[mx][my] = 1;
	arr[mx - 2][my - 1] = 1;
	arr[mx-1][my-2] = 1;
	arr[mx+1][my-2] = 1;
	arr[mx+2][my-1] = 1;
	//将马所在的点和其余能跳到的8个点都赋值为1，表示不能到达
	tmp[2][1] = 1;//起始点为2,2，到达方式为1，让[2][1]或者[1][2]=1都可，这样才能让[2][2]加和为1
	for (int i = 2;i <= 30;i++)
	{
		for (int j = 2;j <= 30;j++)
		{
			if (arr[i][j] == 1) { tmp[i][j] = 0;continue; }//如果不能到达，则让其等于零，表示无法到达，也就不用加和了
			tmp[i][j] = tmp[i - 1][j] + tmp[i][j - 1];//让它的上面和左面的点加和，因为只能从这两种方向到达这个点
		}
	}
	cout << tmp[tx][ty];

}

卡特兰数—-递归与栈

P1044 [NOIP2003 普及组] 栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

既然很多Dalao都说过，那我直接给式子了；

  • 递推式11：

f[n]=f[0]∗f[n−1]+f[1]∗f[n−2]+…+f[n−1]∗f0

然后按照这个递推式模拟就好了(代码后面给)

既然上面标了1，那就有递推式2~

  • 递推式22：

h[n]=h[n−1]∗(4∗n−2)/(n+1)

依旧按式子模拟(代码后面给)

既然有2，那再来个3吧~

  • 递推式33：

h[n]=C[2n,n]/(n+1)(n=0,1,2,…),C是组合数

P**S:C[m,n]=C[m−1,n−1]+C[m−1,n]:且规定：

[0,0]=1C[n,0]=1C[n,n]=1C[0,0]=1

这个公式也叫组合数公式(下面那个也是)

（不知道组合数可以百度）

于是仍然把标程放到最后~

  • 递推式44：

h[n]=C[2n,n]−C2n,n−1 组合数C不解释了；

没有55了

但是有个Dalao写的组合数我没看懂，于是我搜集了各方资料，还是没看懂，不知道他写的组合数是怎么求的，虽然最后结果对了，但是组合数求出来都是错的(￣_￣|||)，不知道是不是巧合？

不管了，A*C就好；（程序还是后面给~）

  • 但是，出现了一个问题，上面介绍了四种公式，哪种最好？其实是第4种：如果这个数太大，那么题目可能会要求取模，那么第11种n太大的时候时空太大；第22种在取模运算中万一不小心整除了就凉了；第33种是除法运算，更行不通；唯有第44种,满足取模原则（加减无所谓），且不会出现倍数 W**A 的情况，所以第44种解为最优解；
  • 接着，比较上面四种做法：很明显的，递推式长得差得不多，它们都源于卡特兰思想，那么就没什么好说的了，只是时空复杂度的不同而已；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
h(n)=h(1)∗h(n−1)+h(2)∗h(n−2)+...+h(n−1)h(1)
#include<bits/stdc++.h>
using namespace std;
int n;
int h(int n){
	if(n==0 or n==1) return 1;
	int a=0;
	for(int i=0;i<n;i++){
		a+=h(i)*h(n-1-i);//我是公式
	}
	return a;
}
int main(){
	cin>>n;
	cout<<h(n);
	return 0;
}

day10/28

记忆化

记忆化一般出现在递归题中，由于递归会一次一次的调用先前已经调用过的值，可能会造成时间复杂度非常大，因此我们可以用一个数组等记录已经出现过的结果，等第二次在调用时可直接返回值。例题如下

P1464 Function - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a, b, c, f[30][30][30];//f数组即为记忆化数组，记下已经调用过的值

int w(int a, int b, int c)
{
    if (a <= 0 || b <= 0 || c <= 0) { return 1; }
    if (a > 20 || b > 20 || c > 20) { return(w(20, 20, 20)); }
    if (f[a][b][c] > 0)return(f[a][b][c]);//这句只能前两句边界判断之后！！！一定要先判断边界！
    if (a < b && b < c) { f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);return(f[a][b][c]); }
    f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    return(f[a][b][c]);
}

int main()
{
    
    while (scanf("%d%d%d", &a, &b, &c))
    {
        if (a == -1 && b == -1 && c == -1) exit(0);
        printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    }
    return 0;
}

dfs超时后的新思路—-01背包（对于每一种物品，只有选中与未选中两种状态）！！！！！

01背包原理：在选与不选之间抉择。若剩余的东西（比如钱）充足，办法总数就等于选这个东西的办法数与不选这个东西的办法数之和；若不充足，办法总数就只能承袭选择前i-1种东西的办法总数。依次递推，在最后，我们只要输出f[n][m]的值即可。

P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

image-20231028210225636

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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,value[105] = {0}, f[105][1005] = { 0 };

int main()
{
	cin >>n>>m;
	for (int i = 1;i <= n;i++)
	{
		cin >> value[i];
	}
	for (int i = 1;i <= n;i++)//i代表菜品
	{
		for (int j = 1;j <= m;j++)//j表示钱数
		{
			if (value[i] == j) { f[i][j] = f[i - 1][j] + 1; }//如果价值等于钱数，选择这道菜以后就一种情况，再加上不选的情况
			else if (value[i] > j) { f[i][j] = f[i - 1][j]; }//如果价值大于钱数，就只有不选的情况
			else { f[i][j] = f[i - 1][j] + f[i - 1][j - value[i]]; }//如果价值小于钱数，分为选与不选两种情况,选的情况要用钱数减去该物品价值
		}

	}
	cout << f[n][m];
	
}


当数据范围过大或长度超过限制时，就不要用暴力破解了，记得找规律！比如将第一个跟第二比，再把第一跟第三比

P3612 [USACO17JAN] Secret Cow Code S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

int main()
{	
	string s;long long int n,k,len=0,len1=0;cin >> s >> n;
	len = s.length();
	k = len;
	while (n > k)
	{
		k *= 2;
	}
	
	while (n > len) {
		len1 = k / 2 + 1;
		if (n >= len1) {
			if (n == len1) { n--; }

			else { n -= len1; }
		}
		k = k / 2;
	}
	
	cout << s[n - 1];
}

注意对特殊情况的判断，比如多项式最后一项没有加号

当递归题涉及到两种不同的情况（比如两种长度不同的砖块），要对这两种情况分别讨论，最好建立两个数组，然后最好从最后算起，看他跟他的上一个有没有什么规律可找，即类似f(n)=f(n-1)+f(n+2)的

P1990 覆盖墙壁 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;


int main()
{ 
	int n, b2[10005] = { 0,1,2 }, b3[10005] = { 0,0,1 };
	cin >> n;
	for (int i = 3;i <= n;i++)
	{
		b2[i] = (b2[i - 1] + b2[i - 2] + 2 * b3[i - 1])%10000;
		b3[i] = (b2[i - 2] + b3[i - 1])%10000;
	}
	cout << b2[n];
}

当题目涉及的范围比较大的时候，比如100*100，要先拆分成一个一个的小单位，寻找有无规律可循，由局部推整体

P1228 地毯填补问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

当前面都有规律可循，而到最后却没有规律的时候，不妨试试对最后几行打表（）

P1259 黑白棋子的移动 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

day10-30

暴力算法—-结构体排序

在计算排序大小时，可以构建数组，然后用sort(在algorithm头文件里)按照某种规则对数组进行排序

P1803 凌乱的yyy / 线段覆盖 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
typedef struct
{
	int time;
	int id;
}coin;
bool cmp(coin c1, coin c2)
{
	return c1.time<c2.time;
}
int main()
{ 
	int n;double result = 0; coin coin1[1000] = { 0 };
	cin >> n ;
	for (int i = 1;i <= n;i++)
	{
		cin >> coin1[i].time;
		coin1[i].id = i;
	}
	sort(coin1+1, coin1 + n+1, cmp);
	for (int i = 1;i <= n;i++)
	{
		cout << coin1[i].id << " ";
		result += (n - i) * coin1[i].time;
	}
	cout << endl;
	printf("%.2lf",result/n);
}

线段覆盖—-结构体排序

按时间排序，有先后顺序，问最多能参加多少场

P1803 凌乱的yyy / 线段覆盖 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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>//（万能库）
struct px{//（定义一个结构体数组，分别储存开始时间和结束时间）
int a;//（开始时间）
int b;//（结束时间）
}x[2000000];
bool cmp(px x,px y){//（不管开始时间，直接按照结束时间排序）
return x.b<y.b;
}
using namespace std;
int main(){
int n,sum=1,mi;
scanf("%d",&n);
for(int i=1;i<=n;i++)
cin>>x[i].a>>x[i].b;//（读入数据）
sort(x+1,x+n+1,cmp);//（排序）
mi=x[1].b;//（无脑记录第一个值）
int j=1;
while(j<=n)//（未优化的超长循环）
{
    j++;
    if(x[j].a>=mi) {//（找到符合要求的比赛，记录，参加）
    sum++;//（计数）
    mi=x[j].b;}
}
cout<<sum;//（输出）
return 0;//（功德圆满）
}

首位相连区域,若中间中断则从左至右

P5019 [NOIP2018 提高组] 铺设道路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
long long ans=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)     cin>>a[i];
	for(int i=2;i<=n;i++)     if(a[i]>a[i-1]) ans+=a[i]-a[i-1];
	cout<<ans+a[1];
	return 0;
}



暴力算法中的双指针问题

用左右两个指针分别遍历，往往是求最大值或是最小值时使用

NOIP2007 普及组] 纪念品分组 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
int main()
{
	long long int  n,arr[3005],result=0,left=0,right=0;
	bool flag = true;
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		cin >> arr[i];
	}
	sort(arr + 1, arr + n + 1);
	left = 1;right = n;
	result += arr[n] * arr[n];
	while (left <= right)
	{
		if (flag) {
			flag = false;result += abs((arr[left] - arr[right]) * (arr[left] - arr[right]));
			right--;
		}
		else { flag = true; result += abs((arr[left] - arr[right]) * (arr[left] - arr[right]));
		left++;
		}
	}
	cout << result;


}

P4995 跳跳！ - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

二叉树的排序和sort排序的简化（当超出时间复杂度时）

找两个最小的叶子结点相加，再拿相加之和与剩余节点相比，再找找两个最小的叶子结点相加，循环往复

此时用sort排序可能超时，我们可以只拿新的相加之和与数组剩余元素比较，节省时间，也叫冒泡单排序

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
int main()
{
	int n, arr[10005]={0}, result = 0;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> arr[i];
	}
	sort(arr + 1, arr + n + 1);//先对原数组进行排序，下面对相加之后的新元素进行排序
	for (int i = 2;i <= n;i++)
	{
		result += arr[i] + arr[i - 1];
		arr[i] = arr[i] + arr[i - 1];//每次取最小的两个数相加
		for (int j = i + 1;j <= n;j++)
		{
			if (arr[j] < arr[j - 1]) { swap(arr[j], arr[j - 1]); }//每次只拿这个新元素与数组元素比较，而sort排序需要对数组全新重排，这种方法可以减少时间复杂度
		}
	}
	cout << result;
}



day11-2

在做有关于数字类的题目时，考虑0这种特殊情况！

P1106 删数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

从s中找到n-k个数，让i从0到n-k-1进行循环，mark做标记，从mark到k+i进行循环，找到最小值

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

string s;
int n, k, mark = o, flag = 0；
int find_min(int 1, int r)(
char minc = s[1];
mark = 1 + 1;
for(int i = mark; i <= r; i++)(
if(s[i] < minc)(
minc = s[il;
mark = i+ 1;
}}return minc;}
}
int main()(
//输入数据string s，int k，求出n
cin >> s >> k;
n = s.length();
// 丛s 中找到n-k 个数
//i:θ - n-k-1 mark~k+i 找出最小值
for(int i = 0; i < n - k; i++)(
cout << find_min(mark, k + i);}
for(int i =0;i< n -k;i++){
tempi= find_min(mark,k +i);
if(tempi ==0 &&flag ==0){
continue;
}
flag=1;
cout <tempi;
)
return 0;
}

定义结构体数组时不要加typedef！！！

1
2
3
4
5
6
 struct zu1{
	int len;
	int nowvalue;
}zu[100005];


蜘蛛纸牌类排序问题写法

AHOI2018初中组] 分组 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
int n, arr[100005],min1=9999,number=0,mark=0;
 struct zu1{
	int len;
	int nowvalue;
 }zu[100005] = { 0 };

void insert(int k)
{
	int flag = 0, find = 0,tnum=100005;
	for (int i = 0;i < mark;i++)
	{
		if (zu[i].nowvalue == k - 1) {
			if (zu[i].len < tnum)
			{
				flag = i;find = 1;tnum = zu[i].len;
			}
		}
	}
		if (find == 1) {

			zu[flag].nowvalue = k;
			zu[flag].len++;
		}
		else {
			zu[mark].nowvalue = k;
			zu[mark].len = 1;
			mark++;
		}

	}
int main()
{
	
	cin >> n;
	for (int i = 0;i <n;i++)
	{
		cin >> arr[i];
	}
	sort(arr , arr  + n);
	for (int i = 0;i < n;i++)
	{
		insert(arr[i]);
	}
	for (int i = 0;i <mark;i++)
	{
		if (zu[i].len < min1) { min1 = zu[i].len; }
	}
	cout << min1;
}


day11-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
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include <map>
int n, m, arr[10005] = { 0 }, chaxun = 0;
int erfen(int k)
{
	int l = 1, r = n,mid=l+(r-l)/2;
	while (l < r) {
		mid = l + (r - l) / 2;
		if (arr[mid] >= k) { r = mid; }
		else { l = mid + 1; }
	}
	if (arr[l] == k) { return l; }
	return -1;
}
int main()
{
	cin >> n>>m;
	for (int i = 1;i <= n;i++)
	{	cin >> arr[i];}
	for (int i = 1;i <= m;i++)
	{
		cin >> chaxun;
		chaxun=erfen(chaxun);
		cout << chaxun<<" ";
	}
}


lower_bound和upper_bound的妙用

P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

原写法（映射）

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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include <map>
long long int n=0, m=0, arr[2000005], len = 0,temp=0,b[3000005];

int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		cin>>arr[i];
		b[arr[i]]++;
	}
	for (int i = 1;i <= n;i++)
	{
        if(arr[i]<m){continue;}
		len += b[arr[i] - m];
	}
	cout << len;
return 0;
}


用c++ stl库函数lower_bound和upper_bound的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>//万能头文件
using namespace std;/命名空间
int n,c,a[200005];
long long ans 0;
int main（）{
cin >>n>>c;
for(int i=0;i<n;i++)cin >>a[i];
sort(a,a+n);
for(int i=0;i<n;i++){
ans +=upper_bound(a,a+n,a[i]+c)-lower_bound(a,a+n,a[i]+c);}//用找到第一个大于的数的下标和减去第一个找到的大于等于的数的下标，即为该数在数组中的个数，若没有二者都指向为迭代器，结果为0；
cout <<ans;
return 0;
}

砍树，求长度最小值中的二分

P1873 [COCI2011-2012#5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

把所有可能出现的长度都试一遍，如果满足结果就输出，如果在一个范围里（或者说不是整数）就用二分求出最

符合的题解

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<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include <map>
long long int n = 0, m = 0, arr[1000005], len = 0, temp = 0, b[3000005];
bool cmp(int a, int b)
{
	return a > b;
}
int main()
{
	cin >> n >> m;
	for (int i = 0;i < n;i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n, cmp);
	int l = 0, r = 100000000; //树最高是100000000米，所以右边界要取到100000000，从0到10000000遍历
	while (l <= r)
	{
		int mid = l + (r - l) / 2;
		long long total = 0;
		for (int i = 0;i < n;i++) {
			if (arr[i] > mid) {
				total += arr[i] - mid;
			}
			else { break; }
		}
		if (total > m) { l = mid + 1; }
		if (total < m) { r = mid - 1; }//刚开始右边界是100000000，每次减1，mid每次也除于2
		if (total == m) { cout << mid;return 0; }//正好求出结果时，直接打印
	}
	cout << r;return 0;//若未完美求出结果，则打印最接近结果的的数
}

用二分法求方程组为0的解

P1024 [NOIP2001 提高组] 一元三次方程求解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

方程f(x)=0，若存在 2 个数 x1 和 x2，且 x1<x2，f(x1)×f(x2)<0，则在 (x1,x2) 之间一定有一个根，此时我们就可以把区间定在一个数和这个数加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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include <map>
double a, b, c, d;
double fc(double x)
{
    return a * x * x * x + b * x * x + c * x + d;
}
int main()
{
    double l, r, m, x1, x2;
    int s = 0, i;
    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);  //输入
    for (i = -100;i < 100;i++)//从题中所给的范围进行遍历
    {
        l = i;
        r = i + 1;
        x1 = fc(l);
        x2 = fc(r);
        if (!x1)
        {
            printf("%.2lf ", l);
            s++;
        }      //判断左端点，是零点直接输出。

                        //不能判断右端点，会重复。
        if (x1 * x2 < 0)                             //区间内有根。
        {
            while (r - l >= 0.001)                     //二分控制精度。
            {
                m = (l + r) / 2;  //middle
                if (fc(m) * fc(r) <= 0)
                    l = m;
                else
                    r = m;   //计算中点处函数值缩小区间。
            }
            printf("%.2lf ", r);
            //输出右端点。
            s++;
        }
        if (s == 3)
            break;
        //找到三个就退出大概会省一点时间
    }
    return 0;
}


lower_bound(返回第一个大于等于的值的下标）用法巩固，注意全部大于和全部小于的情况

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;
int a,b,c[100002],d,e,f,g,h,i,j,k,l;
long long ans;
int main()
{
    cin>>a>>b;
    for(i=1;i<=a;i++)
        cin>>c[i];
    sort(c+1,c+a+1);//先排序一下
    for(i=1;i<=b;i++)
    {
        cin>>d;
        e=lower_bound(c+1,c+a+1,d)-c;//返回查询到的位置
        if(e==a+1)
        ans+=d-c[a];//特判比所有数都大的情况
        else
            if(e==1)//特判比所有数都小的情况
                ans+=c[1]-d;
            else
                ans+=min(abs(c[e]-d),abs(d-c[e-1]));
    }
    return 0;
}


day11-8

二分法，尝试可能的所有结果

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>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include <map>
int m, n, a[100005], b[100005], result = 0, l = 0, r = 100000000, mid = l + (r - l) / 2, mark = 0,max1=0;
int main()
{
    int m, n, k;
    cin >> m >> n >> k;
    for (int i = 1;i <= n;i++)
    { cin >> a[i];}
    for (int i = 1;i <n;i++)
    {
        b[i] = a[i + 1] - a[i];
        max1 = max(max1, b[i]);//取间隔最大值，结果不可能比这个大，所以让右边界与其相等即可
    }
    r = max1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        mark = 0;
        for (int i = 1;i < n;i++)
        {
            max1 = b[i];
            while (max1 > mid)
            {
                mark++;
                max1 -= mid;//每一种间隔都对应一种结果加和
            }
        }
        if (mark <= k) { r = mid - 1; }//看看在当前间隔时结果是大了还是小了
        else{ l = mid + 1; }
    }
    cout << 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>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include <map>
 int m, n, a[100005] , l = 0, r = 12, mid = l + (r - l) / 2, mark = 1,temp=0;
int main()
{
    cin >> m >> n;
    for (int i = 1;i <= m;i++) { cin >> a[i];l = max(l, a[i]); }
    while (l <= r)
    {
        mid = l + (r - l) / 2;
        temp = 0;mark = 1;
        for (int i = 1;i <= m;i++)
        {        
            if (a[i] + temp <= mid) { temp += a[i];continue; }
            if (a[i] + temp > mid) { temp = a[i];mark++;continue; }
        }
        if (mark <= n) { r = mid - 1; }
        else { l = mid + 1; }
    }
    cout << l;
}

银行贷款利息问题

P1163 银行贷款 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
a=(...（m*(1+x)-y)(1+x)-y)...)（共t次乘法）（秦九韶算法）（m表示贷款的原值、y表示每月支付的分期付款金额、t表示分期付款还清贷款所需的总月数，a表示在t个月后按二分得到的利率还剩下多少钱没有还）。如果a是正数说明利率过大，则从左侧继续二分查找；如果a是负数说明利率过大，则从右侧继续二分查找；如果a等于零则输出结束程序。二分查找结束的另一个条件是精度小于0.0001。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
double m,y,s;
int t;
int out(double k)
{
    printf("%.1f",k*100);
    exit(0);
}
void solve(double l,double r)
{
    double k=(l+r)/2,u=r-l;
    double a=m;
    if(u<0.0001) out(k);
    for(int i=1;i<=t;i++)
          a=a*(1+k)-y;
    if(a>0) solve(l,k);
    if(a<0) solve(k,r);
    if(a==0) out(k);
}
int main()
{
    cin>>m>>y>>t;
    solve(0,5);
}

day11-9

递归加搜索

搜索的写法一般都是有好几个数组，每个数组对应一种情况，然后通常会与递归相结合起来

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<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100],b[100],c[100],d[100];
//a数组表示的是行；
//b数组表示的是列；
//c表示的是左下到右上的对角线；
//d表示的是左上到右下的对角线；
int total;//总数:记录解的总数
int n;//输入的数，即N*N的格子，全局变量，搜索中要用
int print()
{
    if(total<=2)//保证只输出前三个解，如果解超出三个就不再输出，但后面的total还需要继续叠加
    {
        for(int k=1;k<=n;k++)
        cout<<a[k]<<" ";//for语句输出
        cout<<endl;
    }
    total++;//total既是总数，也是前三个排列的判断
}
void queen(int i)//搜索与回溯主体
{
    if(i>n)
    {
        print();//输出函数，自己写的
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)//尝试可能的位置
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领，执行以下程序，这里的d数组加n是考虑到可能会相减成负数的情况，所以加上n的偏移量
            {
                a[i]=j;//标记i排是第j个
                b[j]=1;//宣布占领纵列
                c[i+j]=1;左边上下对角线，每行的i+j都相等,相减为定值
                d[i-j+n]=1;右边上下正对角线，每行的i-j都相等
                //宣布占领两条对角线
                queen(i+1);//进一步搜索，下一个皇后
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
                //（回到上一步）清除标记
            }
        }
    }
}
int main()
{    
    cin>>n;//输入N*N网格，n已在全局中定义
    queen(1);//第一个皇后
    cout<<total;//输出可能的总数
    return 0;
}

当有两个组别求最大值时，可以先求一组的最大值，然后让他慢慢减，每减一次求一下当前的结果，如果大了就更新、最后直接输出最大值即可

image-20231109231424158

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<stdio.h>
#include<math.h>
int main()
{
	int n,m,a,b;
   long long sum,sum1,sum2,t;
   scanf("%d %d %d %d",&n,&m,&a,&b);
   sum1=fmin(n/2,m);//a礼包的最大数量 
   sum2=fmin(n-sum1*2,(m-sum1)/2);//a最大时，b的数量 
   sum=sum1*a+sum2*b;
   while(sum1){
   	sum1--;//a礼包数目逐渐减少 
   	sum2=fmin(n-sum1*2,(m-sum1)/2);
   	t=sum1*a+sum2*b;
   	if(t>sum)
   	{
   		sum=t;
	   }
   	
   }
   printf("%lld",sum);
}



day11-10

并查集

【算法与数据结构】—— 并查集-CSDN博客