2017蓝桥杯C++A组题解集合

总结：蓝桥杯的题目大多数都是暴利或者dfs、bfs解出来的，注意往这上面思考

下面是赛题的链接：https://wenku.baidu.com/view/951dab772a160b4e767f5acfa1c7aa00b52a9d2d.html

然后就是部分试题的答案，有些转载的，仅供参考

一、迷宫

四、方格分割

/*
仔细观察样例数据可以发现，要满足题目所需要求，只需要剪切的线关于图案的中点中心对称。
那么我们可以将格子格子之间接壤的看作边，边与边相交的看作点。则从(3,3)点出发，
找一条边到达图案的外圈，不过值得注意的是，从(3,3)出发的是看错两个人出发，两个人的线路一直是对称。
所以dfs中标记的时候要一步标记两个。最后的结果要除以4，因为题目中说要旋转对称的是同一种。
*/
#include<bits/stdc++.h>
using namespace std;
int visited[10][10];
int ans=0;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
void dfs(int x,int y)
{
    if(x==0||y==0||x==6||y==6)
    {
        ans++;
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(visited[nx][ny])
            continue;
        visited[nx][ny]=1;
        visited[6-nx][6-ny]=1;
        dfs(nx,ny);
        visited[nx][ny]=0;
        visited[6-nx][6-ny]=0;
    }
}
int main()
{
    memset(visited,0,sizeof visited);
    visited[3][3]=1;
    dfs(3,3);
    printf("%d %d\n",ans,ans/4);
}

五、字母组串

f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1)

六、最大公共子串

a[i-1][j-1]+1

七、正则问题

#include <iostream> 
#include<algorithm>  
using namespace std;

string str;
int pos, len;
int dfs()
{
    int xnum = 0, res = 0;
    while (pos < len) {
        if (str[pos] == '(') {
            pos++;
            xnum += dfs();
        }
        else if (str[pos] == ')') {
            pos++;
            break;
        }
        else if (str[pos] == '|') {
            pos++;
            res = max(xnum, res);
            xnum = 0;
        }
        else {
            pos++;
            xnum++;
        }
    }
    res = max(xnum, res);
    return res;
}
int main()
{
    cin >> str;
    int ans = 0;
    len = str.length(), pos = 0;
    ans = dfs();
    cout << ans << endl;
    return 0;

}

八、包子凑数

这道题用到了数论的知识：本题要判断能不能凑出c个包子就相当于判断ax+by=c这个方程的是否有解，根据数论知识我们知道gcd(a,b)如果不等于1，那么凑不出来的c就有无穷多个，代码中的求gcd的函数应该熟记，然后else里面的for循环就是动态规划求出所有参数能凑出的包子数

#include <cstdio>  
using namespace std;

int gcd(int a, int b) 
{
    if (b == 0) 
        return a;
    return gcd(b, a%b);
}

int unit[110], n;
const int N = 10010;
bool sign[N];

int main(){
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &unit[i]);
        int g = unit[0];
        for (int i = 1; i < n; i++)
            g = gcd(g, unit[i]);
        if (g != 1){
            printf("INF\n");
        }
        else{
            sign[0] = true;
            for (int i = 0; i < n; i++){
                for (int j = 0; j + unit[i] < N; j++)
                    if (sign[j])
                        sign[j + unit[i]] = true;
            }
            int count = 0;
            for (int i = 0; i < N - 1; i++){
                if (sign[i] == false)
                    count++;
            }
            printf("%d\n", count);
        }
        return 0;
}

九、分巧克力

#include <cstdio>  
using namespace std;

int n, k, length[100010], wide[100010];

bool chocolate(int x)  //判断正方形边长x时能不能切出大于等于K块
{
    int num = 0, a, b, i;
    for (i = 0; i<n; i++)  //n块巧克力一共能切出num块分给小朋友们
    {
        a = length[i] / x;
        b = wide[i] / x;
        num += a*b;
    }
    if (num >= k)
        return true;
    return false;
}
int main()
{
    int i, low, high;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        low = 1;
        high = 100001;
        for (i = 0; i<n; i++)
            scanf("%d%d", &length[i], &wide[i]);
        while (low<high-1)   //二分搜索找出正方形巧克力边长的最大值
        {
            int mid = (low + high) / 2;
            if (!chocolate(mid))
                high = mid;
            else
                low = mid;
        }
        printf("%d\n", low);
    }
    return 0;
}