一、进制转换
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省赛
年号字串 - 蓝桥云课 (lanqiao.cn)
- 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省赛
九进制转十进制 - 蓝桥云课 (lanqiao.cn)
此题可参考二进制转换成十进制的方法
#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省赛
数列求值 - 蓝桥云课 (lanqiao.cn)
题目要求的是第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就能整除,那么d就能整除
求最大公约数代码:
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;//b为真执行gcd(b,a%b);b为假执行return a
}
例题4:等差数列
等差数列 - 蓝桥云课 (lanqiao.cn)
#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:回文日期
回文日期 - 蓝桥云课 (lanqiao.cn)
#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:子串分值和
子串分值和 - 蓝桥云课 (lanqiao.cn)
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.用 记录字母 s[i] 上一次出现的位置;
3.那么往左最多能延伸到,其到第 i 个字母一共有个字母;同理往右最多能延伸到 n,其到第 i 个字母一共有 个字母;
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上次出现的位置是,i是现在这个b在的位置,,所以这些子串的起点可以为3,4,也就是往左最多能延伸到;终点往右最多能延伸到 (n是字符串的长度),终点可以为4,5,这样该字母b被不同子串所包含的总次数即(4-2)*(5-4+1) = 4
表格中的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:数字三角形
数字三角形 - 蓝桥云课 (lanqiao.cn)
#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:砝码称重
砝码称重 - 蓝桥云课 (lanqiao.cn)
#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;
}
求约数的和的代码:文章来源:https://www.toymoban.com/news/detail-406694.html
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:约数个数
约数个数 - 蓝桥云课 (lanqiao.cn)文章来源地址https://www.toymoban.com/news/detail-406694.html
#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;
}
到了这里,关于蓝桥杯高频知识点(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!