首页 💻 数据结构,📝 算法学习

写在前面: 4月18日举办了今年的蓝桥杯, 水了个省一 , 弥补了去年没参加的遗憾, 下面来看一下本届的题目

题目 PDF 下载链接

第十二届蓝桥杯大赛软件赛省赛_CB.pdf


试题A、空间

展开查看详情

题目传送门

暂无

题意

计算256MB空间可以放下多少32位整数

思路

256 * 1024 * 1024 / 4

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << 256 * 1024 * 1024 / 4 << endl;

    return 0;
}

答案: 67108864

试题B、卡片

展开查看详情

题目传送门

暂无

题意

0~9这十个数字每个数字给2021张卡片, 问最多能拼多少个数字

思路

设一个数组存每个数字的卡片个数, 每用一个就减一, 直到为零为止

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans = 1, a[10];

bool judge(ll x){
    while(x){
        if(a[x % 10] <= 0) return false;
        a[x % 10]--; x /= 10;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(ll i = 0; i < 10; i++) a[i] = 2021;
    while(true){
        if(!judge(ans)) break;
        ans++;
    }
    cout << ans - 1 << endl;

    return 0;
}

答案: 3181

试题C、直线

展开查看详情

题目传送门

暂无

题意

坐标轴上的20 * 21个点一共可以确定多少条不同的直线

思路

根据直线公式 $y = kx + b$ 计算任意两点组成直线的 $k$ 和 $b$ 的值, 然后去重即可(注意精度问题)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<double, double>> v;
ll ans = 1;

bool cmp(pair<double, double> x, pair<double, double> y){
    if(x.first != y.first) return x.first < y.first;
    else return x.second < y.second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(ll i = 0; i < 20; i++){
        for(ll j = 0; j < 21; j++){
            for(ll k = 0; k < 20; k++){
                for(ll h = 0; h < 21; h++){
                    if(k == i) continue;
                    double K = (double)(h - j) / (k - i);
                    double B = j - K * i;
                    v.push_back({K, B});
                }
            }
        }
    }
    sort(v.begin(), v.end(), cmp);
    for(ll i = 1; i < v.size(); i++)
        if(fabs(v[i].first - v[i - 1].first) > 1e-8 || fabs(v[i].second - v[i - 1].second) > 1e-8)
            ans++;
    cout << ans + 20 << endl;

    return 0;
}

答案: 40257

试题D、货物摆放

展开查看详情

题目传送门

暂无

题意

计算2021041820210418拆分成 $a * b * c$ 的形式有多少种不同的方式

思路

求出2021041820210418所有的因数, 然后三重循环遍历这些因数即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans, n = 2021041820210418;
unordered_set<ll> st;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(ll i = 1; i * i <= n; i++) if(n % i == 0) st.insert(i), st.insert(n / i);
    for(auto it : st) for(auto jt : st) for(auto kt : st) if(it * jt * kt == n) ans++;
    cout << ans << endl;

    return 0;
}

答案: 2430

试题E、路径

展开查看详情

题目传送门

暂无

题意

按题意建出一张图, 并求1~2021的最短路

思路

邻接表建图跑Dijkstra即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 3e3 + 5;
vector<pair<ll, ll>> edge[maxn];
priority_queue<pair<ll, ll>> q;
ll d[maxn], vis[maxn];

void dijkstra(ll s, ll e){
    memset(d, 0x3f, sizeof(d));
    q.push({-d[s], s}); d[s] = 0;
    while(!q.empty()){
        auto head = q.top();
        q.pop();
        if(vis[head.second]) continue;
        vis[head.second] = 1;
        for(auto it : edge[head.second]){
            if(d[it.first] > d[head.second] + it.second){
                d[it.first] = d[head.second] + it.second;
                q.push({-d[it.first], it.first});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(ll i = 1; i <= 2021; i++)
        for(ll j = i + 1; j <= 2021; j++)
            if(abs(i - j) <= 21)
                edge[i].push_back({j, i * j / __gcd(i, j)}),
                edge[j].push_back({i, i * j / __gcd(i, j)});
    dijkstra(1, 2021);
    cout << d[2021] << endl;
    
    return 0;
}

答案: 10266837




文章评论

    小白 访客ChromeAndroid
    2021-05-26 10:30   回复

    大佬省几

      我爱喝旺仔 站长ChromeWindows
      2021-05-26 10:43   回复

      弱省的蒟蒻省一

        小白 访客ChromeWindows
        2021-05-30 15:22   回复

        我辣鸡py省三

          我爱喝旺仔 站长ChromeWindows
          2021-05-31 13:26   回复

          加油,明年还是有机会的!