首页 > 其他分享 >2021 年蓝桥杯第一次省赛题目全解答

2021 年蓝桥杯第一次省赛题目全解答

时间：2023-03-29 13:03:00浏览次数：57  
标签：std int ll cin long 蓝桥 ++ 2021 省赛

做题链接：A组 B组 C组

填空题

卡片

直接模拟。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::map<char, int> mp;
    for (int i = 0; i <= 9; i++) {
        mp[i + '0'] = 2021;
    }
    
    for (int i = 1; ; i++) {
        for (char j : std::to_string(i)) {
            if (mp[j] > 0) {
                mp[j] -= 1;
            } else {
                std::cout << i - 1 << '\n';
                std::exit(0);
            }
        }
    }
    return 0;
}

直线

分类讨论：水平、竖直或者是斜着（记下斜率 \(k\) 和截距 \(b\)），注意到给定坐标情况下，使用 std::atan2(y, x) 计算斜率 \(k = \dfrac{y}{x}\)；直线方程使用两点式：

\[\dfrac{y - y_0}{y_1 - y_0} = \dfrac{x - x_0}{x_1 - x_0} \]

从而解出截距 \(b = \dfrac{x_0y_1-x_1y_0}{x_1-x_0}\)。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::vector<std::pair<int, int>> p;
    
    const int n = 20, m = 21;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            p.emplace_back(i, j);
        }
    }
    
    std::set<std::pair<double, double>> s;
    std::set<int> kind[2]{};
    int t = p.size();
    for (int i = 0; i < t; i++) {
        int x_0 = p[i].first, y_0 = p[i].second;
        for (int j = i + 1; j < t; j++) {
            int f = 0;
            int x_1 = p[j].first, y_1 = p[j].second;
            
            if (x_0 == x_1) kind[0].insert(x_0), f++;
            if (y_0 == y_1) kind[1].insert(y_0), f++;
            
            if (f == 0) {
                double k = std::atan2(y_1 - y_0, x_1 - x_0);
                double t = 1. * (x_0 * y_1 - x_1 * y_0) / (x_1 - x_0);
                s.emplace(k, t);
            }
        }
    }
    
    std::cout << kind[0].size() + kind[1].size() + s.size() << '\n';
    
    return 0;
}

货物摆放

即求有多少可重排列，使得 \(n = 2021041820210418 = 2\times3^3\times17\times131\times2857\times5882453 = pqr\)。由隔板法，答案为 \(3!{8 + 3 - 1 \choose 3 - 1} = 2430\)。

路径

\(n = 2000\)，在本机使用 Floyd 跑出结果之后交。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
//    std::cout << 10266837 << '\n';
//    return 0;
    
    const int N = 2021 + 10;
    ll g[N][N]{};
    
    for (int i = 1; i <= 2021; i++) {
        for (int j = 1; j <= 2021; j++) {
            if (std::abs(i - j) <= 21) {
                g[i][j] = g[j][i] = 1ll * i * j / std::__gcd(i, j);
            } else {
                g[i][j] = g[j][i] = 0x3f3f3f3f;
            }
        }
    }
    
    for (int k = 1; k <= 2021; k++) {
        for (int i = 1; i <= 2021; i++) {
            for (int j = 1; j <= 2021; j++) {
                g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    
    std::cout << g[1][2021] << '\n';
    
    return 0;
}

回路计数

即求哈密顿回路数，状压即可。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
//     std::cout << "881012367360" << '\n';
//     return 0;
    
    const int n = 21;
    static std::array<std::array<int, n>, n> g{};
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (std::__gcd(i + 1, j + 1) == 1) {
                g[i][j] = g[j][i] = 1;
            }
        }
    }
    
    static std::array<std::array<ll, n>, 1 << n> f{};
    
    f[1][0] = 1;
    for (int i = 1; i < 1 << n; i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j & 1) && f[i][j]) { // `j` selected
                for (int k = 0; k < n; k++) {
                    if (((i ^ (1 << j)) >> k & 1) && g[k][j]) {
                        f[i][j] += f[i ^ (1 << j)][k];
                    }
                }
            }
        }
    }
    
    std::cout << std::accumulate(f.back().begin(), f.back().end(), 0ll) << '\n';
    
    return 0;
}

空间

\(1 \mathrm{Byte} = 8 \mathrm{bit}s\)，因此答案为 \(\dfrac{256\times1024^2\times8}{32} = 67108864\)。

相乘

即求 \(2021x \equiv 999999999 \bmod 1000000007\)，\(x \equiv 999999999 \times 2021 ^ {-1}\) 求得 \(x = 17812964\)。

mod = 1000000007
x = pow(2021, mod - 2, mod) * 999999999 % mod
print(x)

编程题

砝码称重

同 01 背包，只是转移到左右。可使用 std::bitset 的 operator<< 实现。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::bitset<100010> f;
    f[0] = 1;
    for (int i : a) f |= f << i;
    for (int i : a) f |= f >> i;
    f[0] = 0;
    
    std::cout << f.count() << '\n';
    
    return 0;
}

特别注意如果使用 01 背包写法，想在一个循环里完成，需要开两维。

核心代码 
int B = 100000;
std::vector<std::vector<int>> f(2, std::vector<int>(2 * B + 10, 0));
f[0][0 + B] = 1;

for (int i = 1; i <= n; i++) {
    int w = a[i - 1];
    for (int j = -m + B; j <= m + B; j++) {
        f[i & 1][j] = f[~i & 1][j];
        if (j - w >= -m + B) f[i & 1][j] |= f[~i & 1][j - w];
        if (j + w <= +m + B) f[i & 1][j] |= f[~i & 1][j + w];
    }
}

int ans = 0;
for (int i = 1 + B; i <= m + B; i++) {
    ans += f[n & 1][i];
}

异或数列

容易发现平局当且仅当 \(\bigoplus\limits_{i=1}^n X_n = 0\)：记下每一位的次数，从高到低按位贪心，可见如果当前位为偶数则必然不会栽在这个位上。

话接上文，如果当前为出现次数 \(c = 1\)，则先手胜利；若为其他奇数，后手可以选择一个 \(c \ne 1\) 的数来反转，因此当 \(n - c \equiv 0 \bmod 2\) 时先手胜利，否则后手胜利。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int test = 1;
    std::cin >> test;
    void solve();
    while (test--) solve();
    return 0;
}

void solve() {
    int n;
    std::cin >> n;
    
    std::array<int, 30> cnt{};
    
    int s = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        for (int i = 20; ~i; i--) if (x >> i & 1) cnt[i] += 1;
        s ^= x;
    }
    
    if (!s) {
        std::cout << "0\n";
        return;
    }
    
    for (int i = 20; ~i; i--) if (cnt[i] & 1) {
        if (cnt[i] == 1) std::cout << "1\n";
        else if ((n - cnt[i]) & 1) std::cout << "-1\n";
        else std::cout << "1\n";
        break;
    }
}

左孩子右兄弟

用 \(f_u\) 表示 \(u\) 节点对应的答案，可见 \(f_u\) 至少是 \(u\) 的儿子数量，另有 \(\mathop\max\limits_{v \in u}\{f_v\}\)。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int n;
    std::cin >> n;
    
    std::vector<std::vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u;
        std::cin >> u;
        g[u].push_back(i + 1);
    }
    
    std::vector<int> f(n + 1);
    std::function<void(int)> dfs = [&](int u) -> void {
        f[u] = g[u].size();
        int max = 0;
        for (int v : g[u]) dfs(v), max = std::max(max, f[v]);
        f[u] += max;
    };
    dfs(1);
    
    std::cout << f[1] << '\n';
    
    return 0;
}

括号序列

既考虑左括号又考虑右括号很麻烦，不如分开考虑，最终的方案数相乘即可。如对于序列 \())((\)，可以只添加左括号使之成为：\(\color{red}{((}\)\())((\) 或 \(\color{red}{(}\)\()\)\(\color{red}{(}\)\()((\)；只添加右括号时，要转换为上面的问题，将序列反转再翻转：\())((\)，方案是一样的。因此最终答案为 \(4\)。接下来只需解决放左括号的方案数。

将原始序列按照右括号分成若干片段，研究某一段还需要放多少左括号。用 \(f_{i, j}\) 表示前缀 \(i\) 放置 \(j\) 个左括号使之合法（这里指的是左括号不少于右括号数量）的方案数。如果 \(s_i = \tt `('\)，方案数同 \(f_{i - 1, j - 1}\)；否则 \(f_{i, j} = \sum\limits_{k = 0}^{j + 1} f_{i - 1, k} = f_{i, j - 1} + f_{i - 1, j + 1}\)。最终答案即为前缀 \(i\) 放置至少 \(j'\) 个左括号使之合法的方案数。按照定义即使得 \(f_{n, j'} \ge 0\) 的最小 \(j'\)。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

const int mod = 1000000007, N = 5002;

ll f[N][N];

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::string s;
    std::cin >> s;
    
    int n = s.size();
    
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '(') {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j - 1];
            }
        } else {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            for (int j = 1; j <= n; j++) {
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
            }
        }
    }
    
    ll l = -1;
    for (int i = 0; i <= n; i++) {
        if (f[n][i]) {
            l = f[n][i];
            break;
        }
    }
    
    for (auto &si : s) {
        si ^= '(' ^ ')';
    }
    std::reverse(s.begin(), s.end());
    
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= n + 1; j++) {
            f[i][j] = 0;
        }
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '(') {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j - 1];
            }
        } else {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
            for (int j = 1; j <= n; j++) {
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
            }
        }
    }
    
    ll r = -1;
    for (int i = 0; i <= n; i++) {
        if (f[n][i]) {
            r = f[n][i];
            break;
        }
    }
    
    std::cout << l * r % mod << '\n';
    
    return 0;
}

时间显示

不考虑毫秒，直接 /= 1000，接着直接分解各位。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int test = 1;
    std::cin >> test;
    void solve();
    while (test--) solve();
    return 0;
}

void solve() {
    ll x;
    std::cin >> x;
    x /= 1000;
    ll h = 24, m = 60, s = 60;
    x %= h * m * s;
    
    std::cout << std::fixed << std::setw(2) << std::setfill('0');
    std::cout << x / (m * s) << ':';
    std::cout << std::fixed << std::setw(2) << std::setfill('0');
    std::cout << x % (m * s) / m << ':';
    std::cout << std::fixed << std::setw(2) << std::setfill('0');
    std::cout << x % s << '\n';
}

iostream sucks~

杨辉三角形

看到数据范围 \(10^9\)，大概率也是二分或者有结论。尝试二分的话，得寻找单调性，杨辉三角最明显的单调性莫过于每一条斜线了（自上而下）。注意到杨辉三角对称，不妨按照 \({n \choose n / 2}\) 来找。注意组合数容易爆精度，只要大于 \(x\) 就直接返回，反正需要的也只是 \(\ge x\) 的单调性而已。因为 \(10^9 \leq {30 \choose 15}\)。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int test = 1;
    std::cin >> test;
    void solve();
    while (test--) solve();
    return 0;
}

int x;

ll binom(int n, int m) {
    ll res = 1;
    for (int i = n, j = 1; j <= m; i--, j++) {
        res = res * i / j;
        if (res > x) {
            return res;
        }
    }
    return res;
}

void solve() {
    std::cin >> x;
    for (int i = 16;; i--) {
        int l = 2 * i, r = std::max(x, l);
        while (l < r) {
            int mid = (l + r) / 2;
            if (binom(mid, i) >= x) r = mid;
            else l = mid + 1;
        }
        if (binom(r, i) == x) {
            std::cout << 1ll * (r + 1) * r / 2 + i + 1 << '\n';
            return;
        }
    }
    
    __builtin_unreachable();
}

双向排序

注意到有许多步骤，是不需要的：例如 \(x \leq y\) 时 \([1, x], [1, y]\) 中就不需要跑 \([1, x]\)，另一个方向也类似。另外如果第一次操作为 \([x, n]\) 是不需要跑的。

接下来问题转变为两种操作交替时，该如何减少操作次数。观察下面的操作：

\(1. 0, 3\), \([\underline{3, 2, 1}, 4, 5, 6, 7]\)
\(2. 1, 4\), \([3, 2, 1, \underline{4, 5, 6, 7}]\)
\(3. 0, 5\), \([\underline{5, 4, 3, 2, 1}, 6, 7]\)

在这里，前两次操作没有交集，这两次结果被第三次覆盖了，相当于直接从初始状态到第三步。

下面要解决的问题就只有放置了，由于任意相邻两步必有交，因此只能放那些与自己无关的区间，例如 \(0, 5\) 就可以将答案数组置为 \([0, 0, 0, 0, 0, \underline{6, 7}]\)；再下一步 \(1, 2\)，可以将答案置为 \([5, 0, 0, 0, 0, 6, 7]\), ... 以此类推。

注意如果所有操作区间的并不为 \([1, n]\)，还需要按照最后一次操作种类填满。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

const int N = 100010;
int stk[N][2], ans[N];
int top;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int n, m;
    std::cin >> n >> m;
    
    while (m--) {
        int p, q;
        std::cin >> p >> q;
        if (p == 0) {
            while (top && stk[top][0] == 0)
                q = std::max(q, stk[top --][1]);
            while (top >= 2 && stk[top - 1][1] <= q)
                top -= 2;
            stk[++top][0] = p, stk[top][1] = q;
        } else if (top) {
            while (top && stk[top][0] == 1)
                q = std::min(q, stk[top --][1]);
            while (top >= 2 && stk[top - 1][1] >= q)
                top -= 2;
            stk[++top][0] = p, stk[top][1] = q;
        }
    }
    
    int k = n, l = 1, r = n;
    for (int i = 1; i <= top; i++) {
        if (stk[i][0] == 0) {
            while (l <= r && r > stk[i][1])
                ans[r--] = k--;
        } else {
            while (l <= r && l < stk[i][1])
                ans[l++] = k--;
        }
        if (l > r)
            break;
    }
    
    if (top & 1) {
        while (l <= r) ans[l++] = k--;
    } else {
        while (l <= r) ans[r--] = k--;
    }
    
    std::copy(ans + 1, ans + n + 1, std::ostream_iterator<int> {std::cout, " "});
    
    return 0;
}

最少砝码

实际上为平衡三进制最少需要多少底数。实际上有，\(n\) 位平衡三进制，每一位都包含 \(1, z\)，可以表示 \([-\dfrac{3^n - 1}{2}, \dfrac{3^n - 1}{2}]\) 内的所有数，即需要 \(\log_3(2 n + 1)\) 个数。

展开代码 
#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    int test = 1;
    std::cin >> test;
    void solve();
    while (test--) solve();
    return 0;
}

void solve() {
    ll x;
    std::cin >> x;
    
    auto y = std::log(2 * x + 1) / std::log(3);
    std::cout << (int)(std::ceil(y) + .5) << '\n';
}

标签：std,int,ll,cin,long,蓝桥,++,2021,省赛
From： https://www.cnblogs.com/patricky/p/2021-lanqiaocup-province-1.html

相关文章

  • 【漏洞复现】Apache Log4j2 lookup JNDI 注入漏洞（CVE-2021-44228）
    【漏洞复现】ApacheLog4j2lookupJNDI注入漏洞（CVE-2021-44228）0x01漏洞描述ApacheLog4j2是一个基于Java的日志记录工具，是对Log4j的升级，它比其前身Log4j1.x......
  • P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫（概率DP）
    [蓝桥杯2022省A]爬树的甲壳虫题目描述有一只甲壳虫想要爬上一颗高度为\(n\)的树，它一开始位于树根,高度为\(0\)，当它尝试从高度\(i-1\)爬到高度为\(i\)的位置......
  • 评选最佳品牌（第十届 省赛 T3）
      暴力吗，没什么技术含量。程序：#include<bits/stdc++.h>usingnamespacestd;intn,m;inta[101];strings[1002];intvis[101]={0};intmain(){ios::s......
  • 求和比较（第十二届 省赛 T4）
     题目 那么先把A1,A2所组成的等式列出来： 解出A1：       之后，我们可以发现问题变成了求1~n之间任意和为A1的可能性——01背包。顺便看一眼，要用long......
  • 求完数（第十一届 省赛 T2）
     题目：    那么题目里面有需要求因数之和的程序，那么我们先来写一个求因数之和的程序：intw(intk){intans=0;for(inti=1;i*i<=k;i++){......
  • Adobe Edge Animate 2021【An 2021】中文安装包下载及安装教程​
    AdobeAnimate是Adobe公司发布的，简称An，此软件的前身为AdobeFlashProfessional。此版本提供了增强缓动预设相机、图层深度增强、操作代码向导等实用功能，支持外新增HTML5创......
  • luogu P7520 [省选联考 2021 A 卷] 支配
    题面传送门自己瞎胡的支配树，可能是错的（大雾首先我们可以证明，支配关系成树。考虑一个点\(x\)的两个受支配点\(y,z\)，这两个点应该在一条路径上，如果\(y,z\)之间没有支......
  • 最完美LTSC2021_19044.2788软件选装纯净版VIP40.0
    【系统简介】=============================================================1.本次更新母盘来LTSC2021.19044.2788。进一步优化调整。2.此版本精简量不大，满足各大平台需求......
  • 蓝桥杯B组统计子矩阵
    题目传送门题目描述给定一个N×M的矩阵 A，请你统计有多少个子矩阵(最小1×1,最大N×M)满足子矩阵中所有数的和不超过给定的整数 K。输入格式第一行包含三个......
  • 蓝桥杯-砍竹子
    蓝桥杯2022省赛B组J题：砍竹子[蓝桥杯2022省B]砍竹子题目描述这天，小明在砍竹子，他面前有\(n\)棵竹子排成一排，一开始第\(i\)棵竹子的高度为\(h_{i}\).他觉......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99