LiaN

是一只废物捏

0%

【题解】基础算法汇总

发表于 更新于 分类于 本文字数： 18k 阅读时长 ≈ 16 分钟
  • 主要内容
    • 二分、前缀和、差分 、双指针、位运算、离散化、区间合并、归并排序

二分

22-03-10: 今天想起写个题,发现自己连二分都写得磕磕绊绊的,我焯, 是大煞笔

  • 确定一个左闭右闭区间[l,r]，使得目标值在区间里面

  • 找一个性质 ，满足两点

    • 性质 具有二段性（所有二分 都要成立
    • 答案 一定是二段性的分界点

首先通过题目背景和check(mid)函数的逻辑，如果if (check(mid))条件成立，判断答案在左区间还是右区间

  • 如果答案在左区间并且mid也可能是答案👉第一种
  • 如果答案在右区间并且mid也可能是答案👉第二种

🔴第一种：

  • 区间划分：[l, mid] + [mid+1, r]
1
2
3
4
5
6
while(l < r){
    int mid = l + r >>1;
    if(check(mid)) r = mid;
    else l = mid + 1;
}
return l;

🔴第二种：

  • 区间划分：[l, mid-1] + [mid, r]
1
2
3
4
5
6
while(l < r){
    int mid = l + r + 1 >>1;
    if(check(mid)) l = mid;
    else r = mid - 1;
}
return l;

  • 整数二分的总结

    y总说按这种写法可以完美避掉所有坑 //o//:

    首先通过题目背景和check(mid)函数的逻辑，判断答案落在左半区间还是右半区间。

    • 找一个区间[L,R]使得答案一定在该区间中
    • 找一个判断条件,使得该判断条件具有二段性,并且答案一定是该二段行的分界点
    • 分析中点M在该判断条件下是否成立,如果成立or不成立,考虑答案在哪个区间
    • 如果更新方式**R=Mid**,则**不用做任何处理**
    • 如果更新方式**L=Mid**,则需要在计算Mid时**先加上1**

  • 浮点二分，例如，AcWing 790. 求一个浮点数的三次方根 AcWing题库

    1
    2
    3
    4
    5
    6
    7
    double l=-10000,r=10000,mid=0;
    while(r-l>1e-8){
        mid=(l+r)/2;
        if(mid*mid*mid<n) l=mid;
        else r=mid;
    }
    printf("%.6f\n",r);

lower_bound() 和 upper_bound() 🔴

利用二分查找方法在一个排好序的数组中进行查找，$O(logn)$

lower_bound( begin, end, num)：

  • 从数组下标begin到下标end-1位置二分查找第一个大于或等于num的数字
  • 返回：该数字的地址，不存在则返回end。
  • 例如：int position=lower_bound(array,array+size,target)-array;

upper_bound( begin, end, num)：

  • 从数组下标begin到下标end-1位置二分查找第一个大于num的数字

  • 返回：该数字的地址，不存在则返回end。

lower_bound( begin, end, num, greater<type>() ):

  • 从数组下标begin到下标end-1位置二分查找第一个小于或等于num的数字
  • 例如：int position=lower_bound(array,array+size,target,greater<int>())-array;

upper_bound( begin, end, num, greater<type>() )

  • 从数组下标begin到下标end-1位置二分查找第一个小于num的数字

AcWing789 数的范围（模板题）

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

const int N=100005;
int n,q,a[N];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	
	while(q--){
		int k;scanf("%d",&k);
		int L=0,R=n-1;
		
		while(L<R){ // 找第一个≥k 的数 
			int mid=(L+R)>>1;
			if(a[mid]>=k) R=mid;
			else L=mid+1;  
		}
		//最终L==R,判断条件这里写RL都行 
		if(a[R]==k){
			cout<<R<<' ';
			R=n-1; 
			//找第一个≤k的数 
			while(L<R){
				int mid=(L+R+1)>>1;			
				if(a[mid]<=k) L=mid; //如果a[mid]≤k,说明 必然在[Mid,R]之间 
				else R= mid-1; //R往右挪,所以- 
			}
			cout<<L<<endl;  
		}else cout<<"-1 -1"<<endl;
	}
}

AcWing1227 分巧克力

题意

N个Hi乘Wi的方格组成的长方形，划分出K个大小相同且最大的正方形

思路

  • 一个HxW的长方形，分割成边长为x的正方形的块数：

  • 随着x的增大，分割出的块数 减小，故 一定存在当x增大到值时，分割出的块数==K； 故可以采用二分

代码

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

const int N=100005;
int n,k,a[N][3];
// check=true是满足条件的，从0到x之间的部分，所以后面写的是l=mid
bool check (int m){
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=(a[i][0]/m)*(a[i][1]/m);
	}
	if(sum>=k) return true;
	else return false;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
	int l=0,r=N;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	if(l==r) cout<<l<<endl;
}

AcWing730 机器人跳跃问题

730. 机器人跳跃问题 - AcWing题库

题意

N+1座建筑，第i座的高度H(i)，当在第k座时能量为E，跳到第k+1座后能量为E=2*E-H(k)；整个过程能力不能为负值，求最初能量最少是多少。

思路

  • 对于某些题目提到求“最值”的问题，可以首先往二分的角度想一想=V=
  • 设最初能量为e，随着e从小到大增加，一定能找到一个E，
    • 当初值＜E时，跳跃过程中存在能量值＜0 的情况；
    • 当初值=E时，刚好 不存在能力值小于0的情况；
    • 当初值＞E，同样也一定 不存在能力值＜0的情况，
    • 当在中间的某一时刻能量值≥1e5的话后面必然不会存在＜0的情况，防止爆掉int，所以这里要判断一下

代码

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

const int N=100005;
int n,a[N];

//check==true：初始值为m 不会存在小于0的情况 
bool check(int m){
	int e=m;
	for(int i=0;i<n;i++){
		e=e*2-a[i];
		if(e>N) return true;
		if(e<0) return false;
	}
	return true;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	int l=0,r=N;
	while(l<r){
		int mid=(l+r)>>1; //求满足条件的最小值 
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
}

AcWing1221 四平方和

1221. 四平方和 - AcWing题库

知识点

参考：AcWing 1221. 四平方和 + 自定义排序（重载<）+二分 - AcWing

结构体排序

  • 重载运算符

    1
    2
    3
    4
    //x：任意名字，node：结构体的名字
    bool operator<(const node &x) const{
        //排序规则
    }

    比如下面结构体中的s,c,d

    1
    2
    3
    4
    5
    bool operator<(const Sum &t) const{
        if(s!=t.s) return s<t.s;
        if(c!=t.c) return c<t.c;
        return d<t.d;
    }//先比较s，如果s不同，则s小的结构体小；如果s相同但c不同，则c较小的结构体小....

  • sort自定义排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct Sum{
        int s,c,d;
    }sum[2500010];
    bool cmp(Sum a,Sum b){//自定义函数排序,Sum是结构体名
        if(a.s==b.s) return a.c<b.c;
        if(a.c==b.c) return a.d<b.d;
        return a.s<b.s;
    }
    sort(a,a+n);//默认下标0~n-1升序
    sort(a+1,a+n+1);//默认下标1~n升序
    sort(a,a+n,greater<int>());//降序
    sort(a,a+n,cmp);//自定义函数排序,重写cmp

题意

把正整数n写成a,b,c,d这4个数平方和的形式，输出字典序最小的abcd升序排列

思路

  • 如果暴力的话
    • 直接枚举abc（但会爆掉
  • 考虑空间换时间
    • 最先想的是先枚举ab保存下来再枚举cd，发现这样的话大小顺序有问题；
    • 所以，先枚举cd，用结构体数组保存每一组s=c^2+d^2，c，d；升序排序
    • 再枚举ab，a和b从小到大枚举，对于每一对ab，通过计算t = n-a a-b b，然后再通过二分从结构体数组中找第一个满足条件且cd最小的数
  • 说明
    • 首先枚举一定能保证a＜=b，c＜=d
    • 是如何保证b＜=c的？
      • 假设存在答案a,b,c,d ，使得a＜b>c＜d；那么一定有 a×a+b×b>a×a+c×c，因此a,c应当比a,b先出现，枚举一定是先枚举出的ac而不是ab，与假设矛盾，故假设不成立（弄个例子画一下就理解了）

代码

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;

const int N=2500010;
int n;
int a,b,c,d,t;
struct Sum
{
    int s, c, d;
    bool operator< (const Sum &t)const
    {
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];

int main(){
	cin>>n;
	int cnt=0;
	for(c=0;c*c<=n;c++){
		for(d=c;d*d+c*c<=n;d++){
				sum[cnt++]={c*c+d*d,c,d};
		}
	}
	sort(sum,sum+cnt);
	for(a=0;a*a<=n;a++){
		for(b=a;a*a+b*b<=n;b++){
			t = n-a*a-b*b;
			int l=0,r = cnt-1;
			while(l<r){
				int mid=(l+r)>>1; //找满足性质的最小值
				if(sum[mid].s>=t) r=mid;
				else l=mid+1;
			}
			if(sum[l].s==t){
				printf("%d %d %d %d\n",a,b,sum[l].c,sum[l].d);
				return 0;
			}
		}
	}
}

前缀和

  • 只能处理静态数组：只能查询不能修改
  • 线状数组和树状数组可以修改

一维

Acwing795 前缀和（模板题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
//给一个整数序列，求第l到第r个数的和
const int N=100005;
int n,m,a[N],s[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	while(m--){
		int l,r; scanf("%d%d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);
	}
}

AcWing1230 K倍区间

1230. K倍区间 - AcWing题库

题意

给定一组数列，求有多少个子序列的和 是k的倍数

思路

  • 首先想到的是双重循环+前缀和，时间复杂度n²，但是10^10会爆
  • 然后考虑如何优化：
    • 假设用S[i]来表示前缀和数组，易知Ai到Aj的和为S[R]-S[L-1] (L-1<=R)
    • 关键：(S[R] - S[L-1])%k==0 等价于(S[R]%k == S[L-1]%k)
    • 所以可以考虑：
      • 遍历，对于一个当前时刻固定的R，计算该S[R]%k的值，看在该R之前的前缀和 有谁%k的值（即余数）与之相等
      • 若相等，答案个数+1；设cnt[i]表示余数为i的个数
      • 但是，并不是所有子序列都需要两个前缀和来获得，对于S[R]%k==0 的情况，它本身也满足条件，也该加进答案里面，所以这里一定要将cnt[0] = 1;
      • 数据范围大，求和可能会爆int，所以用long long

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=100005;
int n,k;
LL s[N],cnt[N];
/*
1 2 3 4 5  原数字 
1 3 6 10 15  前缀和数组 
1 1 0 0  1   模k=2以后的余数数组  cnt[i]余数=i的个数 
*/
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&s[i]);
	
	for(int i=1;i<=n;i++) s[i]+=s[i-1]; 
	
	LL ans=0; cnt[0]=1;
	for(int i=1;i<=n;i++){
		ans+=cnt[s[i]%k] ; //这里理解下：对于当前第i个前缀和，它的余数是t=s[i]%k,cnt[t]则表示，在第i个前缀和之前的 余数也==t的个数；最初i=1，对于余数＞0的cnt[i]个数为0，随着循环更新增加 
		cnt[s[i]%k]++;
	}
	cout<<ans<<endl;
}

二维

  • 前缀和矩阵的计算：

  • 利用前缀和矩阵计算某个子矩阵（左上角(x1,y1) 到右下角(x2,y2)的和：

AcWing796 子矩阵的和（模板题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
//给定矩阵，求(x1,y1)到(x2,y2)的子矩阵的和
const int N=1005;
int n,m,q,a[N][N],s[N][N];
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);  //前缀和矩阵
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	while(q--){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
	}
}

AcWing99 激光炸弹

题意

99. 激光炸弹 - AcWing题库

思路

  • 很明显是个二维前缀和的问题
  • 一些注意点（内存限制所以这道题看起来简单但是细节好多aaaa（预判一波或许隔段时间再做也会做错QAQ）
    • R的取值范围＞N的取值范围，当R超过N的取值范围，就相当于直接求矩阵的和
    • 因为题目取值范围从0开始，为了方便，让坐标都+1，避免考虑边界问题
    • 注意这道题的内存空间限制168M，所以只能开一个数组，5000*5000的数组已经占了95.36M
    • 遍历的不是原矩阵的每个点，而是用r*r的正方形去遍历，框住那些点
    • ……..

代码

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<bits/stdc++.h>
using namespace std;
const int N=5005; 
int n,r,s[N][N];
int main(){
	scanf("%d%d",&n,&r);
	r=min(5001,r); //这里只能是5001，因为正方形边长最大是5000，
	while(n--){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		x++,y++;  //使所有坐标从1开始，避免考虑边界问题 
		s[x][y]+=w;  //不同目标可以在同一个位置
	}
	for(int i=1;i<=5001;i++)
		for(int j=1;j<=5001;j++){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
		}
	int ans=0;
	for(int i=r;i<=5001;i++)
		for(int j=r;j<=5001;j++){
			int t=s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r];
			ans=max(ans,t);
		}
	cout<<ans<<endl;
}

差分

把原数组看称某个数组的前缀和，这个所谓的某个数组就是差分数组

一般使用场景：

给出 n 个数，再给出 m 个询问，每个询问给出 l，r，x，要求你在 l 到 r 上每一个值都加上 x，而只给你 O(n) 的时间范围

它是对一个区间的操作，并非单点修改or区间查询

数组下标一般从1 开始

1
2
3
4
5
6
7
比如给定数组a 1 2 3 4 5 
构造差分数组b 1 1 1 1 1 
（下标从1开始）要在a[2]到a[4]中加上2:变成1 4 5 6 5
    即对差分数组操作即可，
    对b[2]+=2；注意是b[2]不是b[1]
    然后对b[4+1]-=2；得到 1 3 1 1 -1；
    最后求差分数组的前缀和：1 4 5 6 5；

一维

AcWing797 差分（模板题）

  • 关于差分数组b的构造（代码18行），也可以写成insert(i,i,a[i])：可以把初始原数组a看成全0，那么差分数组b也是全0，给数组赋初值等效于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
#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int n,m;
int a[N],b[N];
//关键方法
void insert(int l,int r,int c){
	b[l]+=c;
	b[r+1]-=c;
}
int main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]-a[i-1];   //构造差分数组
	} 
	while(m--){
		int l,r,c;
		cin>>l>>r>>c;
		insert(l,r,c);
	}
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+b[i];
		cout<<a[i]<<' ';
	}
}

二维

AcWing798 差分矩阵（模板题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n,m,q;
int a[N][N],b[N][N];

void insert(int x1,int y1,int x2,int y2,int c){
	b[x1][y1]+=c;
	b[x2+1][y1]-=c;
	b[x1][y2+1]-=c;
	b[x2+1][y2+1]+=c;
}
int main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
//			b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; 
			insert(i,j,i,j,a[i][j]);
		}
	while(q--){
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		insert(x1,y1,x2,y2,c);	
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
			cout<<a[i][j]<<' ';
		}
		cout<<endl;
	}
}

双指针

在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法优化；注意分析哪个是快指针，哪个是慢指针

1
2
3
4
for(i=0,j=0;i<n;i++){
    while(j<x&&check(i,j)) j++;
    //每道题的具体逻辑
}
  • 核心思想：每个指针的移动次数不超过n，算法复杂度O(N)
  • 例如，分割每个单词abc def ghi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main(){
	char s[1000];
	gets(s);
	int n=strlen(s);
	for(int i=0;i<n;i++){
		int j=i;
		while(j<n&&s[j]!=' ')j++;
		for(int k=i;k<j;k++) cout<<s[k];
		cout<<endl;
		i=j;
	}
}

AcWing799 最长连续不重复子序列

题意

给定一个长度为 n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

思路

  • 例如对于1 4 2 3 2 5，初始i和j都指向1，j向右移动，同时用一个计数数组count[]记录ij指向的区间内的数字出现的次数
  • 当j移动到a[4]时，发现2出现了两次，所以此时i要向右移动到第一个2出现位置的右边；
  • 由于count[]记录了区间ij之间各个数字出现的次数，每当i向右移动，区间ij发生变化。
  • 比如当前i指向a[0]，接下来i打算右移，则a[0]不在ij区间内了，所以对应count数组中存放的该值的个数-1，当移动到第一个2时，同样-1，i后移，这时2的个数=1，那么刚好此时i指向的就是第一个2后面的第一个位置

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,ans;
int a[N],cnt[N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int j=0,i=0;j<n;j++){
		cnt[a[j]]++;
		while(cnt[a[j]]>1){
			cnt[a[i]]--;
			i++;
		}
		ans=max(ans,j-i+1);
	}
	cout<<ans<<endl;
}

AcWing800 数组元素的和

题意

两个升序数组，求a[i]+b[j]==x的坐标（i，j）

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x;
int a[N],b[N];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>x;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int j=0;j<m;j++) cin>>b[j];
	
	for(int i=0,j=m-1;i<n;i++){
		while(j>=0&&a[i]+b[j]>x) j--;
		if(a[i]+b[j]==x){
			cout<<i<<' '<<j;return 0;
		} 
	}
}

AcWing1238 日志统计

题意

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=1e5+10;
typedef pair<int,int>PII;
PII a[N];
bool st[N];
int cnt[N];
int n,d,k;
int main(){
	scanf("%d%d%d",&n,&d,&k);
	for(int i=0;i<n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	sort(a,a+n);
	//i遍历时间 
	for(int i=0,j=0;i<n;i++){
		cnt[a[i].y]++;
		while(a[i].x-a[j].x>=d){
			cnt[a[j].y]--;
			j++;
		}
		if(cnt[a[i].y]>=k) st[a[i].y]=true;
	}
	for(int i=1;i<N;i++){
		if(st[i]) cout<<i<<endl;
	}
}

AcWing1240 完全二叉树的权值

题意

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int w[N];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	LL maxx=LONG_MIN,ans=0;
	for(int d=1,i=1;i<=n;i=i*2,d++){
		LL s=0;
		for(int j=i;j<i+(1<<d-1)&&j<=n;j++)
			s+=w[j];
		if(s>maxx){
			maxx=s;
			ans=d;
		} 
		
	}
	cout<<ans<<endl;
}

位运算

n的二进制表示中第k位数字是啥

1
2
3
4
5
n = 15 = 二级制：1111
//先把n(十进制）的第k位(二进制）数字右移到最后一位 n>>k
//此时的最后一位是几：x&1
    
n>>k&1;

lowbit()树状数组的一个基本操作

  • 返回的是一个二进制，这个二进制是x二级制从右往左的第一个1及其后面的0
1
2
x = 1010;lowbit(x)=10;
x = 101000;lowbit(x)=1000;
  • 实现
1
2
3
int lowbit(x){
	return x&(-x);
}
  • 应用：可以统计x里面1的个数

AcWing801 二进制中1的个数

题意

给定一个数组，求每个数组元素的二进制表示中1的个数

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){
	return x&(-x);
}
/*
x=10101,lowbit(x)=1
x-lowbit(x)=10100,lowbit(x)=100
x-lowbit(x)=10000,lowbit(x)=10000
x-lowbit(x)=0;
*/
int main(){
	int n;cin>>n;
	while(n--){
		int x;cin>>x;
		int res=0;
		while(x){
			x-=lowbit(x);
			res++;
		}
		cout<<res<<endl;
	}
}

AcWing90 64位整数乘法

题意

求a*b mod c ;其中a，b<=1e18

思路

  • 直接算会long long

代码

离散化(整数)

  • 序列（值域）范围很大，但实际数的个数很少，（有些题目我们可能要以这些数为下标来做

    比如数的范围是０－１０＾９，但只有很少的数，比如２，４５４３，３２１３１２３.．．

  • 所以我们可能将这些数 映射到从0开始的连续自然数

  • 又举一个栗子，比如有序数组a[]={1,3,100,2000,500000}，我们可以把它映射到0 1 2 3 4

  • 离散化的本质就是映射，将间隔很大的点，映射到相邻的数组元素中，减少对空间的需求和计算量

  • 问题

    • a中可能有重复元素——去重
    • 如何算出a中某个值x 离散化后的值是多少——二分

去重代码

1
2
3
vector<int> alls;//存储所有待离散化的值（坐标）
sort(alls.begin(),alls,end()); //将所有值排序
alls.erase( unique(alls.begin(),alls.end()) , alls.end() ) //去掉重复元素

二分代码：求出坐标x对应的离散化后的值：即找到第一个＞=x的位置（坐标）

1
2
3
4
5
6
7
8
9
int find(int x){
    int l = 0,r = alls.size()-1;
    while(l < r){
        int mid = l+r>>1;
        if( alls[mid] >= x ) r = mid;
        else l = mid+1;
    }
    return r+1;//+1:映射到1到n；不加：0到n
}

AcWing802 区间和

题意

给定无限长的数轴，所有点初始（该坐标点上面的值）=0（其实数据范围规定从（即数轴坐标）-10^9-10^9)

n个操作，每次操作选择一个下标，把上面的数加上c

m次询问，区间lr之间的所有数的和

思路

参考题解

  • 如果数据范围比较小，就可以用前缀和

  • 但是数据范围跨度很大，而涉及到（所用到）数的个数很少，绝大部分坐标没有用到

  • 因为下标很大，且存在负值，直接开数组很不现实

  • 故：先离散化，把所有用到的下标把它们映射到从1开始（因为后面要用到前缀和计算区间和，所以从1开始）的自然数

  • 针对m次加法（涉及1个坐标）和n次查询（涉及2个坐标），n和m的数据范围在10^5以内，所以可能涉及到的最多的坐标个数为3*10^5；由此确定映射数组的大小—->所以先要把这些坐标都下来，离散化之后，根据对应操作进行处理

代码

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<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=3e5+10;

int n,m;
int a[N],s[N];
vector<int> alls;
//alls 存放原本的数轴上的坐标 
vector<PII>add,query;
//add 暂时存放加操作；query暂时存放查询操作 
int find(int x){
	int l=0,r=alls.size()-1;
	while(l<r){
		int mid=l+r>>1;
		if(alls[mid]>=x) r=mid;
		else l=mid+1;
	}
	return r+1;//将原坐标x映射到1-alls.size()的里面的某个坐标 
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	
	for(int i=0;i<n;i++){
		int x,c;
		cin>>x>>c;
		add.push_back({x,c});//存储加法操作 
		alls.push_back(x); //存储原坐标 
	}
	for(int i=0;i<m;i++){
		int l,r;
		cin>>l>>r;
		query.push_back({l,r}); //存储查询操作 
		alls.push_back(l);//存储原坐标 
		alls.push_back(r); //存储原坐标 
	}
	//在存储坐标时，可能会有重复的，所以首先去重：先排序 
	sort(alls.begin(),alls.end());
	//排完序后，unique把alls的无重复数字放在alls数组里的前面，
	//重复的放在数组里的后面，unique返回的是这个分界点的指针
	//erase去除重复的元素；最终可以确定实际操作的坐标的个数 
	alls.erase(unique(alls.begin(),alls.end()),alls.end());
	//对vector从头遍历（当然也可以用普通的for循环） 
	//加法： 
	for(auto item:add){
		int x=find(item.first);//将坐标进行映射 
		a[x]+=item.second;
	}
	for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
	
	for(auto item:query){
		int l=find(item.first),r=find(item.second);
		cout<<s[r]-s[l-1]<<endl;
	}
	return 0;
}

区间合并

AcWing803 区间合并

题意

给定多个区间，如果两个区间有交集的话，就把它合并成同一个区间；（合并所有有交集单点区间），端点相交也算；求合并完后区间的数量

思路

  • 所有区间按照左端点排序
  • 扫描过程中，将所有有交集的区间合并

代码

1

归并排序

分治：确定分界点mid=l+r>>1划分成两个子区间、递归排序左右、合并左右

归并排序是稳定的，时间复杂度nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,q[N],tmp[N];
//分界+递归+归并 
void merge_sort(int q[],int l,int r){
//	cout<<"in"<<endl;
	if(l>=r) return ;//结束状态
	int mid=l+r>>1;
	merge_sort(q,l,mid),merge_sort(q,mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j]) tmp[k++]=q[i++];
		else tmp[k++]=q[j++];
	}
	while(i<=mid) tmp[k++]=q[i++];
	while(j<=r) tmp[k++]=q[j++];
	//注意是把数组q的l到r排序，注意i的循环范围 
	for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];	
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&q[i]);
	merge_sort(q,0,n-1);
	for(int i=0;i<n;i++) printf("%d ",q[i]);
	return 0;
}

AcWing788 逆序对的数量

题意

求给定数组逆序对的数量，数组元素的取值[0,1e9]

思路

最先开始想的是用之前学过的树状数组做，确实，如果元素的取值范围没那么大的话是可以过的；

所以再复习了一遍归并排序的做法

将逆序对分为三大类：两个数同时出现再左半边；两个数同时出现再右半边；一个数在左，一个数在右

假设归并排序能将整个区间排好序并且返回每个区间内部逆序对的个数

因此所有逆序对的数目就是三类逆序对个数之和

对于一个在左，一个在右的这种情况：对于右半边的每个元素，去找左半边有多少个元素大于它

左右部分都排好序之后，在归并的时候，假设左半边指针i，右半边指针j；当i大于j的时候，对于在右半边j指向的元素x，在左半边就有mid-i+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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n;
int a[N],tmp[N];
LL merge_sort(int l,int r){
	if(l>=r) return 0;
	int mid=l+r>>1;
	LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
	//此时左右两边已经排好序 
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]) tmp[k++]=a[i++];
		else{
			tmp[k++]=a[j++];
			res+=mid-i+1;
		} 
	}
	while(i<=mid) tmp[k++]=a[i++];
	while(j<=r)tmp[k++]=a[j++];
	for(int i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];
	return res; 
	
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	cout<<merge_sort(0,n-1)<<endl;
}