[数据结构与算法] 第十二届蓝桥杯C++B组国赛

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 第十二届蓝桥杯C++B组国赛 -> 正文阅读

[数据结构与算法]第十二届蓝桥杯C++B组国赛

总体评价

国赛跟省赛差距感觉还是蛮大的叭。所以说，还是要好好准备的如果想拿国一的话。我觉得重点还是要准备DP，它每年都会至少两道题，所以说准备DP的话受益还是很大的。不聊啦~补题去惹

试题 A: 带宽

200 / 8 = 25

试题 B: 纯质数

这道题暴力直接交肯定会TLE的，虽然本题暴力理论时间复杂度很高，但是因为质数很少，本地评测很快就出来了，最多大概几秒钟。如果采用筛素数的方式， $O (n)$ 时间复杂度就能过。

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 40010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int a[N];
set<int> S = {2, 3, 5, 7};

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

bool check(int x)
{
    while (x)
    {
        int t = x % 10;
        if (!S.count(t))
            return false;
        x /= 10;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    T = 1;
    // cin>>T;
    int n = 20210605;
    int cnt = 0;
    while (T--)
    {
        rep(i, 1, n + 1)
        {
            if (is_prime(i) && check(i)) cnt ++;
        }
    }
    cout << cnt << endl;
    return 0;
}

试题 C: 完全日期

模拟：977

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 40010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
set<int> S = {2004, 2008, 2012, 2016, 2020};
bool is_leaf(int y, int m)
{
    if (m != 2) return false;
    return S.count(y);   
}

bool check(int y, int m, int d)
{
    int x = 0;
    while (y)
    {
        x += y % 10;
        y /= 10;
    }
    while (m)
    {
        x += m % 10;
        m /= 10;
    }
    while (d)
    {
        x += d % 10;
        d /= 10;
    }
    
    int z = sqrt(x);
    return (z * z) == x;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    T = 1;
    // cin>>T;
    int cnt = 0;
    while (T--)
    {
        int y = 2001, m = 1, d = 1;
        while (y <= 2021)
        {
            if (check(y, m, d))
            {
                cnt ++ ;
            }
            d ++;
            if (d > months[m] + is_leaf(y, m))
                m ++ , d = 1;
            if (m > 12)
                m = 1, y ++ ;
        }
    }
    cout << cnt << endl;
    return 0;
}

试题 D: 最小权值

2653631372
这道题关键就是什么时候这课树的根权值最小。这道题我也不是很确定对不对，思路就是如果深度越深，会发现权值承指数增长，我们尽量让深度较小，深度越小就必须每行都摆满就是一个完全二叉树。

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 2200, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll f[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // init();
    int T;
    T = 1;
    //cin>>T;
    while (T--)
    {
        int n = 2021;
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        rep(i, 1, n + 1)
        {
            rep(l, 0, i)
            {
                f[i] = min(f[i], 1ll + 2 * f[l] + 
                3 * f[i - l - 1] + l * l * (i - l - 1));
            }
        }
        cout << f[n] << endl;
    }
    return 0;
}

试题 E: 大写

库函数：toupper可以直接用

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 5000, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    T = 1;
    // cin>>T;
    while (T--)
    {
        string s;
        cin >> s;
        rep(i, 0, sz(s))
        {
            s[i] = toupper(s[i]);
        }
        cout << s << endl;
    }
    return 0;
}

试题 F: 123

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 2000001, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll f[N];

ll calc(ll x)
{
    ll l = 0, r = N - 1;
    while (l < r)
    {
        ll mid = l + r + 1 >> 1;
        if ((1 + mid) * mid / 2 <= x)
            l = mid;
        else
            r = mid - 1;
    }
    ll s = f[r];
    x -= (r + 1) * r / 2;
    s += (x + 1) * x / 2;
    return s;
}

void init()
{
    rep(i, 1, N)
        f[i] = f[i - 1] + 1ll * (1 + i) * i / 2;
}

int main()
{
    init();
    int T;
    cin>>T;
    while (T--)
    {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        printf("%lld\n", calc(y) - calc(x - 1));
    }
    return 0;
}

异或变换

这种题肯定是找规律的题目，就是找到第一位对后面的影响什么时候能够消除，先打表暴力枚举循环节，发现最多是16384次，之后就可以暴力了

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 10005, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n;
ll t;
char s[N];
int a[N];

int main()
{
    // init();
    // cin>>T;
    int T = 1;
    while (T--)
    {
        scanf("%d%lld%s", &n, &t, s);
        t %= 16384;
        
        rep(i, 0, n)
            if (s[i] == '1')
                a[i] = 1;
        
        rep(j, 0, t)
        {
            int pre = a[0];
            rep(i, 1, n)
            {
                int t = a[i];
                a[i] ^= pre;
                pre = t;
            }
        }
        rep(i, 0, n)
            printf("%d", a[i]);
    }
    return 0;
}

二进制问题

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 71, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int m, a[N];
ll n;
ll C[N][N];

void init()
{
    C[0][0] = 1;
    rep(i, 1, N)
    {
        C[i][0] = 1;
        rep(j, 1, i + 1)
        {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            //printf("%d %d %lld\n", i, j, C[i][j]);
        }
    }
}

int main()
{
    init();
    // cin>>T;
    int T = 1;
    while (T--)
    {
        scanf("%lld%d", &n, &m);
        n ++;
        
        int len = 0;
        for (; n; n >>= 1)
            a[++ len] = n & 1;
        for (int i = 1, j = len; i < j; i ++ , j -- )
            swap(a[i], a[j]);
        
        ll ans = 0;
        int tot = 0;
        rep(i, 1, len + 1)
        {
            if (a[i])
            {
                ans += C[len - i][m - tot], tot ++ ;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}