专栏: 蓝桥杯——每日四道填空题(两道真题+两道模拟题)
&离蓝桥杯已经不到一个月时间了,赶快刷起来吧,填空题一定别丢分!!
୧꒰•̀ᴗ•́꒱୨
另一个专栏是: 蓝桥杯——编程题刷题营(每日四题,两道模拟,两道真题)
目录
第一道真题(2016年省赛):寒假作业 | 答案:64
第二道真题(2019年省赛):质数 | 答案:17569
第三道模拟题(2022年第二次模拟赛): 拆分质数个数 |答案:33
第四道模拟题():答案:10
第一道真题(2016年省赛):寒假作业 | 答案:64
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。现在小学的数学题目也不是那么好玩的。 看看这个寒假作业:
□ + □ = □ □ - □ = □ □ × □ = □ □ ÷ □ = □
每个方块代表 1~13 中的某一个数字,但不能重复。
比如:
6 + 7 = 13 9 - 8 = 1 3 * 4 = 12 10 / 2 = 5
以及:
7 + 6 = 13 9 - 8 = 1 3 * 4 = 12 10 / 2 = 5
就算两种解法。(加法,乘法交换律后算不同的方案)
你一共找到了多少种方案?
运行限制
最大运行时间:1s
最大运行内存: 128M
怎么说呢,dfs 应该是我首选,毕竟是填空题。
但是这题要注意,除法 ' / ' c++是整除的,但实际上3 / 2 != 1,是1.5。
#include<iostream>
using namespace std;
int b[20] , t = 13 ; //b[]存储每次选中的值,
long long ans=0;
bool used[20]; //选中的,要排除掉,避免重复使用。
void dfs(int s){
if(s==13){ //已经到了最后一个数了,说明已经选择好了一种方案。
ans++;
return;
}
if(s==3 && b[0]+b[1]!=b[2]) return; //加法已经选入后,看是否满足条件
if(s==6 && b[3]-b[4]!=b[5]) return;
if(s==9 && b[6]*b[7]!=b[8]) return;
if(s==12 && (double)b[9] / b[10] != b[11]) return; //注意转成浮点数计算,才是真真的除法。
for(int i=0;i<t;i++){
if(!used[i]){
used[i]=true;
b[s]=i+1; //选中的值属于[1 , 13]
dfs(s+1);
used[i]=false;}
}
}
int main(){
dfs(0); //从第一个空开始依次填数
cout<<ans<<endl;
return 0;
}
这题如果数学好,可以仔细手数,因为数据也不是很大。
# 6 + 7 = 13 变形:7+6=13 13-7=6 13-6=7
# 9 - 8 = 1 变形:9-1=8 1+8=9 8+1=9
# 3 * 4 = 12 变形:4*3=12 12/4=3 12/3=4
# 10 / 2 = 5 变形:10/5=2 2*5=10 5*2=10
# 加法:6+7=13 7+6=13 1+8=9 8+1=9
# 减法:9-8=1 9-1=8 13-7=6 13-6=7
# 乘法:3*4=12 4*3=12 2*5=10 5*2=10
# 除法:10/2=5 10/5=2 12/4=3 12/3=4
# 6,7,13 组合:2*2*4*2 = 32
# 1,8,9 组合:同上
#所以:
printf("64");
第二道真题(2019年省赛):质数 | 答案:17569
找了一道真题,复习一下质数的判断。
质数:只能被1和自身整除的数。
首先是最容易理解的方法(耗时):
#include <iostream>
using namespace std;
int main()
{
int num=3;//前三个为2,3,5
for (int i = 6 ; ; i++){//从6开始判断
int flag = 1;
for (int j = 2 ; j < i ; j++){
if (i%j == 0){
flag = 0;
break;
}
}
if (flag == 1){
num ++;
}
if(num == 2019){
cout<<i<<endl;
break;
}
}
return 0;
}
优化:孪生素数法(高效)
当然这里只是一道填空题,但是如果是编程题,还是有必要掌握这个方法的。
#include<iostream>
#include<cmath>
using namespace std;
bool is_prime(int num)
{
if (num == 2 || num == 3)
return true;
if (num % 6 != 1 && num % 6 != 5) //不在6的倍数的两侧一定不是素数
return false;
for (int i = 5; i <= sqrt(num); i += 6)
if (num % i == 0 || num % (i + 2) == 0)//在6的倍数两侧并不是一定就是质数,还要特判一下哦
return false;
return true;
}
int main()
{
int i = 2; //素数
int cnt = 0; //数量
while(true)
{
if(is_prime(i))
{
cnt++;
}
if(cnt == 2019)
{
break;
}
i++;
}
cout << i << endl;
return 0;
}
第三道模拟题(2022年第二次模拟赛): 拆分质数个数 |答案:33
问题描述:
将2022拆分成不同的质数的和,请问最多拆分成几个?
这里我特地找了一道 dfs + 质数判断 的题,练一下吧!
#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
int mp[2023][2023] ;
//为了记录下这条路径后面的“子节点”数量, 如果再次递归到这个父节点就直接返回它后面路径的“子节点个数”
// 不写这个也可以,只是比较浪费时间 ,这样可以节约时间,学到了吗,哈哈!
//bool is_prime(int x) {
// for (int i = 2; i * i <= x; i ++) {
// if (x % i == 0) return false;
// }
// return true;
//}
//或者:
bool is_prime(int num)
{
if (num == 2 || num == 3)
return true;
if (num % 6 != 1 && num % 6 != 5) //不在6的倍数的两侧一定不是素数
return false;
for (int i = 5; i <= sqrt(num); i += 6)
if (num % i == 0 || num % (i + 2) == 0)//在6的倍数两侧并不是一定就是质数,还要特判一下哦
return false;
return true;
}
int dfs(int cur, int idx) {
int mx = 0;
if (cur == 0) return 0;
if (cur < primes[idx]) return -1;
if (mp[cur][idx] != 0) return mp[cur][idx]; //如果这条路径已经查询了,直接返回这条路径 上的节点数目
for (int i = idx; i < primes.size() && cur >= primes[i]; i ++) {
mx = max(mx, 1 + dfs(cur - primes[i], i + 1));
}
mp[cur][idx] = mx; //注意一定要在已经这里才记录下这条路径的子节点数目,因为这条路径不满足上面条件代码才走到这的,
//说明这条路径已经明确了。
return mx;
}
int main() {
for (int i = 2; i <= 2022; i ++) {
if (is_prime(i)) primes.push_back(i);
}
cout << dfs(2022, 0) << endl;
return 0;
}
第四道模拟题(2022年第四次模拟赛):答案:10
贪心思想,每次都尽可能令左子树比右子树多 1 个节点(反之也可),注意根节点是第0层。
//答案 10
#include <bits/stdc++.h>
using namespace std;
int main() {
int cnt = 2021, d = 0;
while (cnt != 1) {
cnt--;
cnt = cnt / 2 + (cnt % 2);
d++;
}
cout << d << endl;
return 0;
}
当然也可以找规律,这是也是我们平时做题重要的思想,毕竟用代码写,和用笔算是两码事。
比如结点数为6,我们画图知道它应该是2层,当结点数是11时,它应该是3层。
你可以大胆的猜测, <= 6 <= ; <= 11 <=
发现,层数和结点数满足上述关系,那么接下来就用一个循环来查找就OK了。文章来源:https://www.toymoban.com/news/detail-400417.html
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
for (int i = 0 ; i <= 31 ; ++i)
{
if(pow(2 , i) <= 2021 && pow(2 , i + 1) >= 2021){
cout<<i<<endl;
break;
}
}
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-400417.html
到了这里,关于【蓝桥杯】每日四道填空题(两道真题+两道模拟题)| 第四天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!