一、二分查找
算法原理
对于一个含有n个元素的无序序列，需要使用顺序查找来定位目标值。由于在最坏的情况下需要检查每一个元素，所以顺序查找算法的时间复杂度是O(n)。
当序列有序且可通过索引访问时，我们可以通过更有效的二分查找算法来定位目标值，不难算出其时间复杂度为O(log n)。这是一个显著的改进。
算法设计
1.首先初始化左值low，右值high，确定检索范围。数组长度为n，目标值为target。然后比较目标值和中间值候选项，即索引项[mid]的数据。
mid=(low+high)/2;
接下来考虑以下三种情况：
1.如果目标值等于[mid]的数据，则查找成功并终止。
2.如果目标值<[mid]的数据，则对前半部分序列重复这一过程，即索引的范围变为[low,mid-1]。
3.如果目标值>[mid]的数据，则对后半部分序列重复这一过程，即索引的范围变为[mid+1,high]。
如果low>high,说明索引范围内无元素，则查找不成功。
基础代码实现
int binary_search(int arr[],int low,int high,int target){
int ret=-1;//未查找到返回-1
int mid;
while(low<=high){
mid=(low+high)->1;//位运算
if(arr[mid]>target) high=mid-1;
else if(arr[mid]<target) low=mid+1;
else{//目标值等于[mid]值时查找成功，并结束循环
ret=mid;
break;
}
}
return ret;
}
下面来看一道运用二分查找算法寻找满足某条件的最大值的题目
暑期训练营第三周F 大佬的生日大礼包
题目大意：
今天是某大佬的生日，转发这场比赛到三个群就可以获得以下三种礼包之一。
豪华礼包：一个U盘、一个鼠标和一个机械键盘。
幸运礼包：一个U盘、两个鼠标。
普通礼包：两个U盘、一个鼠标。
大佬一共准备了a个U盘、b个鼠标和c个机械键盘，同时希望相邻的两位领礼包的参赛选手拿到的礼包类型都是不同的。
问：这些奖品最多可以发出多少份礼包？
输入描述:
输入第一行包含一个正整数T。 接下来T行每行包含3个正整数a, b, c，依次表示U盘、鼠标和机械键盘各有多少个。
输出描述:
输出T行，每行一个整数，表示最多能发出多少份礼包。
思路：
1.认真观察礼包的组成可以发现，每种礼包都含有1个u盘，1个鼠标和1个机械键盘。所以用a，b，c分别记录三种物品的数量，m表示礼包数量，通过赋值操作a=a-m，b=b-m后，此时的a，b，c就分别表示幸运礼包，普通礼包和豪华礼包的数量（以方便表示三种礼包之间的数量关系）。
2.由于希望相邻两个领到礼包的选手拿到的礼包类型都是不同的，所以需要满足数量较少的两种礼包的数量之和要大于等于总礼包数的一半（向下取整）。
3..由于需要找出能发出礼包的最大数量，我们可以采用二分查找的方式检索最大礼包数。若找到了满足条件的m，则向后半序列继续进行二分查找是否存在更大的满足条件的m；若当次找到的m不满足条件，则向前半部分的序列继续进行二分查找。
AC代码
#include<bits/stdc++.h>
using namespace std;
//判断是否能发出m个礼包
bool check(int a,int b,int c,int m){//m表示礼包数量
a-=m;
b-=m;//该赋值操作后a，b，c就分别表示幸运礼包，普通礼包和豪华礼包的数量
if(a<0||b<0||c<0||a+b+c<m) return false;//若a,b,c其中一者小于0或三种礼包数量之和小于总礼包数m，则无法发出m个礼包
else{
int arr[3]={a,b,c};
sort(arr,arr+3);
return arr[0]+arr[1]>=m/2;//数量较少的两种礼包的数量之和要大于等于总礼包数的一半（向下取整）
}
}
void solve(){
int a,b,c;
cin>>a>>b>>c;
int low=0,high=a+b+c;在
while(low<high){
int m=(low+high+1)>>1;//注意此处的low+high+1,缺少+1会进入死循环
if(check(a,b,c,m))
low=m;//若m满足条件，则记录m，继续向后半部分序列查找是否还存在更大的m
else high=m-1;//若m不满足条件，则继续向前半部分序列查找m
}
cout<<low<<endl;
}
int main(){
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
时间复杂度为O(mlog n)。
前缀和与差分
前缀和是指某序列的前n项和，可以将它理解为数学上的数列的前n项和，而差分可以看作前缀和的逆运算。合理地运用前缀和与差分可以有效地减少程序的时间复杂度。
假如有一个这样的问题： 输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。
我们很容易想到用暴力解法，把序列存入数组a中，通过遍历区间求和。
const int N=1e5 + 10;
int a[N];
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(m--)
{
int l,r;
int sum=0;
scanf("%d%d",&l,&r);
for(int i=l;i<=r;i++)
{
sum+=a[i];
}
printf("%d\n",sum);
}
然而这种做法的时间复杂度为O(n*m)，当n和m数据量稍大时，程序的效率比较低下。所以我们考虑用前缀和进行优化。
具体做法
首先做一个预处理，定义一个sum[]数组，其中sum[i]表示数组a的前i项和。每次查询第l个数到第r个数的和时，只需要执行sum[r]-sum[l-1]。
const int N=1e5 + 10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];//前缀和的初始化
}
int l,r;
cin>>l>>r;
cout<<sum[r]-sum[l-1])<<endl;//区间和的计算
这样对于每次查询，时间复杂度为O(1)。
差分可以看作前缀和的逆运算，类似于数学中的求导和积分。
差分数组：
给出一个数组a：a[0]，a[1]，a[2]，……，a[n]；
构造一个数组b ： b[1], b[2], b[3]，……， b[i]；
使得 a[i]=b[1] + b[2] + b[3] + …… + b[i]
也就是说，数组a是数组b的前缀和数组，而我们把数组b叫做数组a的差分数组。
差分数组的构造方法：
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] = a [3] - a[2];
........
b[n] = a[n] - a[n - 1];
因此我们只要知道数组b，就可以通过前缀和运算在O(n) 的时间内得到数组a。
有这样一个问题：
给定区间[l,r]，让我们把a数组中的[l,r] 区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c …… a[r] + c;
暴力做法是对区间[l,r]之间的每一个数进行遍历，如果需要进行m次查询，时间复杂度为O(n*m)。
考虑更高效的差分做法：
由于a是b的前缀和数组，所以b中b[i]的修改会影响a中a[i]之后的每一个数。
首先让b数组的b[l] + c，则a数组的a[l]之后的数变成 a[l] + c ，a[l + 1]+c，……，a[n] + c；
然后再让b数组的b[r+1] - c，则a数组的a[r+1]之后的数变成 a[r + 1] - c,a[r + 2] - c，……，a[n] - c。
这样对于每一次查询，时间复杂度为O(1)。
下面来看一道可以用二分+差分思想进行优化的题目：
2023河南萌新联赛第（七）场D题 借教室
题目较长，点击链接跳转：
思路1（非二分+差分）
用一个数组r来储存每天可用的教室数量，用一个pair数组来储存每个订单信息（first值为需要的教室数dj，second值为pair，用来存储始末天数sj，tj。
先遍历每一个订单，每个订单中再遍历始末天数中的每一天，对每天可用的教室数量进行修改。然后对剩余教室数量进行判断：若剩余教室数量小于0，则终止程序，输出-1以及订单编号；若每次剩余教室数量都大于等于0，最后输出0。
AC代码1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n,m;
cin>>n>>m;
long long r[1000005];
for(ll i=1;i<=n;i++){
cin>>r[i];
}
pair<ll,pair<ll,ll>> p[1000005];
for(ll i=1;i<=m;i++){
cin>>p[i].first>>p[i].second.first>>p[i].second.second;
}
for(ll i=1;i<=m;i++){
for(ll j=p[i].second.first;j<=p[i].second.second;j++){
r[j]=r[j]-p[i].first;
if(r[j]<0){
cout<<"-1"<<endl<<i;
return 0;
}
}
}
cout<<"0"<<endl;
return 0;
}
思路2（二分+差分）
每个订单的操作是对在[sj,tj]之间的r减去dj，所以我们可以用差分的方法加快处理过程。
由于需要找出第一个无法满足订单要求的申请人编号，所以可以通过二分查找出使教室数量第一次出现负值的订单编号。
时间复杂度分析
二分法的时间复杂度为O(log n)；每次差分后用二分求出每天可用的教室数量，时间复杂度为O(m+n)。因此总的时间复杂度为O((m+n)log n)
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; const int N = 1000010;
int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];//用来拷贝数组r
bool check(int k)
{
for (int i = 1; i <= n; i++) b[i] = r[i];//拷贝数组r
for (int i = 1; i <= k; i++)//进行差分处理
{
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
}
LL res = 0;
for (int i = 1; i <= n; i++)
{
res += b[i];
if (res < 0) return true;
}
return false;
}
int main()
{
cin>>n>>m;
for (int i = 1; i <= n; i++) cin>>r[i];
for (int i = n; i; i--) r[i] -= r[i - 1];
for (int i = 1; i <= m; i++) cin>>d[i]>>s[i]>>t[i];
//二分查找
int l = 1, r = m;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (check(r))
{
cout<<"-1"<<endl;
cout<<r;
}
else cout<<"0"<<endl;
return 0;
}
提交代码后，我们发现采用二分和差分后的算法效率大大提高了。
二、快速幂
1.普通幂算法
在程序设计比赛中，我们常常会遇到幂运算f(x)=a^x。但是由于幂运算的结果通常很大，就算连最大的long long类型都无法承载这么大的数值，所以题目经常要求对最后的结果进行取模。
根据取模运算的运算法则
(a * b) % p = ((a % p)* (b % p)) % p
我们可以在循环乘积的每一步都提前进行取模运算，而不是对a^x的原始数值直接进行取模，这样就能计算取模后的结果。下面给出一段代码：
//普通幂运算函数，base为底数，power为指数
long long normal_power(long long base,long long power){
long long result=1;
for(int i=1;i<=power;i++){
result*=base;
result%=1e9+7;
}
return result;
}
上面这段代码是利用取模的运算法则，通过直接的连乘并对1000000007取模进行幂运算。经过测试发现这个算法可以准确地进行幂运算，且不会出现数据溢出的情况。
但是这种普通幂算法的时间复杂度为O(n)（其中n为指数）。对于指数很大的数据，这个程序可能要运行很久很久（例如求2^1000000000要运行将近18秒），效率十分低下。所以我们要考虑使用快速幂算法进行优化。
快速幂
算法原理
快速幂的核心思想就是每一次把指数分成两半，而相应的底数做平方运算。这样就能把很大的指数不断变小，所需要执行的循环也不断减少，而最后的结果却不会改变。
例如我们要计算3^10，可以进行以下的变化：
3^10=3*3*3*3*3*3*3*3*3*3
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
如此一来，原本需要进行10次循环操作的3^10，现在只需要进行5次循环的9^5,减少了一半的循环量。当指数特别大时，简化的效果非常显著。
然而问题也出现了，如何把指数5变为原来的一半呢？由于指数不能是小数，所以不能简单地把5除以2。在这里要使用另外一种方法表示9^5:
先抽出9^1后,剩下的9^4就又可以进行减小指数的操作了。
9^5=(9^4)*(9^1)
9^5=(81^2)*(9^1)
9^5=(6561^1)*(9^1)
此时指数又变成了奇数的1，再次抽出6561^1，发现剩下的指数变成了0，无法再进行减小指数的操作了。所以，3^10最后的结果就是6561*9=59049。
由此可以发现，快速幂的结果实际上就是变化过程中所有指数为奇数的底数。
代码实现
接下来用代码演示一下上面的快速幂算法（结果对1000000007取模）：
long long quick_power(long long base,long long power){
long long result=1;
while(power>0){
if(power%2==1){//如果power是奇数，将指数为奇数的底数的一次方储存好
result=result*base%1e9+7;
}
//如果power是偶数，则直接进行“增底数”和”缩指数“
power=power>>=1;//等价于power=power/2,位运算的速度更快
base=(base*base)%1e9+7;
}
return result;
}
分析可得快速幂算法的时间复杂度为O(log n)。 经过测试，同样是求2^1000000000,快速幂算法只运行了接近0秒的时间，比需要运行大约18秒的普通幂算法要高效许多。
三、逆元
模运算的运算法则与四则运算有些类似，但是除法除外:
1.(a+b)%p=(a%p+b%p)%p
2.(a-b)%p=(a%p-b%p)%p
3.(a*b)%p=((a%p)*(b%p))%p
4.(a^b)%p=((a%p)^b)%p
因此在数论中，(a/b)%p计算很不方便。所以我们要引入逆元将整除运算转化为整数乘法运算。
逆元的定义如下：
欧几里得扩展原理求逆元
扩展欧几里得算法是求ax+by=GCD(a,b)的一组可行解：
设ax+by=GCD(a,b)的一组整数解为x=x1,y=y1；bx+(a%b)y=GCD(b,a mod b)的一组整数解为
x=x2,y=y2。
由欧几里得算法知GCD(a,b)=GCD(b,a mod b)，所以
ax1+by1=bx2+(a%b)y2
因为a mod b=a-[a/b]*b
所以ax1+by1=bx2+(a-[a/b]*b)y2
展开移项得ax1+by1=ay2+b(x2-[a/b]*y2)
根据对应系数可得
x1=y2
y1=x2-[a/b]*y2
因此若想求得ax+by=GCD(a,b)的解，可以转化为先求bx+(a mod b)y=GCD(b,a mod b)。我们发现这两个方程未知数的系数具有“辗转相除”的关系。根据欧几里得算法不断递归后，最终只需要求GCD(a,b)x+0y=GCD(a',b')的解（其中b'为0）。递归终点的解为x=1,y=0，再层层回溯就可以得到ax+by=GCD(a,b)的一组可行解。
a关于模b的逆元整数x满足ax mod b=1，且a与b互质（即GCD(a,b)=1）。因此只需要利用欧几里得扩展原理求解二元一次方程ax+by=1中的x，即为a关于模b的逆元。
扩展欧几里得算法模板
long long Ex_Gcd(long long a,long long b,long long &x,long long &y){
if(b==0){
x=1;y=0;
return a;
}
long long d = Ex_Gcd(b, a % b, x, y);
long long temp=x;
x=y;
y=temp-a/b*y;
return d;
}
long long Ex_Gcd_Inv(long long a,long long b){
long long x,y;
Ex_Gcd(a,b,x,y);
return x;
}
欧几里得扩展定理求逆元是最常用、最安全的求逆元方式，只要逆元存在就可以使用。适用于个数不多但模数很大的情况。
费马小定理求逆元
费马小定理：对于整数a与质数b，若a与b互质，则有：
a^b-1 mod b=1
所以
a*a^b-2 mod b=1
显然，a^b-2就是a模b的逆元。所以我们可以用前面的快速幂算法直接求出逆元
long long Ex_Gcd_Inv(long long a,long long b){
return quick_power(a,b-2);//这里省略快速幂函数
}
适用范围：由费马小定理的条件可知，这种求逆元的方法只适用于模数为质数的情况。
下面来看一道需要求逆元的题目：
暑期训练营第四周F题 异或和
题目大意
有一个n*m的网格图，给出小B出现在每个位置的可能性，用一个n*m的01矩阵表示，小B等概率出现在所有1的位置。求小A在每个位置上与小B期望曼哈顿距离的异或和，先把期望取模之后再异或。
输入描述:
第一行读入两个整数 n,m (n,m <= 2000) 接下来n行，每行读入一个长度为m的01字符串。
输出描述:
输出一个整数表示答案模 1e9+7。
思路：
曼哈顿距离（Manhattan distance）又称为城市街区距离或L1距离，是两点在南北方向和东西方向上的距离之和。
对于二维平面上的两个点A(x1, y1)和B(x2, y2)，它们的曼哈顿距离可以表示为：
d = |x1 - x2| + |y1 - y2|
一个点到另外一个点的曼哈顿距离可以分解为x和y方向上的分量：同一行的所有点到另一点的曼哈顿距离在x方向上的分量相同，同一列的所有点到另一点的曼哈顿距离在y方向上的分量相同。
所以我们先枚举遍历每一行和每一列，分别统计其在x方向和y方向上的曼哈顿距离的分量。对于点(i,j)，其曼哈顿距离的期望值等于第i行的x分量与第j列的y分量之和。
计算期望时要注意对分母使用逆元。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll mat[2004][2004];ll x[2004],y[2004];
ll c[2004];ll r[2004];//c为列，r为行
ll qpow(ll b,ll p){
ll res=1;
while(p>0){
if(p&1) res=res*b%mod;
p>>=1;
b=b*b%mod;
}
return res;
}
void solve(){
int n,m;
cin>>n>>m;//n行m列的矩阵
ll deno=0;//分母
for(int i=1;i<=n;i++){
string str;
cin>>str;
for(int j=1;j<=m;j++){
mat[i][j]=str[j-1];//记录矩阵
if(mat[i][j]=='1'){
deno++;//记录分母
r[i]++;//记录行值
c[j]++;//记录列值
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
x[i]+=r[j]*abs(i-j);//遍历每一行，记录在x方向上的分量
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++){
y[i]+=c[j]*abs(i-j);//遍历每一列，记录在y方向上的分量
}
ll res=0;
ll ny=qpow(deno,mod-2);//费马小定理求分母的逆元
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ll mem=(x[i]+y[j])%mod;
res ^= mem * ny % mod;//求异或和
}
cout<<res<<endl;
}
signed main(){
solve();
return 0;
}
时间复杂度为O(n^2)+O(m^2)+O(n*m)
滑动窗口算法
滑动窗口算法是在给定特定大小窗口的数组或字符串上执行要求的操作，该算法可以将一部分问题中的嵌套循环转化为一个单循环，以减少时间复杂度。
核心思路
滑动窗口算法类似于双指针，形成的关键在于两个指针如何移动。
1.首先初始化左右指针left，right=0，初始窗口为[left,right]。此时窗口内没有任何元素。 2.接着通过循环遍历数组中的元素，判断当前的右指针是否超过整个数组的长度。若超过则退出循环，否则执行下一步。 3.右指针每次向右移动一个长度，并对窗口区间内的数据进行更新。 4.当窗口区间内的数据满足要求时，固定右指针，开始移动左指针。直到窗口区间内的数据不再满足要求时，左指针停止移动。 5.继续执行第2步。
其中，窗口的更新和维护是很重要的一个步骤。每次新元素加入窗口以及旧元素移出窗口，都需要及时更新窗口范围内的相关数据。
滑动窗口算法的代码框架如下：
int left=0,right=0;
while(right<=arr.size()){//右指针未越界
right++;
char ch=arr[right];//右指针移动
...
//窗口数据满足条件 对于固定大小的窗口，就是窗口的大小>=固定值；
//对于动态大小的窗口，就是右指针不断移动，直到第一次满足题意的位置。
while(窗口数据满足条件）{
//记录或更新全局数据
...
//固定右指针，左指针开始移动
left++;
char temp=arr[left];
...
}
//返回结果
...
}
（图片来自知乎 @惊鸿只为卿）
2023河南萌新联赛第（七）场K题 质量检测
题目描述较长，点击链接跳转：
思路
这是一道典型的滑动窗口模板题。由题意可知，滑动窗口大小为固定的M，每次在窗口内查找最小值。
先用一个数组储存N件产品的分数，再定义一个队列稍后用于储存产品编号。用右指针i遍历每一个产品编号，当队尾的编号对应的产品分数大于右指针对应的的产品分数，将队尾的编号弹出，然后将右指针的产品编号存入队尾；若队尾编号对应的产品分数不大于右指针对应的产品分数，则直接将右指针的产品编号存入队尾。
如果右指针大于等于窗口的大小M，对队首的编号（可以看作左指针）进行判断，如果队首的编号小于等于i-m（右指针与窗口大小的差值），则将左指针超出窗口范围，将队首元素弹出。
这样操作下来，留在队首的编号对应的产品就是当前窗口内分数最小的一个。
AC代码
#include<bits/stdc++.h>
using namespace std;
deque<int> q;
void solve()
{
int n,m;cin>>n>>m;
vector<int> a(n+1);
for(int i = 1;i <= n;i ++) cin>>a[i];
for(int i = 1;i <= n;i ++){
while(!q.empty() && a[q.back()] > a[i]) q.pop_back();
q.push_back(i);
if(i >= m){
while(!q.empty() && q.front() <= i - m) q.pop_front();
printf("%d\n",a[q.front()]);
}
}
return ;
}
signed main()
{
solve();
return 0;
}
时间复杂度为O(n)。
京公网安备 11010502036488号