目录
一、二分法
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.构造的应用场景
构造题目在算法竞赛中起着重要的作用，它们旨在考察选手对问题的抽象能力、发现规律的能力以及解决问题的创造性思维。以下是一些构造题目在算法竞赛中的常见应用场景:
·数学问题:
·构造满足一定条件的数列、集合或排列组合。
·利用数学关系构造出特定的解。
图论问题:
·构造特定的图结构，如树、图、有向图等。
·根据题意构造出满足条件的图。
字符串处理:
·构造满足字符串性质的解，如回文串、循环字符串等。
·构造满足特定字符串操作的解。
组合与排列:
构造出满足一定条件的排列或组合。
根据条件构造特定的排列组合解。
游戏策略:
设计游戏规则，构造出有趣的游戏场景，考验选手的策略思维。
逻辑推理:
构造逻辑谜题或者推理题，要求选手根据题目信息进行推理，得出正确答案。
数据结构:
构造特定的数据结构，如堆、树、图等，要求选手在构造的基础上进行一系列操作。
动态规划:
构造状态转移方程，设计合适的状态表示，构造动态规划解，
贪心算法:
构造出合适的贪心策略，使得贪心策略能够得到最优解。
模拟问题:
设计模拟题，要求选手模拟特定场景或过程，根据模拟的结果得出答案。
这些是一些常见的构造题目应用场景。构造题目的特点是多样化，可以涵盖许多不同的领域和难度级别，有助于培养选手的创造性解决问题的能力。因此，在算法竞赛中，构造题目通常被认为是一种重要的题型。
4.构造例题解析
【题目描述】数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N个整数。现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项,请输出这几项。
【输入描述】输入的第一行包含一个整数N。 第二行包含N个整数A,,A,···,A.。(注意A,~A,,并不一定是按等差数列中的顺序给出)(对于所有评测用例，2≤N<100800，0≤Ai≤10°。)
【输出描述】输出一个序列表示答案
所有数字间距离最小的间隔是公差吗?
等差数列的最小间隔(实际上不是公差)，例如(2，5，7}，最小的间隔是2，但公差不是2，是1。
这其实一个GCD构造问题，可以通过计算给定数字间的所有间隔的最大公约数(GCD)来确定。
把n个数据排序，计算它们的间隔，对所有间隔做GCD，结果为公差。
同时，通过最小值、最大值和公差，可以计算出等差数列的最少数量。
最少数量等于=(最大值-最小值)/公差+1。
从最小值到最大值依次输出即可。
七、进制的转换
1.进制的本质
对于一个十进制数字，比如说153，其本质是每一个数位上的数字乘上这一位上的权重，
即:
153=(1x102)+(5 x10)+(3 x10°)
而二进制，只不过是把10换成了2，任意一个非负整数都有唯一的一个二进制表示:
(153)10 =
在计算机中，数字均通过二进制补码表示，所以学习进制转换尤为重要。
2.将任意进制转换为十进制
假设给了一个数组来表示一个k进制(假设k>10)的整数，我们该如何得到它的十进制数?
| k^4 | k^3 | k^2 | k^1 | k^0 | |
| a | 1 | 3 | 10 | 5 | 7 |
| idx | 1 | 2 | 3 | 4 | 5 |
1l x= 0;
for(int i = 1;i <= n; ++ i)
x=x* k + a[i];
cout << x<< '\n';
一般来说，这个k进制的数组可以通过对输入字符串的处理得到。
3.将十进制转换为任意进制
假设现在有一个十进制数x，如何转换为k进制呢?
我们可以先假设一个x的k进制表达式，再逐步地去求解。
x = x
+...+
x
+
x
对于这个表达式，我们可以快速计算出a0=x%k
计算出a0之后怎么办，我们只需要将x/=k，就可以将原本的a1放到a0位置上，再同样解即可。
x/k = x
+...+
x
11 x;
cin >>x;
while(x) a[++ cnt]=x % k,x /= k;
reverse(a+1，a+1+cnt);//注奖翻转一下，才能使得高位在1的位置
例如十进制的11转换为二进制，根据这个规则得到的a数组为[1,1,0,1]，而实际上11的二进制为[1,0,1,1]。
![[CKS] K8S AppArmor Set Up](https://i-blog.csdnimg.cn/direct/882683808a7f4174b6c1be9748c2682b.png)
