01 最少砝码
最少砝码
问题描述
你有一架天平。现在你要设计一套砝码,使得利用这些砝码
可以出任意小于等于N的正整数重量。那么这套砝码最少需要包含多少个砝码?
注意砝码可以放在天平两边。
输入格式
输入包含一个正整数N。
输出格式
输出一个整数代表答案。
样例输入
7
样例输出
3
样例说明
3个砝码重量是1、4、6,可以称出1至7的所有重量。
1=1:
2=6-4(天平一边放6,另一边放4);
3=4-1;
4=4:
5=6-1:
6=6:
7=1+6:
少于3个砝码不可能称出1至7的所有重量。
评测用例规模与约定
对于所有评测用例,1≤N≤1000000000。
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
// 请在此输入您的代码
//它让找到可以表示1-目标数字的最少砝码块,我们不妨找到不同砝码块个数所能表示到的最大值,如一个最大可以表示到1,两个(1,3)最大可以表示到4
//因此我们可以找到最大值大于目标重量的砝码块数即可
//找规律可得最大砝码块依次1,3,9,27.....可以看出为3的幂次
int n;
scanf("%d",&n);
int weight=1;//表示其中最大的一个砝码
int sum=1;//表示所能秤的最大重量
int num=1;//表示所需要的砝码数目
while(n>sum)
{
num++;
weight*=3;
sum+=weight;
}
printf("%d",num);
return 0;
}
02 承压计算
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结
果输出即可。
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致,但重量不同。金属材料被严格
地堆放成金字塔形。
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
其中的数字代表金属块的重量(计量单位较大)。
最下一层的X代表30台极高精度的电子秤。
假设每块原料的重量都十分精确地平均落在下方的两个金属块上,最
后,所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小,所以显示的数字很大。
工作人员发现,其中读数最小的电子秤的示数为:2086458231
请你推算出:读数最大的电子秤的示数为多少?
#include <stdio.h>
int main(void) {
double arr[30][30] = {
{7},
{5, 8},
{7, 8, 8},
{9, 2, 7, 2},
{8, 1, 4, 9, 1},
{8, 1, 8, 8, 4, 1},
{7, 9, 6, 1, 4, 5, 4},
{5, 6, 5, 5, 6, 9, 5, 6},
{5, 5, 4, 7, 9, 3, 5, 5, 1},
{7, 5, 7, 9, 7, 4, 7, 3, 3, 1},
{4, 6, 4, 5, 5, 8, 8, 3, 2, 4, 3},
{1, 1, 3, 3, 1, 6, 6, 5, 5, 4, 4, 2},
{9, 9, 9, 2, 1, 9, 1, 9, 2, 9, 5, 7, 9},
{4, 3, 3, 7, 7, 9, 3, 6, 1, 3, 8, 8, 3, 7},
{3, 6, 8, 1, 5, 3, 9, 5, 8, 3, 8, 1, 8, 3, 3},
{8, 3, 2, 3, 3, 5, 5, 8, 5, 4, 2, 8, 6, 7, 6, 9},
{8, 1, 8, 1, 8, 4, 6, 2, 2, 1, 7, 9, 4, 2, 3, 3, 4},
{2, 8, 4, 2, 2, 9, 9, 2, 8, 3, 4, 9, 6, 3, 9, 4, 6, 9},
{7, 9, 7, 4, 9, 7, 6, 6, 2, 8, 9, 4, 1, 8, 1, 7, 2, 1, 6},
{9, 2, 8, 6, 4, 2, 7, 9, 5, 4, 1, 2, 5, 1, 7, 3, 9, 8, 3, 3},
{5, 2, 1, 6, 7, 9, 3, 2, 8, 9, 5, 5, 6, 6, 6, 2, 1, 8, 7, 9, 9},
{6, 7, 1, 8, 8, 7, 5, 3, 6, 5, 4, 7, 3, 4, 6, 7, 8, 1, 3, 2, 7, 4},
{2, 2, 6, 3, 5, 3, 4, 9, 2, 4, 5, 7, 6, 6, 3, 2, 7, 2, 4, 8, 5, 5, 4},
{7, 4, 4, 5, 8, 3, 3, 8, 1, 8, 6, 3, 2, 1, 6, 2, 6, 4, 6, 3, 8, 2, 9, 6},
{1, 2, 4, 1, 3, 3, 5, 3, 4, 9, 6, 3, 8, 6, 5, 9, 1, 5, 3, 2, 6, 8, 8, 5, 3},
{2, 2, 7, 9, 3, 3, 2, 8, 6, 9, 8, 4, 4, 9, 5, 8, 2, 6, 3, 4, 8, 4, 9, 3, 8, 8},
{7, 7, 7, 9, 7, 5, 2, 7, 9, 2, 5, 1, 9, 2, 6, 5, 3, 9, 3, 5, 7, 3, 5, 4, 2, 8, 9},
{7, 7, 6, 6, 8, 7, 5, 5, 8, 2, 4, 7, 7, 4, 7, 2, 6, 9, 2, 1, 8, 2, 9, 8, 5, 7, 3, 6},
{5, 9, 4, 5, 5, 7, 5, 5, 6, 3, 5, 3, 9, 5, 8, 9, 5, 4, 1, 2, 6, 1, 4, 3, 5, 3, 2, 4, 1}
}, max = 0, min = 9999;
int i = 1, j = 0;
for (i = 0; i < 30; ++i) {
for (j = 0; j < 30; ++j) {
if (j - 1 >= 0) {
arr[i][j] += arr[i - 1][j - 1] / 2.0;
if (29 == i) {
max = max < arr[i][j] ? arr[i][j] : max;
min = min > arr[i][j] ? arr[i][j] : min;
}
}
if (i - 1 >= 0 && arr[i - 1][j] > 0) {
arr[i][j] += arr[i - 1][j] / 2.0;
if (29 == i) {
max = max < arr[i][j] ? arr[i][j] : max;
min = min > arr[i][j] ? arr[i][j] : min;
}
} else {
break;
}
}
}
printf("%lld\n", (long long)(max * (2086458231.0 / min)));
return 0;
}
03 数的分解
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果
输出即可。
把2019分解成3个各不相同的正整数之和,并且要求每个正整数都不
包含数字2和4,一共有多少种不同的分解方法?
注意交换3个整数的顺序被视为同一种方法,例如1000+1001+18
和1001+1000+18被视为同一种。
#include<iostream>
using namespace std;
bool judge(int n){
while(true){
if(n==0){
return 1;
break;
}
if(n%10==2||n%10==4){
return 0;
break;
}
n/=10;
}
}
int main(){
int sum=0;
for(int i=1;i<=672;i++)
for(int j=i+1;j<2019-i-j;j++)
if(judge(2019-i-j)&&judge(j)&&judge(i))
sum++;
cout<<sum;
return 0;
}
04 顺子日期
问题描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果
输出即可。
小明特别喜欢顺子。顺子指的就是连续的三个数字:123、456等。顺子日期指的就是在日期的yyyymmdd表示法中,存在任意连续的三位数是一个顺子的日期。例如20220123就是一个顺子日期,因为它出现了一个顺子:123;而20221023则不是一个顺子日期,它一个顺子也没有。小明想知道在整个2022年份中,一共有多少个顺子日期?
#include<iostream>
using namespace std;
int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int q[])
{
for(int i=3;i<=5;i++)
{
if(q[i]==(q[i+1]-1)&&q[i+1]==(q[i+2]-1))
{
return true;
}
}
return false;
}
int main()
{
int q[8]={2,0,2,2};
int res=0;
for(int i=1;i<=12;i++)
{
q[4]=i/10%10;
q[5]=i%10;
for(int j=1;j<=day[i];j++)
{
q[6]=j/10%10;
q[7]=j%10;
if(check(q)) res++;
}
}
cout<<res<<endl;
return 0;
}
05 灭鼠先锋
问题描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
灭鼠先锋是一个老少咸宜的棋盘小游戏,由两人参与,轮流操作。
灭鼠先锋的棋盘有各种规格,本题中游戏在两行四列的棋盘上进行。
游戏的规则为:两人轮流操作,每次可选择在棋盘的一个空位上放置
一个棋子,或在同一行的连续两个空位上各放置一个棋子,放下棋子
后使棋盘放满的一方输掉游戏。
小蓝和小乔一起玩游戏,小蓝先手,小乔后手。小蓝可以放置棋子的
方法很多,通过旋转和翻转可以对应如下四种情况:
XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO
其中O表示棋盘上的一个方格为空,X表示该方格已经放置了棋子。
请问,对于以上四种情况,如果小蓝和小乔都是按照对自己最优的策
略来玩游戏,小蓝是否能获胜。如果获胜,请用V表示,否则用L表
示。请将四种情况的胜负结果按顺序连接在一起提交。
#include <iostream>
#include <map>
//必败局一定转化为必赢局
//必赢局至少有一个可能转化为必败局
//基于这两种方式可以做到两种dfs
//即必赢局dfs和必败局dfs(两种理解方式更深入理解博弈论)
using namespace std;
//dfs 返回为true,则本局为必赢局
map<string,bool>m;
bool dfs(string s)
{
if(m.count(s))//m有s的键值
return m[s];
int index=0;
for(int i=0;i<s.size();++i)
{
if(s[i]=='O')
++index;
}
if(index==1)
return m[s]=false;//只有一个可选,为必败局
//只要找到一个能形成的必败局,这局就是必赢局。
for(int i=0;i<s.size();++i)
{
if(s[i]=='O')
{
string ss=s;
ss[i]='X';
if(!dfs(ss))//下一局为必败局
return m[s]=true;
}
}
for(int i=0;i<s.size();++i)
{
if(s[i]=='O'&&s[i+1]=='O'&&i!=3)
{
string ss=s;
ss[i]=ss[i+1]='X';
if(!dfs(ss))
return m[s]=true;
}
}
return false;//没找到则是必败局
}
int main()
{
// 请在此输入您的代码
string s[4]={"XOOOOOOO","XXOOOOOO","OXOOOOOO","OXXOOOOO"};
for(int i=0;i<4;++i)
{
if(dfs(s[i]))//对手是必赢局
cout<<"L";
else
cout<<"V";
}
return 0;
}
//dfs返回为true,则本局为必败局
// map<string,bool>m;
// bool dfs(string s)
// {
// if(m.count(s))
// return m[s];
// int index=0;
// for(int i=0;i<s.size();++i)
// {
// if(s[i]=='O')
// ++index;
// }
// if(index==1)
// return m[s]=true;
// if(index==0)
// return m[s]=false;
// for(int i=0;i<s.size();++i)
// {
// if(s[i]=='O')
// {
// string ss=s;
// ss[i]='X';
// if(dfs(ss))
// return m[s]=false;
// }
// }
// for(int i=0;i<s.size();++i)
// {
// if(s[i]=='O'&&s[i+1]=='O'&&i!=3)
// {
// string ss=s;
// ss[i]=ss[i+1]='X';
// if(dfs(ss))
// return m[s]=false;
// }
// }
// return true;
// }
// int main()
// {
// // 请在此输入您的代码
// string s[4]={"XOOOOOOO","XXOOOOOO","OXOOOOOO","OXXOOOOO"};
// for(int i=0;i<4;++i)
// {
// if(dfs(s[i]))
// cout<<"V";
// else
// cout<<"L";
// }
// return 0;
// }
06 练习
问题描述
小蓝在蓝桥杯练习系统上做题。做到一道题,他编写好程序,在自己的
电脑上尝试了题目中提供的几个样例,全部得到了正确的结果,可是当
他将自己的程序提交到练习系统上时,却得了0分,这种情况可能的原
因是什么?请在以下选项中选择所有可能导致这种情况的原因。
A.题目中的样例一般比较小,在评测的时候可能使用的评测用例比较
大,小蓝的程序虽然在小样例能得到解,对于大一些的评测用例可能速
度太慢,超过了题目要求的时间限制。
B.小蓝的内存使用过多,虽然在自己的电脑上运行正确,可是在评测的
内存限制下无法运行。
C.小蓝的程序有考虑不足之处,题目中的样例比较小,小蓝的程序恰好
能得到对应的结果,可是当评测用例比较复杂时,小蓝的程序无法得到
正确的结果。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为
一个由大写字母组成的字符串,按字母顺序给出所选择的选项,在提交
答案时只填写这个字符串,填写多余的内容将无法得分。例如,如果选
项全部正确 请填写答案ABC
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
printf("ABC");// 请在此输入您的代码
return 0;
}
07 排序
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。
在冒泡排序中,每次只能交换相邻的两个元素。
小蓝发现,如果对一个字符串中的字符排序,只允许交换相邻的两个
字符,则在所有可能的排序方案中,冒泡排序的总交换次数是最少
的。例如,对于字符串lan排序,只需要1次交换。对于字符串qiao排
序,总共需要4次交换。
小蓝找到了很多字符串试图排序,他恰巧碰到一个字符串,需要100
次交换,可是他忘了吧这个字符串记下来,现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串,对该串的字符排序,正好需要100次交换。如果可能找到多个,请告诉小蓝最短的那个。如果最短的仍然有多个,请告诉小蓝字典序最小的那个。
#include <stdio.h>
#include <stdlib.h>
char* init(char a[26],char s[26]);
int count(char s[26],int n);//排序次数
int main(int argc, char *argv[])
{
// 请在此输入您的代码
char s[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char a[26];
int len=0;
int k;
int c;
for(int i=0;i<26;i++){
char *m=init(a,s);
int c=count(a,len);
len++;
if(c>100){
k=c;
break;
}
}
init(a,s);
len--;
char result[len];
for(int i=0;i<len;i++){
result[i]=s[len-1-i];
}
int m=k-100;//第几位放在最前面
char x=result[m];
for(int i=m-1;i>=0;i--){
char g=result[i];
result[i]=result[i+1];
result[i+1]=g;
}
printf("%s",result);
return 0;
}
int count(char s[26],int n){
int a=0;
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
if(s[j]-'0'>s[j+1]-'0'){
a++;
char k=s[j];
s[j]=s[j+1];
s[j+1]=k;
}
}
}
return a;
}
char* init(char a[26],char s[26]){
char m[26];
for(int i=0;i<26;i++){
a[i]=s[25-i];
m[i]=a[i];
}
return m;
}
08 等差素数列
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果
输出即可。
2,3,5,7,11,13,……是素数序列。类似:7,37,67,97,127,157这
样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为30,长度为6。
2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数
列。这是数论领域一项惊人的成果!
有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:
长度为10的等差素数列,其公差最小值是多少?
#include <stdio.h>
int main()
{
printf("210"); 对于长度为k的素数等差数列,它们的公差能被小于k的所有素数整除。故为2*3*5*7=210
}
#include <iostream>
using namespace std;
bool Sushu(int n){
for(int i=2;i<n/2;i++)
{
if(n%i==0)
return false;
}
return true;
}
int main()
{
for(int i=2;i<1000000;i++){
if(Sushu(i)){
for(int k=1;k<10000;k++){
if(Sushu(i+1*k)&&Sushu(i+2*k)&&Sushu(i+3*k)&&Sushu(i+4*k)&&Sushu(i+5*k)&&Sushu(i+6*k)&&Sushu(i+7*k)&&Sushu(i+8*k)&&Sushu(i+9*k))
{
cout<<k;
return 0;
}
}
}
}
return 0;
}
09 七段码
题目描述
小蓝要用七段码数码管来表示一种特殊的文字
文章来源:https://www.uudwc.com/A/ZGDnx/
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
// 请在此输入您的代码
int sum = 0;
//有一段二极管发光; a,b,c,d,e,f,g
int l1 = 7;
//有两段二极管发光; ab,af,bc,bg,cg,cd,de,eg,ef,fg
int l2 = 10;
//有三段二极管发光; abf,abc,abg,afg,afe,bcd,bcg,bgf,bge,cgd,cgf,cge,cde,cdg,deg,def,efg
int l3 = 16;//
//有四段二极管发光; abcd,abcg,abcf,abge,abgf,abfe,afeg,bcde,bcdg,bcgf,bcge,bged,bgef,cdef,cdeg,cdgf,cgfa,cgfe,defg,defa
int l4 = 20;
//有五段二极管发光即有两端不发光; ab,ac,ad,ae,af,ag,bc,bd,be,bg,cd,cf,cg,de,df,dg,ef,eg,fg
int l5 = 19;//
//有六段二极管发光即有一端不发光; a,b,c,d,e,f,g
int l6 = 7;//(找一段二极管不发光的:)
//第七种情况,全部发光
int l7 = 1;
sum = l1 + l2 + l3 + l4 + l5 + l6 + l7;
printf("%d\n", sum);
return 0;
}
10 三角回文数
文章来源地址https://www.uudwc.com/A/ZGDnx/
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int x=0;//记录三角数
for(int i=1;;i++){//查找三角数
x+=i;
if(x>20220514){//大于20220514,验证是否为回文数
int b=x;
int a=0;
while(b!=0){//将三角数倒置放入a中储存
a=a*10+b%10;
b/=10;
}
if(a==x){//比较a是否等于x,相等说明x为三角回文数
printf("%d",x);
break;
}
a=0;//不是,重置a进入下一次验证
}
}
return 0;
}