2021年蓝桥杯题目整理

空间

第一题考了一个空间对应int型数据能存多少个

256mb可以存多少32位的数据 答案：1byte = 8bit 所以256 * 1024 * 256 = 67108864

卡片

第二题考得是一个模拟

#include "iostream"
using namespace std;
int main()
{
    int a[10] = { 2021,2021,2021,2021,2021,2021,2021,2021,2021,2021 };
    int num = 0;
    int flag = 1;
    while (flag)
    {

        num++;
        int t = num;
        while (t)
        {
            a[t % 10]--;
            if (a[t % 10] == 0)flag = 0;
            t /= 10;
        }
    }
    cout << num;
    return 0;
}
答案：3181

直线

第三题考了一个连直线的问题 说是一个n*m列阵里面连直线，可以连多少条 问的是20*21 给的条件是2*3时有11条

思路：每条不同的直线方程为ax+by+c=0,只要a,b,c（除以最小公约数）不一样就是不同的直线，


#include "iostream"
#include <vector>
#include <queue>
using namespace std;
int dp[25][25];
struct Node {
    int a;
    int b;
    int c;
    Node(int a1, int b1, int c1)
    {
        a = a1;
        b = b1;
        c = c1;
    }
};//三元组定义
vector<Node>res;

bool find(Node num)//查找当前res中有没有新加入的三元组
{
    for (int i = 0; i < res.size(); i++)
    {
        if (res[i].a == num.a&&res[i].b==num.b&&res[i].c==num.c)return true;
    }
    return false;
}
int gcd(int x, int y)
{
    return !y ? x : gcd(y, x%y);
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n * m; i++)//减少循环次数，用i*j来区分行和列，遍历每个点
    {
        double x, y;
        x = i % n;
        y = (i-1) / n+1;//得出第一个点
        for (int j = i; j <= n * m; j++)
        {
            if (x == 0)x = n;
             double x1, y1;
             x1 = j % n;
             double k=0;
             y1 = (j-1) / n+1;
             if (x1 == 0)x1 = n;//得出第二个点

             int a=0, b=0, c=0,t=0;
             if (x != x1 && y != y1)
             {
                a = y1 - y;
                b = (x1 - x);
                c = (y - y1) * x1 + (x1 - x) * y;//两点确定一条直线的公式

                t = gcd(a, b);
                 if (c % t == 0) {
                     a /= t;
                     b /= t;
                     c /= t;
                 }//最下公约数，确保不重合
             }
                Node* n = new Node(a, b, c);

            if(!(n->a==0&&n->b==0&&n->c==0)&&!find(*n))
                 res.push_back(*n);
        }
    }
    cout << res.size()+n+m;
    return 0;
}
答案40257

货物摆放

第四题问一个数分成3个数相乘有多少种分法

思路：先取出所有的因子然后循环因子，记得开longlong

#include <iostream>
using namespace std;
typedef long long ll;
ll s[100005]; int index = 0;
int an = 0;
int main()
{
    ll a = 2021041820210418;
    ll cur = sqrt(a);//因子不会超过其平方，减少循环次数
    for (ll i = 1; i <= cur; i++)
    {
        if (a % i == 0) {
            s[index++] = i; s[index++] = a / i;//加入因子
        }
    }
    for (int i = 0; i < index; i++)
    {
        for (int j = 0; j < index; j++)
        {
            for (int k = 0; k < index; k++)
            {
                if (s[i] * s[j] * s[k] == a)an++;
            }

        }
    }
    cout << an;
    return 0;
}
答案2430

最短路径

第五题叫求最短路径，说是总共2021个节点，一个节点到另一个小于自己21的有最小公倍数的距离

思路:先填入数据,你要找里面的最小值，要先把数组全部赋值为无穷大0x3f，然后Floyd

#include <iostream>
using namespace std;

const int n = 2021;
int gcd(int x, int y)
{
    return !y ? x : gcd(y, x % y);
}
int dp[n + 5][n + 5];
int main()
{

    memset(dp, 0x3f, sizeof dp);//关键,填入无穷大
    for (int i = 1; i <= n; i++)
    {
        dp[i][i] = 0;
        for (int j = 1; j <= 21; j++)
        {
            dp[i + j][i] = dp[i][i + j] = (i * (i + j)) / gcd(i, i + j);//填入数据

        }
    }
    for (int k = 1; k <= n; k++)//floyd算法
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dp[i][k] + dp[k][j] < dp[i][j]) {//算小值现附上最大值
                    dp[i][j] = dp[i][k] + dp[k][j];//i-j的距离=i-k+k-j
                }

    cout << dp[1][n];
    return 0;
}

答案10266837

砝码称重

dfs就完事了

思路:砝码只有三种状态，在左边，在右边，没放上去，我们深度搜索遍历所有情况，最后取绝对值就是可以量出来的数

输入数据:3 1 4 6 输出:10

#include <iostream>
using namespace std;
int ans = 0;
int a[1005];
int b[1005];
int c[1005];
int n;
int sumz = 0;//左边砝码重量
int sumy = 0;//右边砝码重量
int sum = 0;
void dfs(int u)
{
    if (u == n) {//放完砝码跳出
        c[abs(sumy - sumz)] = 1;//将能称出来的数据置1
        sumy = 0;
        sumz = 0;
        return;
    }

    for (int k = 0; k < 3; k++)
    {
        b[u] = k;
        for (int j = 0; j < n; j++)
        {
            if (b[j] == 1)sumy += a[j];
            if (b[j] == 2)sumz += a[j];
        }
        dfs(u + 1);

    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];//算出最大的循换次数
    }
    dfs(0);
    for (int i = 0; i < sum; i++)
    {
        if (c[i] == 1)ans++;//算所有能出来的重量
    }

    cout << ans;
    return 0;
}

杨辉三角形

第八题考了个杨辉三角求数字出现的位置，考试的时候我直接暴力了，应该不能全对，现在也没有更好的思路

思路:应该要退公式，推不来，直接暴力骗分

#include<iostream>
using namespace std;
int a[1005][10005];
int b[100000005]; int t = 0;
void input()//将杨辉三角放到一个一维数组
{
    for (int i = 0; i < 1000; i++)
    {
        a[i][0] = 1;
        a[i][i] = 1;
    }
    for (int i = 2; i < 1000; i++)
        for (int j = 1; j < i; j++)
        {
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
        }
}
int main()
{
    int m;
    cin >> m;
    input();
    for (int i = 0; i < 1000; i++)
        for (int j = 0; j <= i; j++)
        {
            b[t++] = a[i][j];
        }
    for (int i = 0; i < t; i++)
    {
        if (b[i] == m) { cout << i + 1; break; }
    }
    return 0;
}

双向排序

第九题考的是排序，说实话有点简单用stl库就可以写

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        a[i] = i + 1;
    }
    for (int i = 0; i < m; i++)
    {
        int p, q;
        cin >> p >> q;
        if (p == 1)
        {
            sort(a + q - 1, a + n);
        }
        if (p == 0)
        {
            sort(a, a + q, greater<int>());
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

括号序列

第十题是括号配对的题dFS我感觉能解

思路:先算出左括号和右括号的差值，然后就知道要补什么符号，之后dfs，将每种的出来的括号序列存unordered_map,如果以前存过就不存这一种，我写的不能全对，望赐教

#include <iostream>
#include <unordered_map>
using namespace std;
string start;
unordered_map<string,int>mp;
int z = 0;
int y = 0;
int n = 0;
char ch;
int ans = 0;
bool is(string t)//判断是不是一个正确的括号序列
{
    int temp = 0;
    int fl = 0;
    vector<bool>flag(t.length());//设一个数组存每一个括号，如果括号有对应的就把这个bool数组两个位置都射程true，如果最后所有都是true，那么就是一个正确的括号序列
    for (int i = 0; i < t.length(); i++)
    {
        if (t[i] == '('&&flag[i]==false) {
            int k = i;
            fl = 0;
            for (int j = k; j < t.length(); j++)
            {
                if (t[j] == ')'&&flag[j]==false) {
                    temp = j; fl = 1; break;
                }
            }
            if(fl==1)
            flag[k] = true;
            flag[temp] = true;
        }
    }
    for (int i = 0; i < t.length(); i++)
    {
        if (flag[i] == false)
        {
            return false;
        }
    }
    return true;
}
void dfs(int u,string t)//层数为两种括号的差值
{
    t = start;
    if (u == n) {
        if (mp.count(t) == 0 && is(t))ans++;
        mp[t] = 1; return;
    }
    int len = start.length();
    for (int i = 0; i < len; i++)
    {
        start.insert(i,1, ch);
        dfs(u + 1, t);
        start.erase(i, 1);
    }
    return;
}
int main()
{
    cin >> start;
    for (int i = 0; i < start.length(); i++)
    {
        if (start[i] == '(')z++;
        if (start[i] == ')')y++;
    }
    n = abs(z - y);
    if (z > y)ch = ')';
    else
    {
        ch = ')';//判断要添加的是左括号还是右括号
    }

    dfs(0, start);
    /*if (is("(("))cout << 123;*/
    cout << ans%100000007;
}