前言

距离蓝桥杯还剩短短俩个月的时间，最后的号角已经吹响，没有撤退可言!

最后的时间如果要彻底的搞懂比赛所需的算法，很难，但是最后的成绩可能也不是很好，所以我们用真题+解析的形式来做最后的冲刺！

话不多说，开启我们的第二天！

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;
}

最后

今天我们就刷这几个题，题不算难，但是都是真题，坚持下去，时间会给出答案！