devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十二届蓝桥杯国赛 C++ 大学B组 题解_a+b按位处理a和b的每一个二进制位 编程计算a op b的结果 蓝桥杯

作者：我家小花儿 | 2024-05-29 15:25:12

赞

踩

a+b按位处理a和b的每一个二进制位 编程计算a op b的结果 蓝桥杯

目录

A. 带宽

B. 纯质数

C. 完全日期

D. 最小权值

E. 大写

F. 123

G. 异或变换

H. 二进制问题

I. 翻转括号序列

J. 异或三角

前言

因为自己的大意马虎和迷之自信，还有一些其他原因。去年拿国一，又训练了一年反而退步到了国二。总之还是个人原因，不管为人还是处事，一定要谦虚谨慎，不断进取，自我反省。

A. 带宽

在这里插入图片描述
答案

200/8 = 25

B. 纯质数

在这里插入图片描述

答案

1903

代码

先欧拉筛出所有质数，然后对每个数按位判断，注意素数标记数组要把 1 1 1 和 0 0 0 都设置为非素数。

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const int maxn = 3e7 + 10;

vector<int> prime;
bitset<maxn> vis;

void euler() {
    vis.set();
    vis[0] = 0;
    vis[1] = 0;
    for (int i = 2; i < maxn; i++) {
        if (vis[i]) prime.push_back(i);
        for (int j = 0; j < prime.size() && i * prime[j] < maxn; j++) {
            vis[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

bool check(int x) {
    while (x) {
        if (!vis[x % 10]) return 0;
        x /= 10;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int ans = 0;
    euler();
    for (int i = 1; i <= 20210605; i++) {
        if (vis[i] && check(i)) ans++;
    }
    cout << ans << ENDL;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

C. 完全日期

在这里插入图片描述
答案

977

代码

模拟日期一天一天加。老是忘记闰年的判断，实际上只需要记住每四年为闰年，但是世纪年要模400为0才是闰年，例如1900年就不是闰年。

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const int maxn = 2e5 + 10;

int run[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int ping[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int cal(int x) {
    int ans = 0;
    while (x) {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}

bool check(int y, int m, int d) {
    int x = cal(y) + cal(m) + cal(d);
    int q = sqrt(x + 0.5);
    return q * q == x;
}

bool isRun(int y) {
    if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int y = 2001, m = 1, d = 1, cnt = 0;
    while (1) {
        if (y == 2022) break;
        if (check(y, m, d)) cnt++;
        if (isRun(y)) {
            if (d == run[m]) {
                d = 1;
                if (m == 12) m = 1, y++;
                else m++;
            } else d++;
        } else {
            if (d == ping[m]) {
                d = 1;
                if (m == 12) m = 1, y++;
                else m++;
            } else d++;
        }
    }
    cout << cnt << ENDL;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

D. 最小权值

在这里插入图片描述
答案

2653631372

代码

这题实际上是一个DP，递归的想每个点的权值只和左右子树的节点个数有关，因此可以写记忆化搜索， d [ i ] = i n f , d [ 0 ] = 0 d[i] = inf,d[0] = 0 d[i]=inf,d[0]=0。

当前子树下需要放置 x x x 个节点，那么当前节点放一个，枚举左子树放置 i ( 0 ≤ i < x ) i(0 \leq i < x) i(0≤i<x) 个，那么右子树放置的个数为 x − 1 − i x - 1 - i x−1−i，状态转移方程为 d [ x ] = m i n ( d [ x ] , d [ x ] ∗ 2 + d [ x − 1 − i ] ∗ 3 + i ∗ i ∗ ( x − 1 − i ) d[x] = min(d[x], d[x] * 2 + d[x - 1 - i] * 3 + i*i*(x - 1 - i) d[x]=min(d[x],d[x]∗2+d[x−1−i]∗3+i∗i∗(x−1−i)。

时间复杂度 O ( n 2 ) O(n^2) O(n2)

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

ll d[3000];

ll dfs(int x) {
    if (d[x] != INF) return d[x];
    ll ans = d[x];
    for (int i = 0; i < x; i++) {
        ans = min(ans, 1LL + dfs(i) * 2 + dfs(x - 1 - i) * 3 + 1LL * i * i * (x - 1 - i));
    }
    return d[x] = ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (int i = 1; i <= 2021; i++) d[i] = INF;
    cout << dfs(2021) << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

E. 大写

在这里插入图片描述
代码

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    char c;
    while (cin >> c) cout << (char) toupper(c);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

F. 123

在这里插入图片描述在这里插入图片描述
思路

根据前缀和得出区间之和为 s u m [ r ] − s u m [ l − 1 ] sum[r] - sum[l-1] sum[r]−sum[l−1]。

题目明显是分段来求的，具体来说是将序列看做 { 1 } , { 1 , 2 } , { 1 , 2 , 3 } , { 1 , 2 , 3 , 4 } , . . . \{1\},\{1,2\},\{1,2,3\}, \{1,2,3,4\},... {1},{1,2},{1,2,3},{1,2,3,4},...

其中每一块的长度刚好是 1 , 2 , 3 , 4... 1,2,3,4... 1,2,3,4...，而每一块的所有元素之和是 1 , 3 , 6 , 10... 1,3,6,10... 1,3,6,10...，每块元素之和的前缀和为 p r e [ i ] = { 1 , 4 , 10 , 20... } pre[i] = \{1,4,10,20...\} pre[i]={1,4,10,20...}，这个前缀和的第 i i i 项刚好对应了组合数 C i + 2 3 C_{i + 2}^3 Ci+23​。

因此思路就很明确了，二分确定前面有多少个完整的块，然后 O ( 1 ) O(1) O(1) 算出这些块的和，最后拿 n n n 减去前面块的元素个数，得到的一定是一个新的块中的从1开始的连续若干个自然数，根据等差数列公式 n ( n + 1 ) 2 \frac{n(n + 1)}{2} 2n(n+1)​即可求出，累加上述二者即可。

代码

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

ll cal1(ll n) {
    return n * (n + 1) * (n + 2) / 6;
}

ll cal2(ll n) {
    return n * (n + 1) / 2;
}

ll getSeg(ll n) {
    ll l = 1, r = 1e9, mid, ans;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (cal2(mid) <= n) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

ll solve(ll n) {
    if (n == 0) return 0;
    ll s = getSeg(n);
    return cal2(n - cal2(s)) + cal1(s);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    ll l, r;
    cin >> T;
    while (T--) {
        cin >> l >> r;
        cout << solve(r) - solve(l - 1) << ENDL;
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

G. 异或变换

在这里插入图片描述
在这里插入图片描述
思路

正解目前不会，网上也没找到讲解，但是暴力能拿80%的分，首先随机01串打表发现对于长度为 n n n 的01串，其周期为大于等于它的最小的2的幂次。因此 n ≤ 1000 n \leq 1000 n≤1000时周期最大为1024，可以暴力。

代码

b i t s e t bitset bitset最右位下标为0。

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

bitset<1005> a;
map<string, bool> mp;
string res[10005];

void table() {
    srand(time(0));
    int n = rand() % 1000 + 1;
    string s = "";
    for (int i = 0; i < n; i++) a[i] = rand() % 2, s += '0' + a[i];
    mp[s] = 1;
    int T = 0;
    while (1) {
        T++;
        bitset<1005> b = a;
        b >>= 1;
        a ^= b;
        s = "";
        for (int i = n - 1; i >= 0; i--) s += '0' + a[i];
        if (mp.count(s)) break;
    }
    cout << n << " " << T << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    table();
    int n;
    ll t;
    string s = "";
    cin >> n >> t;
    cin >> s;
    for (int i = n - 1, x, j = 0; i >= 0; i--, j++) {
        x = s[j] - '0';
        if (x) a.set(i);
    }
    mp[s] = 1;
    int T = 0;
    while (1) {
        res[T++] = s;
        bitset<1005> b = a;
        b >>= 1;
        a ^= b;
        s = "";
        for (int i = n - 1; i >= 0; i--) s += '0' + a[i];
        if (mp.count(s)) break;
    }
//    cout << T << endl;
    t %= T;
    cout << res[t] << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

H. 二进制问题

在这里插入图片描述
思路

最裸的数位DP了。

代码

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

ll d[105][55][2];
int digit[105];
int k;

ll dfs(int pos, int sum, bool flag) {
    if (pos == 0) return sum == k;
    if (d[pos][sum][flag] != -1) return d[pos][sum][flag];
    int up = flag ? digit[pos] : 1;
    ll ans = 0;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos - 1, sum + (i == 1), flag & (i == up));
    }
    return d[pos][sum][flag] = ans;
}

ll solve(ll n) {
    int len = 0;
    while (n) {
        digit[++len] = n & 1;
        n /= 2;
    }
    memset(d, -1, sizeof d);
    return dfs(len, 0, 1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n;
    cin >> n >> k;
    cout << solve(n) << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

I. 翻转括号序列

在这里插入图片描述
在这里插入图片描述

思路

暴力可拿20%

代码

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

char s[maxn];
int n;

int solve(int x) {
    stack<char> st;
    int ans = 0;
    for (int i = x; i <= n; i++) {
        if (s[i] == '(') st.push(s[i]);
        else {
            if (st.size()) st.pop();
            else return ans;
            if (st.empty()) ans = i;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int m;
    char ch;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> ch;
        s[i] = ch;
    }
    int op, l, r;
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> l >> r;
            for (int i = l; i <= r; i++) s[i] = (s[i] == '(' ? ')' : '(');
        } else {
            cin >> l;
            cout << solve(l) << ENDL;
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

J. 异或三角

在这里插入图片描述
在这里插入图片描述

思路

根据异或的性质一个数异或它本身得0，可拿20%

代码

#include <bits/stdc++.h>

using namespace std;
#define ENDL "\n"
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

bool check(int i, int j, int k) {
    int a[3];
    a[0] = i, a[1] = j, a[2] = k;
    sort(a, a + 3);
    return a[0] + a[1] > a[2];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        int ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1, k; j <= n; j++) {
                k = i ^ j;
                if (1 <= k && k <= n && check(i, j, k)) {
                    //cout << i << " " << j << " " << k << ENDL;
                    ans++;
                }
            }
        cout << ans << ENDL;
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/642900
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号