文章目录
前言
距离蓝桥杯还剩短短俩个月的时间，最后的号角已经吹响，没有撤退可言!
最后的时间如果要彻底的搞懂比赛所需的算法，很难，但是最后的成绩可能也不是很好，所以我们用真题+解析的形式来做最后的冲刺！
话不多说，开启我们的第二天！
2015b 九数组分数（DFS）
1,2,3…9 这九个数字组成一个分数，其值恰好为1/3，如何组法？
下面的程序实现了该功能，请填写划线部分缺失的代码。
一道填空题，DFS回溯问题，下面我们来看他给出的代码
#include <stdio.h>
void test(int x[]) {
int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
if(a*3 == b) printf("%d / %d\n", a, b);
}
void f(int x[], int k) {
int i,t;
if(k>=9){
test(x);
return;
}
for(i=k; i<9; i++) {
{t=x[k]; x[k]=x[i]; x[i]=t;}
f(x,k+1);
___________________// 填空处
}
}
int main() {
int x[] = {1,2,3,4,5,6,7,8,9};
f(x,0);
return 0;
}
不难，代码如下，抽时间专门写一下dfs和bfs的专题
{t=x[k]; x[k]=x[i]; x[i]=t;}
2015b 加法变乘法
我们都知道：1+2+3+ … + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015
比如：
1+2+3+…+1011+12+…+2728+29+…+49 = 2015
就是符合要求的答案。
请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。
注意：需要你提交的是一个整数，不要填写任何多余的内容。
代码题的第一个还是比较简单的，俩个for循环来写，值得注意的是第二个for不要从1开始写，从第一个for的下一位开始写
#include<iostream>
using namespace std;
int main() {
for(int i = 1; i<=48; i++)
for (int j = i + 1; j <= 48; j++) {
if (i == j) continue;
//ans转换俩次
int ans = 1225 - 2 * i - 2 * j - 2;
ans = ans + i * (i + 1) + j * (j + 1);
if (ans == 2015) {
printf("%d\n", i);
}
}
return 0;
}
输出为10和16，案例中为10，所以答案为16，要改变一下，应该给if中加条件
if (ans == 2015 && i != 10)
2015b 我被挟持了
标题开了个玩笑，是.牌型种数
小明被劫持到X赌城，*与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
请填写该整数，不要填写任何多余的内容或说明文字。
没有时间限制，我们可以暴力枚举每一张牌拿的张数，最后判断手里是不是13张。
#include<iostream>
using namespace std;
int a[14], ans;
int main() {
for (a[1] = 0; a[1] <= 4; ++a[1])
for (a[2] = 0; a[2] <= 4; ++a[2])
for (a[3] = 0; a[3] <= 4; ++a[3])
for (a[4] = 0; a[4] <= 4; ++a[4])
for (a[5] = 0; a[5] <= 4; ++a[5])
for (a[6] = 0; a[6] <= 4; ++a[6])
for (a[7] = 0; a[7] <= 4; ++a[7])
for (a[8] = 0; a[8] <= 4; ++a[8])
for (a[9] = 0; a[9] <= 4; ++a[9])
for (a[10] = 0; a[10] <= 4; ++a[10])
for (a[11] = 0; a[11] <= 4; ++a[11])
for (a[12] = 0; a[12] <= 4; ++a[12])
for (a[13] = 0; a[13] <= 4; ++a[13]) {
int t = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9] + a[10] + a[11] + a[12] + a[13];
if (t == 13) ans++;
}
printf("%d\n", ans);
return 0;
}
DFS也能写
#include <bits/stdc++.h>
using namespace std;
int cnt;
void dfs(int i, int j) { // 发到第 i种牌 手里有 j张
if(i > 13) return;
if(j > 13) return; // 剪枝 当手里的牌数大于13张时，肯定不符合。
if(j == 13) {
cnt ++;
return ;
}
dfs(i+1, j);
dfs(i+1, j+1);
dfs(i+1, j+2);
dfs(i+1, j+3);
dfs(i+1, j+4);
}
int main() {
dfs(0, 0);
printf("%d\n", cnt);
return 0;
}
最后
今天我们就刷这几个题，题不算难，但是都是真题，坚持下去，时间会给出答案！