(蓝桥杯C/C++）——基础算法(上）

一、二分法

1.二分法简介

二分法简介-解题步骤

2.整数二分-简介

整数二分-模板

3.浮点二分-简介

浮点二分-模板

4.二分答案-简介

二分答案-模板

二、位运算

1.位运算简介

2.常见的位运算

按位与AND(&)

按位或OR( | )

按位异或XOR(^)

按位取反(~)

按位左移(<<)

按位右移(>>)

3.位运算技巧

1.判断数字奇偶性

2.取二进制数的某一位

3.修改二进制中的某一位为1

4.快速判断一个数字是否为2的幂次方

5.获取二进制位中最低位的1

三、贪心算法

1.贪心算法介绍

2.贪心算法实现步骤

3.常见贪心模型和例题

四、模拟算法

1.模拟算法介绍

2.例题讲解

五、双指针

1.双指针介绍

2.对撞指针

3.快慢指针

六、构造

1.构造介绍

2.构造题目的特点

3.构造的应用场景

4.构造例题解析

七、进制的转换

1.进制的本质

2.将任意进制转换为十进制

3.将十进制转换为任意进制

一、二分法

1.二分法简介

二分法是一种高效的查找方法，它通过将问题的搜索范围一分为二(两边具有明显的区别)，迭代地缩小搜索范围，直到找到目标或确定目标不存在。
分法适用于有序数据集合，并且每次迭代可以将搜索范围缩小一半。
分法本质上也是枚举，但和暴力枚举不同，二分法利用数据结构的单调性减少了很多不必要的枚举，从而极大地提高了效率，一般可以将O(n)的枚举优化到O(logn)。

常见的二分类型有:

(1)整数二分
(2)浮点二分
(3)二分答案(最常见)

二分法简介-解题步骤

1.研究并发现数据结构(或答案变量)的单调性。

2.确定最大区间[L,R]，确保分界点一定在里面，具体有一些细节:若以r作为答案，那么答案区间在[L+1,R]，若以L作为答案，那么答案区问在[L,R-1]。

3.确定check函数，一般为传入mid(区间中某个下标)，返回mid所属区域或返回一个值，当check函数较简单时可以直接判断。

4.计算中点mid =(L+R)/2，用check判断该移动L或R指针，具体移动哪个需要根据单调以及要求的答案来判断。

5.返回L或R，根据题意判断。

2.整数二分-简介

整数二分就是在一个有的有序数组上，进行二分查找，一般为找出某个值的位置)或者是找出分界点。

这个数组肯定是开的下的，其数组大小一般在1e6（1e6 = 1000000）以内。

区域划分如下图。

找第一个>=6的，即6的左边界，返回right

2	4	4	6	6	10	18
a1	a2	a3	a4	a5	a6	a7
		↑ left	↑ right

找最后一个<=6的，即6的右边界，返回right

2	4	4	6	6	10	18
a1	a2	a3	a4	a5	a6	a7
				↑ left	↑ right

整数二分-模板

找到升序数组a中的x第一次出现的位置

int L=0,R=1e9;

//注意这里的判断条件，这样可以保证L，L最终一定收敛到分界点代码如下（示例）：

while(L + 1 != r) //L和R相邻时推出

{
int mid =(L + R) / 2;

//如果a为升序，说明mid偏大了，需要减小mid，就只能将r变小，即r = mid

if (a[mid] >= x)

R = mid //保持在所属区域

else L = mid;

}
cout << r << '\n'；

3.浮点二分-简介

浮点二分不再是在有序数组上做二分查找，而是在某个实数范围内进行查找，因为实数域本身是单调的，所以也满足单调性，和整数二分的主要区别在于使用的变量类型、退出的判断条件不同。

浮点二分-模板

eps是一个非常小的浮点数，用于处理浮点数比较时的误差或精度问题。

//计算单调函数f(x)的零点

double L = 0; R = 1e9, eps = 1e-6

//注意这里的判断条件，r最终一定收敛到分界点

while(R-1>= eps) //eps足一个极小量，设置为1e-6较合适

{

double mid = (1+R) / 2;

//f(x)单调递增，f (mid) >= 0，说明mid偏大了，需要减小mid，就只能将R变小，即r=mid

if (f (mid) >= 0)

R = mid;

else L = mid;

}
//最后返回L，R差别不大

cout << R << '\n';

4.二分答案-简介

二分答案是二分法中最常见也最重要的题型，考察的比较灵活，需要选手从题目中发现某个单调的函数，然后对其进行二分。

常见的模型是:
二分框架(时间复杂度O(logm)) + check兩数(时间复杂度O(n))

一般情况下，我们会将答案进行二分，然后在举出某个可能解后判断其是否可以更优或是否合法，从而不断逼近最优解。
二分答案的题的特征:如果已知某个答案，很容易判断其是否合法或更优。某些贪心问题可能可以转化成二分答案问题。

二分答案-模板

bool check(int mid)

{

bool res = true;
//do somtnin to check the authority of mid ...

return res;
}

int main()
{

int L = 0; R = 1e9;

while(1 + L !=R)

{
int mid = (L + R）/ 2;

//具体写法需要根据题意修改

if (check (mid)) L = mid;

else R= mid;

}
cout<< L <<'\n';//具体输出的内容需要根据题意判断

}

二、位运算

位运算是一种对二进制数的位进行操作的运算方式。
它直接对二进制数的每一位进行逻辑操作，而不考虑整个数的数值大小，一般情况下，位运算中每一位都相互独立，各自运算得出结果(左右移除外)在计算机科学和编程中，位运算常用于优化算法、位掩码操作、位字段处理等领域。
在竞赛中，位运算经常考察异或的性质、状态压缩、与位运算有关的特殊数据结构、构造题等。

注意:位运算只能应用于整数，且一般为非负整数，不能应用于字符、浮点等类型

1.位运算简介

在计算机中，整数是通过补码表示的，但是一般情况下，我们对负数进行位运算意义不大，99%情况下都是对正整数进行处理，而正数的原码=补码，所以我们直接考虑二进制数的原码，也就是直接地表示二进制数。

例如整数10，在计算机中存储如下(按照书写习惯，一般认为右边为低位，在左右移时尤为重要):

val	0	0	0	0	...	1	0	1	0
idx	31	30	29	28	...	3	2	1	0
int 32位

2.常见的位运算

按位与AND(&)

按位与运算符(&)用于对两个操作数的对应位进行逻辑与操作。它的运算规则是，只有当两个位都为1时，结果位才为1，否则为0。两个数字做与运算，结果不会变大。

同一为一，有零为零

x	y	x&y
0	0	0
0	1	0
1	0	0
1	1	1

按位或OR( | )

按位或运算符(1)用于对两个操作数的对应位进行逻辑或操作。
它的运算规则是，只要两个位中有一个为1，结果位就为1，否则为0。
两个数字做或运算，结果不会变小。

同零为零，有一为一

x	y	x\|y
0	0	0
0	1	1
1	0	1
1	1	1

按位异或XOR(^)

按位异或运算符(^)用于对两个操作数的对应位进行逻辑异或操作。
它的运算规则是，当两个位不同时，结果位为1，否则为0。
两个数字做异或运算，结果可能变大也可能变小，也可能不变。

x	y	x^y
0	0	0
0	1	1
1	0	1
1	1	0

按位取反(~)

用于对操作数的每一位进行取反操作，即将0变为1，将1变为0。按位取反操作通常用于无符号整数(unsigned int/longlong)，这是为了避免符号位取反造成千扰。

x	~x
0	1
1	0

按位左移(<<)

左移(<<)操作将一个数的二进制表示向左移动指定的位数。

移动后，低位补0，如果数据类型为有符号整型，注意移动的时候不要移动到符号位上，或者干脆使用无符号整型。1会移动到符号位上。

左移操作相当于对原数进行乘以2的幂次方的操作。

例如，对于整数5(二进制表示为00000101)执行左移3位操作，相当于执行5*(2^3)。

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

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

按位右移(>>)

左移(>>)操作将一个数的二进制表示向右移动指定的位数。

移动后，一般情况高位补0，如果数据类型为有符号整型，注意移动的时候让符号位为0，或者干脆使用无符号整型。如果符号位上有1不会被移走，这是负数位移的规则。

右移操作相当于对原数进行除以2的幂次方的操作例如，对于整数13(二进制表示为00001101)执行左移2位操作，相当于执行13/4向下取整，

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

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

3.位运算技巧

1.判断数字奇偶性

公式:x&1

如果结果为1说明是奇数，结果为0说明是偶数。

2.取二进制数的某一位

公式:x>>i&1

结果必然为0或1，表示x的二进制表示中的第i位。

3.修改二进制中的某一位为1

公式:x|(1<<i)

将x的第i位或上1，则x[]变为1，其他位上或上0没有影响。

修改为0就类似地用与运算即可，就是构造出只有第i位为0，其他位都为1的一个二进制数然后和x做与运算。

4.快速判断一个数字是否为2的幂次方

公式:x &(x-1)

如果x为2的幂次方，则x的二进制表示中只有一个1，x-1就有很多个连续的1并且和x的1没有交集，两者与运算一定为0，可以证明其他情况必然不为0。

5.获取二进制位中最低位的1

公式:lowbit(x)=x&-x

如果x=(010010)，则lowbit(x)=(000010)。
常用于数据结构树状数组中。

三、贪心算法

1.贪心算法介绍

学习目标:
1.理解贪心算法的基本概念和原理。
2.掌握贪心算法的基本思想和解题思路。
3.理解常见贪心模型，并能够分析并解决简单的贪心问题。

贪心的基本原理:每一步都选择局部最优解，而尽量不考虑对后续的影响，最终达到全局最优解。

贪心的局限性:贪心算法不能保证获得全局最优解，但在某些问题上具有高效性。

贪心的特征:贪心选择性质、最优子结构性质(根据我的观察，很多贪心的题目会出现“不同的操作产生的贡献相同”的特征，在此特征下我们每次选择代价最小的)。

贪心的类型多且杂，难以划分，需要不断练习和积累。

2.贪心算法实现步骤

1.确定问题的最优子结构(贪心往往和排序、优先队列等一起出现)。
2.构建贪心选择的策略，可能通过“分类讨论”、“最小代价”、“最大价值”等方式来思考贪心策略。简单验证贪心的正确性，采用句式一般是:这样做一定不会使得结果变差、不存在比当前方案更好的方案等等。
3.通过贪心选择逐步求解问题，直到得到最终解。

3.常见贪心模型和例题

最近同学们表现出色，他们的老师决定给他们分发糖果，肖思购买了几个不同种类的糖果，用小写的阿拉怕字母表示，每个糖果须分发给一个同学，并且每个同学至少要分到一个糖果，同学们的开心程度定义为他们所分到的糖果组成的字特串 s[i] 的字典序，恩希望同学们的开心程度相差尺量小，因此他要找到一种方客，使得所有糖果组成的字特串中字曲序最大的字符电尽可能小。请输出能够实现字典序最小可能的max(s|1|, s(2], s[3].…s|z])

#Include <bits/stac++.h>

using namespace std;
const int N = 1e6 +9;
char s[N];
int = main()

{
int n, x; cin >> n >> x;

cin > s+1;

sort (s+1，s+1+n);
if(s[1] == s[n])

{

for(int i = 1; i <= n / x + (n % x ? 1 :0); ++i)

cout << s[1];

}

else if(s[1] == s[n])

{
for(int i = x ; i <= m ; ++ i)

cout << s[i];

}

else

cout << s[x];

return 0;

}

四、模拟算法

1.模拟算法介绍

模拟算法通过模拟实际情况来解决问题，一般容易理解但是实现起来比较复杂，有很多需要注意的细节，或者是一些所谓很“麻烦”的东西。模拟题一般不涉及太难的算法，一般就是由较多的简单但是不好处理的部分组成的，考察选手的细心程度和整体的逻辑思维。一般为了使得模拟题写的逻辑清晰一些，经常会写比较多的小函数来帮助解题，例如int和string的相互转换、回文串的判断、日期的转换、各种特殊条件的判断等等。

2.例题讲解

2020 年春节期间，有一个特殊的日期引起了大家的注意:2020年2月2日。因为如果将这个日期按yyyymmdd" 的格式写成一个8位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期,
有人表示 20200202 是“千年一遇”的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期:20211202即2021年12月2日。
也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个ABABBABA型的回文日期:21211212即 2121年12月 12日。算不上“千年遇”，顶多算“千年两遇”
给定一个8位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

#include <iostream>
using namespace std;

bool isLeap(int y){
return (y%4==0&&y%100!=0)||(y%400==0);
}

bool check(int year,int month,int day){//判断是否为合法日期
if(month>12||month==0) return false;
if(day>31) return false;
if(month==2){
if(isLeap(year)&&day>29)
return false;
if(!isLeap(year)&&day>28)
return false;
}
if(month==4||month==6||month==9||month==11){
if(day>30) return false;
}
return true;
}
int main()
{
int n,i;
cin>>n;
int a,b,c,d,e,f,g,h;//8位数字
int year,month,day;
bool flag=false;
for(i=n+1;i<=99999999;i++){
year=i/10000;
month=(i%10000)/100;
day=i%100;
a=i%10;
b=(i/10)%10;
c=(i/100)%10;
d=(i/1000)%10;
e=(i/10000)%10;
f=(i/100000)%10;
g=(i/1000000)%10;
h=(i/10000000)%10;
if(a==h&&b==g&&c==f&&d==e&&flag==false){
if(check(year,month,day)){
cout<<i<<endl;
flag=true;//只输出一个回文
}
}
if(a==h&&b==g&&c==f&&d==e&&a==c&&b==d){
if(check(year,month,day)){
cout<<i<<endl;
break;
}
}

}
return 0;

五、双指针

1.双指针介绍

双指针算法是一种常用的算法技巧，它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。
双指针并非真的用指针实现，一般用两个变量来表示下标(在后面都用指针来表示)。双指针算法使用两个指针在数据结构上进行选代，并根据问题的要求移动这些指针。双指针往往也和单调性、排序联系在一起，在数组的区间问题上，暴力法的时间复杂度往往是O(n^2)的，但双指针利用“单调性”可以优化到O(n)。

常见的双指针模型有:
(1)对撞指针
(2)快慢指针

2.对撞指针

指的是两个指针 left、right(简写为1,r)分别指向序列第一个元素和最后一个元素。然后1指针不断递增，r不断递减，直到两个指针的值相撞或错开(即1>=r)，或者满足其他要求的特殊条件为止。
对撞指针一般用来解决有序数组或者字符串问题(常见于区间问题):
查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题
字符串反转问题:反转字符串、回文数、颠倒二进制等问题。

对撞指针——求解步骤

1.使用两个指针 left,right。left 指向序列第一个元素，即:left=1，right 指向序列最后-个元素，即:right=n。

2.在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left++。当满足另外一定条件时，将右指针左移，right--
3.直到两指针相撞(即left==right)，或者满足其他要求的特殊条件时，跳出循环

a1	a2	a3	a4	a5	a6	a7
left↑→ ←↑right

对撞指针例题

题目描述
给定一个长度为 n的字符串 S、请你判断字符串 S是否回文

回文判定

对撞指针，每次判断s[1]和s[r]是否相等，如果相等就都移动一步，否则直接判断为“不是回文串”

#include <iostream>

using namespeace std;

const int N = 1e6 + 9;
char s[N];

int main()

{

ios::sync_with_stdio(o),cin.tie(o),cout.tie(o);

cin >> s + 1;

int n = strlen(s + 1);

int l = 11, r = n;

bool ans = trun;

while(l < r && ans)

{

if (s[l] != s[r] ans = false;

l ++, r++;

}

cout << (ans ? "Y" : "N") <<'\n';

return 0;

}

3.快慢指针

快慢指针一般比对撞指针更难想，也更难写，
指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢，
移动快的指针被称为快指针，移动慢的指针被称为慢指针。
为了方便理解，我们成快指针为r，慢指针为1，这样慢指针和快指针构成区间[1,]。
两个指针以不同速度、不同策略移动，直到快抬针移动到数组尾端，或者两指针相交，满足其他特殊条件时为止。

快慢指针——求解步骤

1.使用两个指针 l、r。l一般指向序列第一个元素，即: l=1,r一般指向序列第零个元素，即:r=0。即初始时区间[l,r」=[1,0]表示为空区间。

2.在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即1++。当满足另外一定条件时(也可能不需要满足条件)，将快指针右移，即r++，保持1,r为合法区间3.到指针移动到数组尾端(即 l==n且r==n)，或者两指针相交，或者满足其他特殊条件时跳出循环体。

	a1	a2	a3	a4	a5	a6	a7
right↑	left↑
→

a1	a2	a3	a4	a5	a6	a7
	left ↑			right ↑

对撞指针例题

题目描述
给定一个长度为 n 的序列 a1,42,……,a„ 和一个幫数 S。
对于一个连续区间如果它的区间和大于或等于S，则称它为美丽的9区间,
对于一个美图的区间，如果其区间长度越短，它就越美丽，
请你从序列中找出最美丽的区间。

利用快慢指针，保持区间[i,j]尽可能小且和>=S。
在这里当[i,j]的sum>=S后，再增加j没有意义，所以i，j都不动了，当i增大后sum可能<S，此时i不可能左移，所以只能右移，于是i，j都只能右移，出现左移。

#include <iostream>

using namespeace std;

const int N = 1e5 + 9;
int a[N],S;

int main()

{

ios::sync_with_stdio(o),cin.tie(o),cout.tie(o);

int n, S;

cin >> nn >>S;

for(int i = 1; i <= n; ++i)

cin >> a[i];

int ans = n + i;

for(int i = 1,j = 0, sum = 0; i <= n; ++i)

{

//考虑移动j，即j++

while(i > j || (j + 1 <= n &&sum < S))

sum += a[++j];

if(sum >= S)

ans = min(ans, j - i + 1);

sum - a[i];

}

cout << (ans > n ? 0 : ans)<<'\n';

return 0;

}

六、构造

1.构造介绍

构造题在比赛和解决问题的过程中确实是常见的一类题型。它们通常要求解题者通过观察问题的结构和规律，找到一种通用的方法或模式，使得在问题规模增大时，依然能够高效地得到答案。
在解决构造题时，以下几点思考是很重要的:
观察问题规模的增长:了解问题随着规模的增大，答案的变化趋势。这可以帮助
你找到一种通用的解决方案。
推广规律:尝试将你观察到的规律推广到更大的问题规模上。这可能涉及到数学
归纳法或者其他类似的思考方式。

考虑状态转移(适用于动态规划等问题):如果问题可以通过状态转移来求解，那么要仔细考虑从一个状态到另一个状态的转移会带来什么影响。
模式识别:尝试寻找问题中的模式或者特征，这有助于你更好地理解问题的本质。
实践和练习:通过解决大量的构造题，你会逐渐培养出发现规律和应用通用方法的能力。注意特殊情况:一些构造题在特定的情况下可能会有不同的解法或者规律，要注意考虑这些特殊情况。

总的来说，解决构造题需要一定的观察力、归纳能力和数学思维。随着练习的增多，你会变得越来越熟练在这类问题上。

2.构造题目的特点

构造题的显著特点之一是其高自由度:
也就是说一道题的构造方式可能存在多种，但往往会有一种相对简单且能够满足题意的构造方式。这种特性看似降低了难度，使问题更易理解，但实际上，这种高自由度往往会导致考生在面对题目时感到迷茫，难以找到明确的解题思路。

面对构造题的特点，我在做题时一般通过以下方法帮助我更有效地解决这类问题:
分析题目要求和条件:
·仔细阅读题目，确保你理解了题目的要求和所给的条件。
·弄清楚问题的背景和目标，明确你需要构造的内容或解决的问题。
尝试特例和极端情况:
试图找出一些特殊情况下的解法，这可以帮助你更好地理解问题的本质
。探索极端情况，看看在极端条件下是否会出现特殊的构造方式或者规律。
寻找模式和规律:
·观察题目中是否存在一些明显的模式或者规律，这可能是解决问题的关键。
·尝试从已知的情况中找到一般性的解法，并推广到更一般的情况。

尝试逆向构造:
·从问题的反面思考也可以给出有用的线索。尝试反向推导出符合条件的情况。
使用数学归纳法:
·尝试使用数学归纳法证明某种构造方式在所有情况下都成立。
灵活运用已知知识:
将已学的数学、物理、逻辑等知识灵活应用，可能会为你找到新的解法。
反复实践和总结:
多做类似的题目，总结解题经验，找出有效的解题方法，虽然不存在通解，但是部分构造题可能会用到相似的套路，如果能够有做题的广度并且经常总结，那么对于你解决构造题目是非常有帮
助的。

保持耐心和信心:
构造题可能需要时间和多次尝试才能找到合适的解法，保持耐心和信心是很重要的

那什么是构造
其实从我前面的描述中，大家也能感受到，构造题目很难找到一个准确的形式化定义，也没有一个通用的解题方法。因此，接下来我们将分享一些经典例题，以帮助大家初步了解构造题的类型。虽然我们不能涵盖所有可能的模式和类型，但可以选择几个比较常见的套路，让大家熟悉一下。

3.构造的应用场景

构造题目在算法竞赛中起着重要的作用，它们旨在考察选手对问题的抽象能力、发现规律的能力以及解决问题的创造性思维。以下是一些构造题目在算法竞赛中的常见应用场景:

·数学问题:
·构造满足一定条件的数列、集合或排列组合。
·利用数学关系构造出特定的解。
图论问题:
·构造特定的图结构，如树、图、有向图等。

·根据题意构造出满足条件的图。

字符串处理:
·构造满足字符串性质的解，如回文串、循环字符串等。
·构造满足特定字符串操作的解。

组合与排列:
构造出满足一定条件的排列或组合。
根据条件构造特定的排列组合解。
游戏策略:
设计游戏规则，构造出有趣的游戏场景，考验选手的策略思维。
逻辑推理:
构造逻辑谜题或者推理题，要求选手根据题目信息进行推理，得出正确答案。
数据结构:
构造特定的数据结构，如堆、树、图等，要求选手在构造的基础上进行一系列操作。

动态规划:
构造状态转移方程，设计合适的状态表示，构造动态规划解，
贪心算法:
构造出合适的贪心策略，使得贪心策略能够得到最优解。

模拟问题:

设计模拟题，要求选手模拟特定场景或过程，根据模拟的结果得出答案。
这些是一些常见的构造题目应用场景。构造题目的特点是多样化，可以涵盖许多不同的领域和难度级别，有助于培养选手的创造性解决问题的能力。因此，在算法竞赛中，构造题目通常被认为是一种重要的题型。