[C++知识库]第十二届蓝桥杯C/C++ A组省赛 题解（更新至D题）

A题：卡片

题面：

思路：

用一个一维数组保存卡片数量，数组的下标对应数字卡片。从1开始遍历，对于当前数字，尝试用剩余卡片组成，如果不能组成，则答案是上一位数字。

实现：

#include <iostream>

using namespace std;

const int N = 10;
int a[N];

int main()
{
    for(int i = 0; i <= 9; i++) a[i] = 2021;

    int cnt = 1;
    bool flag = true;
    while(flag)
    {
        int x = cnt;
        while(x)
        {
            if(a[x % 10] > 0) a[x % 10]--;
            else
            {
                cout << cnt - 1 << endl;
                flag = false;
                break;
            }
            x /= 10;
        }

        if(!flag) break;

        cnt++;
    }

    return 0;
}

答案：3181

B题：直线

题面

?

思路

计算两点的斜率和纵截距，两者都相同的记为一条直线（这里没有出现精度损失的问题，可能题目数据要求不高，故不作特殊处理）

实现

#include <iostream>
#include <map>
#include <utility>
#include <vector>

using namespace std;

const int X = 20, Y = 21;

int main()
{
    vector<pair<int, int>> vec;
    for(int i = 0; i < X; i++)
        for(int j = 0; j < Y; j++)
            vec.push_back({i, j});

    map<pair<double, double>, bool> ma;
    for(int i = 0; i < vec.size(); i++)//从这些数中任意两个数，不允许重复
        for(int j = i + 1; j < vec.size(); j++)
        {
            int x1 = vec[i].first, x2 = vec[j].first;
            int y1 = vec[i].second, y2 = vec[j].second;
            if(x1 != x2 && y1 != y2)//排除斜率为0和斜率无穷大的情况
            {
                double k, b;//两点式推导出来的斜率和纵截距计算公式
                k = double(y2 - y1) / (x2 - x1);
                b = double(x1 * y2 - x2 * y1) / (x1 - x2);

                if(!ma[{k, b}]) ma[{k, b}] = true;
            }
        }

    //最后结果要加上斜率为0和斜率无穷大的直线
    cout << ma.size() + X + Y  << endl;

    return 0;
}

答案：40257

C题：货物摆放

题面

思路

由题可知，摆放成长方体的长宽高，必须是202104180418的因数，否者无法构成长方体。求出这个数的所有因数，再用三重循环找出可能解

实现

#include <iostream>
#include <vector>

using namespace std;
const long long NUM = 2021041820210418;
int main()
{
    vector<long long> vec;

    for(int i = 1; i < NUM / i; i++)
        if(NUM % i == 0)
            vec.push_back(i), vec.push_back(NUM / i);

    int ans = 0;
    for(int i = 0; i < vec.size(); i++)
        for(int j = 0; j < vec.size(); j++)
            for(int k = 0; k < vec.size(); k++)
                if(vec[i] * vec[j] * vec[k] == NUM) ans++;

    cout << ans << endl;

    return 0;
}

答案：2430

D题：路径

题面

思路

按照题目要求，利用二维的路径矩阵存储边权，由于是无向边，所以要存储 i 到 j 和 j 到 i，然后用dijkstra求最短路径。

实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//辗转相除法求最大公约数
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

//最小公倍数
int stimes(int a, int b) { return a * b / gcd(a, b); }

const int N = 2022, M = 22;
int g[N][N], dist[N];//g是路径矩阵，dist是1到其它点的距离
bool st[N];//表示该点是否使用

void dijkstra()
{
    dist[1] = 0;
    for(int i = 1; i < N; i++)
    {
        int t = -1;
        for(int j = 1; j < N; j++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        //用选中的点更新其它点
        for(int j = 1; j < N; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main()
{
    memset(dist, 0x3f, sizeof dist);
    memset(g, 0x3f, sizeof g);

    //构建无向边
    for(int i = 1; i < N; i++)
        for(int j = i + 1; j < N && j - i < M; j++)
            g[i][j] = g[j][i] = stimes(i, j);

    dijkstra();

    cout << dist[2021] << endl;

    return 0;
}

答案：10266837