蓝桥杯备战试题总结

2020-09-09

一、递归和递推

1. 递归实现指数型枚举

题意:给定一个整数 N,1-N 中每个数只能被选一次,输出所有的选择方案。

思路:利用二进制枚举的方式,位运算向右移动第 k 位即代表这个数被选择到。

#include<bits/stdc++.h>

using namespace std;

int n;

void dfs(int x,int state)
{
    //递归边界
    if(x==n) {
        for(int i=0;i<n;i++) {
            if(state>>i&1) cout<<i+1<<' ';
        }
        puts("");
        return ;
    }
  
    //若当前数不选
    dfs(x+1,state);
  
    //若选择了当前的数
    dfs(x+1,state|1<<x);
  
}

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

2.递归实现组合型枚举

题意:把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。

思路:建立一个 vector,用来存储答案,每次递归的时候标记掉当前数,是否被用过,回溯的时候回溯现场即可实现对所有的情况的遍历。其实是个简单题,但是我记得曾经写过这样的题,要注意高复杂度的情况。

#include<bits/stdc++.h>

using namespace std;

int n;
int path[30];
int vis[30];

void dfs(int idx)
{
    //递归边界
	if(idx==n) {
		for(int i=0;i<n;i++) cout<<path[i]<<' ';
		cout<<'\n';
		return ; 
	}

	//向下递归搜索
	for(int i=1;i<=n;i++) 
	{
		if(!vis[i])  {
			path[idx]=i;
			vis[i]=1;
			dfs(idx+1);
			//恢复现场
			vis[i]=0;
		}
	}
}

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

2、简单的递推,经典的有斐波那契数列和数字三角形,以及杨辉三角,杨辉三角延伸出来的又有递推求组合数

题意:输出斐波那契数列的前 n 项的值。

#include<bits/stdc++.h>

using namespace std;

const int N=100;

typedef long long LL;

LL f[N];

int main()
{
    int n;
    cin>>n;
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=n;i++)
        f[i]=f[i-1]+f[i-2];
  
    for(int i=0;i<n;i++)
        cout<<f[i]<<' ';
    puts("");
  
    return 0;
}

二、二分和前缀和

例 1、数的范围

题意 给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回“-1 -1''


三、数学与简单 DP

四、枚举、模拟、与排序

五、树状数组与线段树

树状数组 本质上:单点修改、区间查询

image.png

image.png

树状数组例题:

1264. 动态求连续区间和

  1. 给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 [a,b]的连续和。

输入格式

第一行包含两个整数 n 和 m,分别表示数的个数和操作次数。

第二行包含 n 个整数,表示完整数列。

接下来 m 行,每行包含三个整数 k,a,b(k=0 表示求子数列[a,b]的和;k=1 表示第 a 个数加 b)。

数列从 1 开始计数。

输出格式

输出若干行数字,表示 k=0 时,对应的子数列 [a,b]的连续和。

数据范围

1≤n≤100000,1≤n≤100000,
1≤m≤100000,1≤m≤100000,
1≤a≤b≤n,1≤a≤b≤n

输入样例:

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

输出样例:

11
30
35

思路:

给定 n 个数,对每个数可以执行加上某个数,或者改变成某个数的话就相当于加上与原数的差值,做法是先初始化 C 数组,直接对于每个位置 i 加上 a[i]即可,add 函数是通过 i~i+lowbit(i)<=n 之间的数加上的,询问的时候也是从 1~~i 之间的数的和

代码:

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int c[N];
int a[N];

int lowbit(int x) {
	return x&(-x);
}

void add(int x,int v) {
	for(int i=x;i<N;i+=lowbit(i))
		c[i]+=v;
}

int sum(int x) {
	int res=0;
	for(int i=x;i;i-=lowbit(i))
		res+=c[i];
	
	return res;
}

int main()
{
	int  n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		add(i,a[i]);
	
	while(m--) {
		int k,a,b;
		cin>>k>>a>>b;
		if(!k) {
			cout<<sum(b)-sum(a-1)<<'\n';
		}
		else {
			add(a,b);
		}
	}
	return 0;
 }

2、1215. 小朋友排队

n 个小朋友站成一排。

现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。

开始的时候,所有小朋友的不高兴程度都是 0。

如果某个小朋友第一次被要求交换,则他的不高兴程度增加 1,如果第二次要求他交换,则他的不高兴程度增加 2(即不高兴程度为 3),依次类推。当要求某个小朋友第 k 次交换时,他的不高兴程度增加 k。

请问,要让所有小朋友按从低到高排队,他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数 n,表示小朋友的个数。

第二行包含 nn 个整数 H1,H2,…,Hn 分别表示每个小朋友的身高。

输出格式

输出一行,包含一个整数,表示小朋友的不高兴程度和的最小值。

数据范围

1≤n≤100000,1≤n≤100000,
0≤Hi≤10000000,≤Hi≤1000000

输入样例:

3
3 2 1

输出样例:

9

样例解释

首先交换身高为 3 和 2 的小朋友,再交换身高为 3 和 1 的小朋友,再交换身高为 2 和 1 的小朋友,每个小朋友的不高兴程度都是 3,总和为 9。

思路:

1、看数据范围就知道肯定是预处理出来某些东西因为不可能是暴力双 for 去求解的,通过推理可得到每个小朋友的不开心度就是左边比其大的数 + 右边比起小的个数,而要线性得到比某个数大的数或者比某个数小的数有多少个或者判定一个数是否出现过可以通过树状数组的形式,在第 i 个位置上加 1 即可或者让这个位置变成 1,加上 1 可以用来统计个数,变成 1 可以用来标记是否出现过 1,这也让我想起来了之前 cf 有道题大佬告诉我可以用树状数组标记某些数是否出现过,进行线性求解
比如从 1 到 n 对于第 i 个数为 a[i],要判断 i 之前是否有小于或者大于 a[i]的出现过,可以通过将前面的 a[j]均标记为 1,在求的时候直接算 sum(a[i]-1)即为小于 a[i]的数有多少个,而 sum(N)-sum(a[i])就为大于 a[i]的数有多少个 2333

2、通过逆序对数量来计算答案 逆序对->Ai>Aj&&i<j

代码:

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10,M=2e6+10;

typedef long long LL;

LL a[N];
LL tr[M];
LL ans[N];

int lowbit(int x) {
	return x&(-x);
}

void add(int x,int v) {
	for(int i=x;i<M;i+=lowbit(i))
		tr[i]+=v;
}

LL sum(int x) {
	LL res=0;
	for(int i=x;i;i-=lowbit(i)) {
		res+=tr[i];
	}
	return res;
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		a[i]++;
	}

	//统计左边比起大的个数
	for(int i=1;i<=n;i++) {
		LL x=sum(a[i]);
		LL y=sum(M);
		ans[i]+=y-x;
		add(a[i],1);
	} 
	//统计右边比起小的个数
	memset(tr,0,sizeof tr);
	for(int i=n;i>=1;i--) {
		LL x=sum(a[i]-1);
		ans[i]+=x;
		add(a[i],1);
	}

	long long int cnt=0;
	for(int i=1;i<=n;i++) {
		cnt+=(1LL*ans[i]*(ans[i]+1))/2;
	}
   	cout<<cnt<<'\n';
	return 0;
}

线段树

例 1、1228 油漆面积

X 星球的一批考古机器人正在一片废墟上考古。

该区域的地面坚硬如石、平整如镜。

管理人员为方便,建立了标准的直角坐标系。

每个机器人都各有特长、身怀绝技。

它们感兴趣的内容也不相同。

经过各种测量,每个机器人都会报告一个或多个矩形区域,作为优先考古的区域。

矩形的表示格式为 (x1,y1,x2,y2)代表矩形的两个对角点坐标。

为了醒目,总部要求对所有机器人选中的矩形区域涂黄色油漆。

小明并不需要当油漆工,只是他需要计算一下,一共要耗费多少油漆。

其实这也不难,只要算出所有矩形覆盖的区域一共有多大面积就可以了。

注意,各个矩形间可能重叠。

输入格式

第一行,一个整数 n,表示有多少个矩形。

接下来的 n 行,每行有 4 个整数 x1,y1,x2,y2 空格分开,表示矩形的两个对角顶点坐标。

输出格式

一行一个整数,表示矩形覆盖的总面积。

数据范围

1≤n≤10000,1≤n≤10000,
0≤x1,x2,y2,y2≤10000,0≤x1,x2,y2,y2≤10000
数据保证 x1<x2,x1<x2 且 y1<y2,y1<y2。

输入样例 1:

3
1 5 10 10
3 1 20 20
2 7 15 17

输出样例 1:

340

输入样例 2:

3
5 2 10 6
2 7 12 10
8 1 15 15

输出样例 2:

128
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e4+10;

struct Node {
	int x1,y1,y2;
	int op;
	bool operator<(const Node &W) const{
		return x1<W.x1;
	} 
}seg[N];

struct node{
	int l,r;
	int cnt;//当前区间被覆盖的个数
	int len;//l到r之间至少被覆盖一次的区间总长度	
}tree[N*4];

void pushup(int u)
{
	if(tree[u].cnt>0) tree[u].len=(tree[u].r-tree[u].l+1);
	else if(tree[u].l==tree[u].r) tree[u].len=0;
	else tree[u].len=tree[u<<1].len+tree[u<<1|1].len;
}

void build(int u,int l,int r) {
	tree[u]={l,r};
	//递归到叶子节点 
	if(l==r) {
		//这是全局变量可不用更新 
		tree[u].cnt=tree[u].len=0;
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	//全为0也可以不用更新 
	//pushup(u); 
}

void modify(int u,int l,int r,int d)
{
	if(tree[u].l>=l&&tree[u].r<=r) {
		tree[u].cnt+=d;
		pushup(u);
		//这个地方别忘记更新了 
		return ;
	}
	int mid=tree[u].l+tree[u].r>>1;
	if(l<=mid) modify(u<<1,l,r,d);
	if(r>mid) modify(u<<1|1,l,r,d);
	//当修改操作发生在区间的时候肯定是递归找到了完全包含的区间
	//回溯的时候需要用子节点的信息更新父节点 
	pushup(u);
}

int main()
{
	int n;
	cin>>n;
	int m=0;
	for(int i=1;i<=n;i++) {
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		seg[m++]={x1,y1,y2,1};
		seg[m++]={x2,y1,y2,-1};
	}
	
	//按x坐标排序
	sort(seg,seg+m); 
	
	//按照y坐标建树	
	build(1,0,10000);
	LL res=0;
	for(int i=0;i<m;i++) {
		if(i) {
			res+=(LL)tree[1].len*(seg[i].x1-seg[i-1].x1);
		}
		//区间更新和,区间下标比点下标少1 
		modify(1,seg[i].y1,seg[i].y2-1,seg[i].op);
	}
	cout<<res<<'\n';
	return 0;
}

六、双指针、BFS 与图论

七、贪心

八、数论

九、复杂 DP

其他综合


标题:蓝桥杯备战试题总结
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/09/09/1599614617773.html