标签：二分培训入门 int 复杂度算法数组我们

#include<bit/stdc++.h>//万能头文件
#define int long long //信息学竞赛界流传着一句话”十年竞赛一场空，不开longlong见祖宗“
using namespace std;
signed main(){
    printf("welcome to AC Algorithm Community");
    return 0;
}

计算机精神

RTFM:read the friendly manual(读友好的手册)
STFW:search thr friendly web(搜索友好的网络）

第一课

1 什么是算法

1.1 定义

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

1.2 特征

有穷性
一个算法总是在执行有限步数后结束（跑不完怎么行）
确定性
算法每一个步骤都是明确的，确定的（计算机可不会猜你心意）
输入
一个算法有0或多个输入
输出
一个算法有1或多个输出
可行性
算法每一个步骤都是要在有限时间内完成的（同1）

1.3 如何评价一个算法

正确性
可读性
健壮性 （这里是指容错性一般算法竞赛中不考虑，如果数据给错了，那出题人应该好自为之好好反思）
时间复杂度
空间复杂度

1.4 时间复杂度

一般我们用科学技术法表示比较大的数字，也方便我们更直观的计算量级
$aeb=a10^b$
例如$2.9e7=2.910^7$,$1e9=109$

一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n) 表示，若有某个辅助函数 f(n) ，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n)=Ｏ( f(n) ) ，称 Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
简而言之对于对于 T(n) 忽略其低次项与系数即可。

（上课举例详解）

1.5 空间复杂度

空间复杂度指程序使用空间大小规模
让我们复习一下基础数据类型占用多少空间

数据类型	大小
int	4B
long long	8B
double	8B
char	1B
bool	1B

8bit ==1B
1024B ==1KB
1024KB ==1MB
1024MB ==1GB
实际比赛中一般空间限制为 256MB ,思考一下，你可以开一个多大的数组，如果是正方形二维的呢？

2 模拟枚举贪心双指针

2.1 模拟

2.1.1 什么是模拟

模拟算法是一种最基本的算法思想，是对程序员基本编程能力的一种考查，其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟。在解决模拟类问题时，需要注意字符串处理、特殊情况处理和对题目意思的理解。
模拟算法，用一句老话说，就是“照着葫芦画瓢”；官方化的诠释则是：根据题目表述进行筛选提取关键要素，按需求书写代码解决实际问题。

2.1.2 怎么模拟

我们需要利用一些数据结构（比如数组）表示出题目中的元素，用一些代码表示出题目中的操作。

（上课举例详解）

2.2 枚举

2.2.1循环枚举

这是最简单的枚举，比如问一个数组中最大子段和，我们可以用枚举两个端点算出所有子段和求解。

2.2.2排列枚举

有一个函数叫做 next_permutation( start, end) ,这个函数的作用是将 [start, end) 的数组变为他的严格的下一个字典序排列,并返回是否变化成功（如果字典序已经最大则变化失败）。
例如$[2,3,1]$变成$[3,1,2]$,再下一步变成$[3,2,1]$

使用样例如下

#include<bits/stdc++.h>
using namespace std;
int a[100];
signed main() {
	int n=4;
	for( int i = 1; i <= n; i ++) a[i] = i;
	do {
		for( int i = 1; i <= n; i ++ ) cout << a[i] <<" ";
		cout<<"\n";
	} while(next_permutation(a+1, a+1+n));
}
//大家可以试一试跑一下这个代码(可以自己动手修改n的值并观察输出，不过n不要太大哦)

2.2.3 子集枚举(暴力)

先让我们先熟悉一下位运算

&& ，||，这些逻辑运算符想必大家已经了解了，在位运算中我们一般使用 &，| 进行计算。& 的作用是与( and ), | 的作用是或 (or) ,另外还有一个常用位运算符号 ^ 作用是异或(xor)。

a	b	a or b	a ^ b
0	0	0	1
0	1	1	0
1	0	1	0

由上图可见他们具有交换性

有人可能会好奇那两个双符号好像和他们的单符号一样啊。他们的区别在于双符号有着短路这一特性，如 a&&b ,如果 a 为 false ,则不管 b 为什么直接返回 false , || 反之亦然。
>> 与 << 在c++中代表着流，我们一般使用它进行输入输出，但是它也是一个运算符，众所周知数字在计算机中以二进制储存例如20为10100，我们把20赋值给一个int型变量 a，那么a就是10100，那么如果对他使用 >>3，那么它就会向右移动三位，至于移动前右边的三位该怎么办呢？那当然是丢掉了。所以现在他的二进制就变成了10，大家会发现a>>b实际上就是 $a/ 2^b$,并且下取整，如果是 <<,同理就变成了 $a2^b$。（这里对于截断溢出等底层原理不细讲，如果想要深入研究计算机内部底层原理，建议在以后的学期好好学习 《计算机系统基础》（袁春风））*

假设有八个物品在一个集合，如果想要枚举出这个集合的子集，那么如果从二进制为0枚举到11111111实际上我们就已经枚举出了8个位置的所有情况，也就是这个集合的所有子集。

上课举例详解

2.3 贪心

很多时候太贪婪不是一件好事，因为目光短浅，没有考虑到后面的事情，结果没有办法保证最后的结果做到最好。

但是在算法竞赛中求解某些问题的时候，只需要做出在当前看来是最好的选择就能获得最好的结果，而不需要考虑整体上的最优化，即使目光短浅也没有关系。
贪心不是所有问题都可以得到整体最优解，一定要具备无后效性(即某个状态之前的过程不会影响后面的状态)，一般来说只有能证明贪心是正确的，才可以使用贪心算法，如果能找到一个反例就说明不正确。
不过话说回来，如果我们连哪些东西是最好的都不知道，我们该怎么贪心呢，所以我们要学习排序！
c++友好的提供了一个函数叫做 sort ,如果你想要一个大小为$n$数组$a[]$升序排序，sort(a+1,a+1+n),可是如果我们想要降序排序，甚至是对一个自定义结构体数组排序，我们该怎么做呢？上课我们会讲的。

2.4 双指针

还记得校赛的那一题吗

jessc有一个女同学是幼儿园老师，她有一天向jessc请教了一个问题：我们班有n名小朋友坐成一排，我想一次给连续m名小朋友发糖果。但不是每个小朋友都喜欢我手里的糖果，那么我发一次糖果最多有几名小朋友开心呢？jessc已经被实验报告缠绕了，暂时没有时间，委托善良的你帮助他解决这个问题。

这题我们设置两个值$l,r$，作为两个指针（注意，不是语法里面的指针哦，不过作用倒是差不多），$l=1,r=m$,然后先算出当前这个区间的总和,接着每次$l++,r++$同时减去被丢出两个指针包含区间的最左边的元素值，再加上刚刚进来的最右边的元素的值，每次拿答案和当前总和比较一下，如果当前总和比答案大，便更新答案即可。
双指针的用法灵活多变，但是只要掌握基本思想，即可运用。

3 递推与递归

先让我们思考一个问题，如何求阶乘呢？？？

//递归
int Factorial(int x){
    if( x == 1 ) return 1;//再递归就不礼貌了
    else return x * Factoria l( x-1 );//x的阶乘当然是x-1的阶乘再乘上x啦
}
//递推
int Factorial[maxn];//Factorial[i]为i的阶乘
Factorial[1]=1;
for( int i = 2 ;i <= n ; i++ ){
    Factorial[i] = Factorial[i-1] * i;
 }

3.1 递推

3.1.1 前缀和与差分

前缀和

//前缀和在预处理后可以在 O(1) 的时间内求出任意区间和。
int Prefixes[maxn];//prefixes[i]为前i个数的总和
int sum(int l,int r) {
    return Prefixes[r]-Prefixes[l-1];
}//该函数求出[l,r]区间呢元素之和
for( int i = 1; i<= n; i++) Prefixes[i]=Prefixes[i-1]+a[i];//递推求出Prefixes数组

大家惊呼：好简单啊。。。不过二维的呢？~~（也蛮简单的就是了）~~

差分

我们从一个问题引入这个算法
c++老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？
第一行有两个整数 $n$，$p$，代表学生数与增加分数的次数。第二行有 $n$ 个数, $a_1,a_2...a_n$代表各个学生的初始成绩。接下来 $p$ 行，每行有三个数，$x，y，z$，代表给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。
题目的数据范围：$n\le 5e6, p\le n$

我们先思考一下如果采用上文提到的模拟，时间复杂度会是多少？
一共$p$次操作，每次复杂度为$O(n)$,总复杂度为很明显是 $O(np)$ , 无法通过。

我们可以注意到一个事实，就是每次对区间操作，每个数加上的数字都是一样的。

我们先想一想假如我们有一个数组，这个数组一开始每个元素都为$0$,然后如果我们在第三个位置加一个$1$，那么他的前缀和数组是什么样子的呢？应该是 :$0,0,1,1,1,1,1,1,1...$,接着我们在原数组第六个位置加上-1，那么他的前缀和数组就变成了这样：$0,0,1,1,1,0,0...$,我们惊奇的发现只要做两次操作，就可以使得的这个数组的前缀和数组的一个区间加上相同的值，这不就是我们想要的吗？

只要在$a[l]$和$a[r+1]$上加上$x$和$-x$ ,那么a的前缀和数组的$[l,r]$就会加上x,还是没有理解也没有关系，上课时会用图像来解释清楚。

int d[5000001];//差分数组
int a[5000001];
int main(){
	int n, p, x, y, z, i, min = 1e9;
	cin >> n >> p;
	for( i = 1 ; i <= n ; i ++ )   cin >> a[i];
    for( i=1 ; i <= n ; i ++ )  d[i] = a[i] - a[i-1];//初始化，将初始数组归并到差分数组中,可以看到这是前缀和的逆运算
	for( i = 0; i < p ; i ++ ) {
		cin >> x >> y >> z;
		d[x] += z;
		d[y+1] -= z;
	}
	for( i = 1 ; i <= n ; i ++ )	{
		a[i] = a[i-1] + d[i] ;
		if( min > a[i] )    min = a[i];
	}
	cout << min;
	return 0;
}

（什么？太简单了？递推当然没有这么简单，不过确实写不下了，其余上课详解）

3.2 递归（分治）

最简单的递归我们已经在本节求阶乘的地方给出了，如果能够完全理解的话大家可以自行搜索一下 汉诺塔，汉诺塔作为一个典中典的递归分治模型，已经存在很久了，网上到处都有相关思想图解代码，什么？太累了？内容太多？没有关系上课会讲的。

4二分查找与二分答案

前icpc世界决赛冠军Um_nik老哥说过，如果你连红名都没有，你就应该好好学习二分算法（二分战神称呼由来）~~所以，喜欢我二分吗？~~

4.1二分查找

给定一个含有$n$个元素的单调递增的数列和$m$次询问，每次询问给出一个整数$x$，怎么找到里面第一个不小于$x$的数呢？

每次一个个的找？很明显太慢啦，所以我们就要使用二分算法
二分算分：使用双指针指定区间，一开始双指针指向的是整个区间的左右两个端点，每次取中点，我们注意到这个数组是单调递增的，如果当前中点小于当前要找的数，那么中点左边的数字比中点还要小必然不会被我们选上，那么我们把左指针移动到中点右边第一个（因为中点自己也不行），如果当前中点大于要找的数字，说明答案要么是这个要么是左边的数字，区间右边的就可以排除了，于是我们可以把右指针移动到中点。

模板代码如下：

#include<cstdio>using namespace std;
int n,m,q,a[1000005];
int find(int x) //二分查找 {
        int l=1,r=n;
        while (l<r) {
                int mid=l+(r-l)/2;
                if (a[mid]>=x) r=mid;
                else l=mid+1;
        }
         if (a[l]==x) return l; //找都了就输出他的位置 
        else return -1; // 没找到输出-1 
}
int main(){
        scanf("%d %d",&n,&m); //读入 
        for (int i=1 ; i<=n ; i++)
        scanf("%d",&a[i]); //还是读入 
        for (int i=1 ; i<=m ; i++) {
                scanf("%d",&q);
                int ans=find(q); //看看查找的结果 
                printf("%d ",ans); //输出 
        }
        return 0;
}

这个算法好像写多了就无聊了，没关系，c++为我们提供了 lower_bound(),upper_bound() ,这是c++为我们封装好的二分函数。
当容器中的元素按照递增的顺序存储时，lower_bound(star,end,x) 函数返回$[start,end)$ 第一个大于等于目标值的位置(注意返回的是地址，所以如果要得到元素在数组中的下标，需要减去数组首地址)。

使用如下

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int a[MAXN];
int main(){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        while(m--){
                cin>>x;
                int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意减去a（数组首地址）
                if(x!=a[ans]) printf("-1 ");//没有，输出-1
                else printf("%d ",ans);//有，输出ans
        }
        return 0;//华丽结束
}

4.2二分答案

回想一下，二分查找其实是一个单调性判定问题。将这个问题抽象一下：已知答案如果存在，则存于在区间$[l,r]$上，并且如果某个点满足条件(大于x),那么右边的点也必然满足条件，那么先检验中点$mid$，如果条件不成立，说明答案在$[mid,r]$上，否则在$[l,mid-1]$上。

上课将详细讲解单调性判定问题并且举例详解更多单调性判定问题

附录

推荐

推荐c++语言学习书籍：《C++ Primer Plue》
推荐算法学习/比赛网站：acwing，牛客竞赛，洛谷，codeforces, atcoder

c++加速输入输出代码，放在main函数首部即可

ios::sync_with_stdio(false);
cin.tie(0); 
cout.tie(0);

标签：二分,培训,入门,int,复杂度,算法,数组,我们
From： https://www.cnblogs.com/107557224-qyj/p/17970049

入门培训

第一课