练习题(12-06)
目录
1.最小数
2.数天数
3.非常特殊的数
4.最大值路径
5.拆分质数
6.文件拷贝
7.除去重复单词
8.变成回文字符串
1.最小数
题目描述
请找到一个大于2022的最小数，这个最小的数转换成二进制后，最低的6个二进制全为0.
思路：枚举即可。
#include
#include
#include
#include
using namespace std;bool check(int n)
{vector c;while(n){c.push_back(n%2);n/=2;}for(int i=0;i<6;i++)if(c[i]!=0) return false;return true;
}int main()
{for(int i=2023;;i++)if(check(i)){cout< 2.数天数
问题描述
我们计算从1949年10月1日至2022年1月1日一共经历了多少天？
#include
using namespace std;bool check(int n)
{if(n%4==0&&n%100!=0||n%400==0) return true;return false;
}int main()
{int res=31+30+31;for(int i=1950;i<2022;i++){res+=365;if(check(i)) res++;}cout< 3.非常特殊的数
题目描述
8518是一个非常特殊的数，如果把这个数看成16进制，那么他的值为8161616+51616+116+8=3472 ，而34072正好是8518的整数倍。9558也是这样一个数，当看成16进账时是38232.其实长度为1的数0到9都满足看成16进制是自己的整数倍.请问，除开长度为1的数，最小的满足这样条件的数是多少？
思路：从10开始枚举即可。
#include
#include
#include
using namespace std;int main()
{for(int i=10;i<=8518;i++){string s=to_string(i);int len=s.size();int sum=0;for(int j=0;j 4.最大值路径
题目描述
小蓝有一个30行60列的数字矩阵，矩阵中每一个数都是0到9之间的数字。现在小蓝想从这个矩阵第一行第一列画一条折线到第30行60列，请问这样经过的折线上的数字之和最大值是多少？
思路：dp问题，f[i][j]中i表示向左走的数字之和，j表示向下走的数字之和，w[i][j]:表示i行j列上面的数字 。
最后一格不是从上面到最后一格，就是从左边到最后一格。
f[i][j]表示的集合如下：
则状态转移方程f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j],
代码如下：
#include
#include
#include
using namespace std;
const int N=100;
int w[N][N],f[N][N];
int main()
{for(int i=1;i<=30;i++){string s;cin>>s;for(int j=1;j<=60;j++) w[i][j]=s[i-1]-'0';}f[1][1]=w[1][1];for(int i=1;i<=30;i++)for(int j=1;j<=60;j++){if(i==1&&j==1) continue;f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];}cout< 5.拆分质数
题目描述
将2022拆分成不同的质数的和，请问最多可以拆分几个？
思路：01背包的变形，可以先求出0~2022之间所有的质数，假设这些质数就是物品，背包的容量就是2022，只要找出最多可以放进背包的物品个数，就可以解决。
#include
#include
#include
#include
using namespace std;const int N=3000;
int q[N];
int f[N][N];
int v[N];
int n=1;bool check(int n)
{for(int i=2;i<=n/i;i++)if(n%i==0) return false;return true;
}int main()
{for(int i=2;i<=2022;i++)if(check(i)) v[n++]=i;int m=2022;for(int i=1;ij) f[i][j]=f[i-1][j];else f[i][j]=max(f[i-1][j],f[i][j-v[i]]+1);cout< 6.文件拷贝
题目描述
小蓝正在拷贝一件文件，他现在已经拷贝了t秒时间，已经拷贝了c字节，文件总共有s字节，如果拷贝是匀速进行的，请问小蓝大概还要拷贝多少秒？
输入格式
输入一行包含3个整数t,c,.
输出格式
输出一个整数表示答案。
数据范围
1<=t,c,s<=1000000000.
#include
#include
#include
using namespace std;
typedef long long ll;int main()
{ll t,c,s;cin>>t>>c>>s;double v=t*1.0/c;s-=c;double cnt=s*v;if(cnt-(int)cnt>0) cout<<(int)cnt+1< 7.除去重复单词
问题描述
小蓝有n个单词，但是有些单词是重复的，请你去掉重复的单词。
样例输入：
5
apple
apple
net
think
net
样例输出
think
数据范围
1<=n<=100
#include
#include
#include
#include
#include
using namespace std;
unordered_map h;
vector c;
int main()
{int n;cin>>n;while(n--){string x;cin>>x;if(h.count(x)==1) continue; //已经出现过else{c.push_back(x);h[x]++;}}for(int i=0;i 8.变成回文字符串
题目描述
一个字符串如果从左往右和从右往左读相同，则称为回文串，例如lanqiaoaiqnal是一个回文串。小蓝有一个字符串，请你在这个字符串的右边加入若干字符，使其成为一个回文串，请你输出最短的回文串。
数据范围
1<=字符串长度<=100
思路：从头往后遍历，找到第一个元素，以这个元素为起点到字符串末尾 构成一个回文串，此时这段区间就是公共的区间，只需要把这个字符前面的字符串反转到末尾即可。
这时候我们需要用到反转函数和字符串中i到j之间的字符串的函数，我们可以先考虑stl库，如果实在想不到，可以手写。
substr函数：
string substr(string x,int i,int j)
{string y;for(int k=i;k<=j;k++)y+=x[i];return y;
}reverse函数：
string reverse(string x,int i,int j)
{string y;for(int k=j;k>=i;k--)y+=x[i];return y;
}
#include
#include
#include
using namespace std;string s;bool check(string s)
{int l=0,r=s.size()-1;while(l>s;int i=0;int n=s.size();for(i=0;i 下一篇：蓝桥杯嵌入式Debug