一、进制转换
1.十进制： 都是以0-9这九个数字组成，不能以0开头。
2.二进制： 由0和1两个数字组成。
3.八进制： 由0-7数字组成，为了区分与其他进制的数字区别，开头都是以0开始。
4.十六进制：由0-9和A-F组成。为了区分于其他数字的区别，开头都是以0x开始。
1.整数转换
（1）十进制转二进制的转换原理：除以2，反向取余数，直到商为0终止。
（2）十进制转八进制的转换原理：除以8，反向取余er数，直到商为0终止。
（3）十进制转十六进制的转换原理：除以16，反向取余数，直到商为0终止。
2.小数部分转换
（1）十进制转二进制的原理：十进制小数转换成二进制小数采用 “乘2取整，顺序输出” 法。
例题： 0.68D = ______ B（精确到小数点后5位）
如下所示，0.68乘以2，取整，然后再将小数乘以2，取整，直到达到题目要求精度。得到结果：0.10101B.
例如：十进制小数0.68转换为二进制数
具体步骤：
0.68* 2=1.36 -->1
0.36* 2=0.72 -->0
0.72* 2=1.44 -->1
0.44* 2=0.88–>0
0.88* 2=1.76 -->1
已经达到了题目要求的精度，最后将取出的整数部分顺序输出即可
则为：0.68D–>0.10101B
（2）十进制转八进制的原理：十进制小数转换成八进制小数采用 “乘8取整，顺序输出” 法。
例题： 10.68D = ______ Q（精确到小数点后3位）
解析：如下图所示，整数部分除以8取余数，直到无法整除。小数部分0.68乘以8，取整，然后再将小数乘以8，取整，直到达到题目要求精度。得到结果：12.534Q.
例如：十进制数10.68转换成八进制数，分为整数部分和小数部分求解
步骤：
(1)整数部分
10/8=1 -->2
1/8=0 -->1
倒序输出为12
(2)小数部分
0.68* 8=5.44 -->5
0.44* 8=3.52 -->3
0.52* 8=4.16 -->4
已经达到了题目要求的精度，即可结束
则小数部分为：0.68–>0.534
因此10.68D -->12.534Q
（3）十进制转十六进制的原理：十进制小数转换成十六进制小数采用 “乘16取整，顺序输出” 法。
例题： 25.68D = ______ H（精确到小数点后3位） 解析：如下图所示，整数部分除以16取余数，直到无法整除。小数部分0.68乘以16，取整，然后再将小数乘以16，取整，直到达到题目要求精度。得到结果：19.ae1H.
（1）整数部分
25/16=1 -->9
1/16=0 -->1
倒序输出为：19
（2）小数部分
0.68* 16=10.88 -->a(即十进制中的10)
0.88* 16=14.08 -->e
0.08* 16=1.28 -->1
已经达到了要求的精度，顺序输出为：ae1
则：25.68D -->19.ae1H
总结：小数部分转换原理都是乘进制数取整数部分，再将整数部分顺序输出。
例题1：年号字串（十进制转换成二十六进制）——2019省赛
- 2019 / 26 = 77 余 17 ，17 对应
Q - 77 / 26 = 2 余 25，25 对应
Y - 2 / 26 = 0 余 2, 2 对应
B
ASCII码中：48～57为0到9十个阿拉伯数字；65～90为26个大写英文字母；97～122号为26个小写英文字母
ASCII码大写字母转换为数字：大写字母-‘A’+1 或者 大写字母-‘@’
ASCII码数字转换为大写字母：数字+‘A’-1 或者 数字+‘@’或者 数字+64
ASCII码小写字母转换为数字：小写字母-‘a’+1
ASCII码数字转换为小写字母：数字+‘a’-1
ASCII码大写字母转换为小写字母：大写字母+32 或者 大写字母-‘A’+‘a’
ASCII码小写字母转换为大写字母：小写字母-32 或者 小写字母-‘a’+‘A’
ASCII码字符型数字转换为整型数字：字符型数字 - ‘0’ 或者 字符型数字 - 48
8、ASCII码整型数字转换为字符型数字：整型数字 + 48 或者 整形数字 + ‘0’
解法1：迭代
#include <iostream>
using namespace std;
void solve(int n) {
if (n==0) {
return ;
}
solve(n / 26);
cout << (char)(n % 26 + 64);//int值65强转char会根据ASCII转成对应的字符A,
}
int main() {
solve(2019);
return 0;
}解法2：STL容器
#include <iostream>
#include <stack>
using namespace std;
stack<int> sta;
int main()
{
int n=2019;
while(n!=0)
{
sta.push(n%26);
n=n/26;
}
while(!sta.empty())
{
cout<<(char)(sta.top()+64);
//或者把加上64换成加上'@'
cout<<(char)(sta.top()+'@');
sta.pop();
}
return 0;
}例题2：九进制转换成十进制 ——2022省赛
此题可参考二进制转换成十进制的方法
#include <iostream>
#include<stack>
#include<cmath>
using namespace std;
int main()
{
// 请在此输入您的代码
int n=2022;//把2，0，2，2分别传入sta中
stack<int> sta;
sta.push(n/1000);
n=n-(n/1000)*1000;
sta.push(n/100);
n=n-(n/100)*100;
sta.push(n/10);
sta.push(n-(n/10)*10);
int num=0;//2022的十进制数
int i=0;
while(!sta.empty())
{
i++;
//cout<<sta.top()<<" ";
num+=sta.top()*pow(9,i-1);
sta.pop();
}
cout<<num;
return 0;
}二、模运算
取模运算也叫取余运算，在C中用%来表示， 数学中叫mod。
例题3：数列求值——2019省赛
题目要求的是第20190324位的后四位数，所以，每次计算只需要计算后四位相加的结果，这时我们可以想到对数列的每一项进行对10000取模的操作，这样即保留的是数的后四位，又不会改变它的值。
#include <iostream>
#include<vector>
using namespace std;
int main()
{
// 请在此输入您的代码
vector<int> vec(20190324);
vec[0]=1;
vec[1]=1;
vec[2]=1;
for(int i=3;i<20190324;i++)
{
vec[i]=(vec[i-3]+vec[i-2]+vec[i-1])%10000;
}
cout<<vec[20190323];
return 0;
}三、GCD求最大公约数
如何求最大公约数？
欧几里得算法（辗转相除法）
定理1：d能整除a且d能整除b，那么d就能整除ax+by；
定理2：
证明：
a/b就是（a整除b）=c，也就是c是整数。
因为d能整除a且d能整除b，那么由定理1可得，d就能整除
求最大公约数代码：
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;//b为真执行gcd(b,a%b);b为假执行return a
}例题4：等差数列
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;//b为真执行gcd(b,a%b);b为假执行return a
}
int main()
{
int n,i;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());//排序
int d=a[1]-a[0];
for(int i=2;i<n;i++)
{
d=gcd(d,a[i]-a[i-1]);
}
if(a[n-1]==a[0])cout<<n<<endl;//考虑特殊情况，也就是n个数都相等的情况
else cout<<((a[n-1]-a[0])/d)+1<<endl;//等差数列公式
return 0;
}四、日期枚举
1.什么是闰年：
闰年一年的时间为：366天，2月份有29天。
平年一年的时间为：365天，2月份有28天。
2.闰年的判定方法：
（1）普通年能被4整除且不能被100整除的为闰年。（如2004年就是闰年，1900年不是闰年）
（2）世纪年能被400整除的是闰年。（如2000年是闰年，1900年不是闰年）
判断闰年的代码：
bool isleep(int year)
{
if((year%4==0&&year%100!=0)||year%400==0) return true;
else return false;
}判断日期是否有效的代码：
bool isvalid(int year,int month,int day)
{
if(month<=0||month>12) return false;
if(day>31) return false;
if(month==2)
{
if(isleep(year)&&day>29) return false;//是闰年
if(!isleep(year)&&day>28) return false;//不是闰年
}
return true;
}例题5：回文日期
#include <iostream>
using namespace std;
bool isleep(int year)
{
if((year%4==0&&year%100!=0)||year%400==0) return true;
else return false;
}
bool isvalid(int year,int month,int day)
{
if(month<=0||month>12) return false;
if(day>31) return false;
if(month==2)
{
if(isleep(year)&&day>29) return false;//是闰年
if(!isleep(year)&&day>28) return false;//不是闰年
}
return true;
}
int main()
{
// 请在此输入您的代码
int n;
cin>>n;
int a,b,c,d,e,f,g,h;
int year,month,day;
bool flag=false;
for(int 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;//hgfedcba
if(h==a&&g==b&&f==c&&e==d&&isvalid(year,month,day)&&flag==false)
{
cout<<i<<endl;
flag=true;
}
if(a==h&&g==b&&f==c&&e==d&&h==f&&g==e&&isvalid(year,month,day))
{
cout<<i<<endl;
break;
}
}
return 0;
}五、枚举，计算贡献
例题6：子串分值和
1.unordered_set 容器具有以下几个特性：
- 不再以键值对的形式存储数据，而是直接存储数据的值；
- 容器内部存储的各个元素的值都互不相等，自动删去重复元素，使得集合内的元素各不相同，且不能被修改；
- 不会对内部存储的数据进行排序（这和该容器底层采用哈希表结构存储数据有关；
2.unordered_set 容器的成员方法：
| size() | 返回当前容器中存有元素的个数。 |
| insert() | 向集合中插入某个元素。 |
| emplace() | 向容器中添加新元素，效率比 insert() 方法高。 |
| clear() | 清空容器，即删除容器中存储的所有元素 |
方法一：暴力枚举（只能通过40%的案例）
#include <iostream>
#include<unordered_set>
using namespace std;
int main()
{
// 请在此输入您的代码
string s;
cin>>s;
int n=s.length();
int res=0;
for(int l=0;l<n;l++)
{
for(int r=l;r<n;r++)
{
unordered_set<char> S;
for(int k=l;k<=r;k++) S.insert(s[k]);
res+=S.size();
}
}
cout<<res;
return 0;
}方法二：乘法原理
1.每个字母只有在第一次出现时才有f值（也叫贡献度），因此可以统计每个字母在第一次出现的情况下，能被多少子串所包含；
2.用
3.那么往左最多能延伸到
4.二者相乘，就是该字母被不同子串所包含的总次数；
那么该如何来计算每个字符的贡献度呢？所谓贡献度，即该字符能够影响到的子串个数，就比如：
| 0 | 1 | 2 | 3 | 4 | 5 |
| a | b | a | b | c |
表格中的4号b能够影响多少个子串呢？
列举一下有：ab,b,abc,bc共有4个（这些子串的f值都因为b增加了1，而bab这个子串不会因为3号b增加f值）.
那么如何用数学的方法计算出来贡献度呢？
b上次出现的位置是
表格中的3号a能影响多少子串呢？列举一下有；ba,bab,babc,a,ab,abc
起点可以是2，3；终点可以是3，4，5，所以该字母a被不同子串所包含的总次数即（3-1）*（5-3+1） =6
a，出现在 a,ab,aba,abab,ababc中，对每一个串贡献值为1,和为5，
b，出现在b,ba,bab,babc+ab,aba,abac,ababc,对每一个串贡献值为1，和为8
a，出现在a,ab,abc + ba,bab,babc + aba,abab,ababc,有重复子串 aba，abab，ababc（这几个其实第一个a已经包含过它们了，所以只需要从a算到b a,前面的可以删去不用，因为之前的情况前面的a已经贡献过了），最后算得贡献值为6，
b,出现在了b,bc + ab,abc +bab,babc + abab,ababc,含有相同字符的前串bab ，babc，abab，ababc可以去掉，最后算得贡献值为4，
c，出现在c,bc,abc,babc,ababc对每一个串贡献值为1，和为5
答案就是： 5 + 8 + 6 + 4 + 5 = 28
六、动态规划之线性DP
例题7：数字三角形
#include <iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
// 递推公式dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j])
int N;
cin>>N;
vector<vector<int>> a(N,vector<int>(N));
vector<vector<int>> dp(N,vector<int>(N));
for(int i=0;i<N;i++)//行
{
for(int j=0;j<i+1;j++)
{
cin>>a[i][j];
}
}
dp[0][0]=a[0][0];
for(int i=1;i<N;i++)//行
{
for(int j=0;j<=i;j++)//列
{
if(j==0) dp[i][0]=dp[i-1][0]+a[i][0];//左斜边
else if(j==i) dp[i][j]=dp[i-1][j-1]+a[i][j];//右斜边
else dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
}
}
cout<<*max_element(dp[N-1].begin(),dp[N-1].end());
// int res=0;
// for(int j=0;j<N;j++) res=max(res,dp[N-1][j]);
// cout<<res;
return 0;
}七、动态规划之偏移量
例题8：砝码称重
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll N;
ll a[200];
ll summ = 0;
ll ans = 0;
int dp[200][200000];
//dp[i][j]表示用到前i个砝码，能否称出j重量
//1为可以，0为不可以
int main()
{
// 请在此输入您的代码
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> a[i];
summ += a[i];
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= summ; j++)
{
dp[i][j] = dp[i - 1][j];//继承前一个状态
if (dp[i][j] == 0)
{
if (j == a[i]) dp[i][j] = 1;//如果需要的重量正好就是第i个砝码，那么可以
if (dp[i - 1][j + a[i]] == 1) dp[i][j] = 1;//如果前i-1个能搞出j+a[i]重量，那么把第i个砝码放到另一侧就行
if (dp[i - 1][abs(j - a[i])] == 1) dp[i][j] = 1;//如果前i-1个砝码能搞出abs(j-a[i])重量
//那么把第i个砝码放同侧就行
}
}
}
for (int j = 1; j <= summ; j++)
{
if (dp[N][j] == 1) ans++;//遍历，看dp[][]==1的个数，就是答案
}
cout << ans << endl;
return 0;
}八、因子分解
比如：18=2×3×3=2×3^2。约数有1，2，3，6，9，18，约数个数为（1+1）×（2+1）。
为什么要加1：因为对于2×3^2来说。2这个位置有两种选择（0，1），3这个位置有三种选择（0，1，2）；18的约数之和就是
求约数个数的代码：
int get_an(int x)//求x的约数个数
{
unordered_map<int, int> primes;//i放质因数，primes[i]放对应的质因数的个数
int res=1;
for(int i=2;i<=x/i;i++)
{
while (x % i == 0)//说明i是x的质约数
{
x=x/i;
primes[i]++;//i是质因子，primes[i]是指数
}
}
if(x>1) primes[x]++;
//for(auto p:primes) cout<<p.first<<" "<<p.second<<endl;
for(auto p:primes) res=res*(p.second+1);
cout<<res<<endl;
}求约数的和的代码：
int get_an(int x)//求x的约数的和
{
unordered_map<int, int> primes;//i放质因数，primes[i]放对应的质因数的个数
for(int i=2;i<=x/i;i++)
{
while (x % i == 0)//说明i是x的质约数
{
x=x/i;
primes[i]++;//i是质因子，primes[i]是指数
}
}
if(x>1) primes[x]++;
//for(auto p:primes) cout<<p.first<<" "<<p.second<<endl;
vector<int> vec;
for(auto p:primes)
{
int sum=0;
for(int j=0;j<=p.second;j++)
{
sum+=pow(p.first,j);
}
vec.push_back(sum);
}
int ans=1;//ans是最后的总和
for(int i=0;i<vec.size();i++) ans*=vec[i];
cout<<res<<endl;
}例题9：约数个数
#include <iostream>
#include<unordered_map>
using namespace std;
int main()
{
int x=1200000;
int res=1;
unordered_map<int, int> primes;
for(int i=2;i<=x/i;i++)
{
while (x % i == 0)//说明i是x的质约数
{
x=x/i;
primes[i]++;//i是质因子，primes[i]是指数
}
}
if(x>1) primes[x]++;
//for(auto p:primes) cout<<p.first<<" "<<p.second<<endl;
for(auto p:primes) res=res*(p.second+1);
cout<<res<<endl;
return 0;
}