[C++知识库]第四届蓝桥杯A组题解

第四届蓝桥杯A组题解

视频讲解点这里

错误票据

解题思路

因为他给我们的$n$行，每行有多少个元素其实是一个不确定的量，那么我们就是需要用字符串存储

第一种方法

这里我们使用了$C++$自带的字符串流$stringstream$，然后我们直接以空格分割了字符串，这个字符流厉害在于，可以自动根据空格分隔字符串，然后我们还是可以自动实现$string$到$int$和$int$到$string$的转换

第二种办法

我们使用读到文件尾的方法, 一直读取到最后为止, 然后我们在进行一个排序输出

代码实现

第一种方法

#include <bits/stdc++.h>

using namespace std;

void solve() {
    vector<int> res;
    int n;
    cin >> n;
    string tmp = "\n";
    getline(cin, tmp);
    for (int i = 1; i <= n; i++) {
        stringstream ss;
        string s;
        getline(cin, s);
        ss << s;
        int j;
        while (ss >> j) res.push_back(j);
    }
    sort(res.begin(), res.end());
    // for (auto &it : res) cout << it << " ";
    int okk = res[0], res1 = 0, res2 = 0;
    for (int i = 1; i < res.size(); i++) {
        if (res[i] != okk + 1 and res[i] != okk) res1 = okk + 1;
        else if (res[i] == okk) res2 = okk;
        okk = res[i];
    }
    cout << res1 << " " << res2 << "\n";
}

signed main() {
    solve();
    return 0;
}

第二种方法

#include <bits/stdc++.h>

using namespace std;

int n, idx, a[100010], res1, res2;

void solve() {
    scanf("%d", &n);
    while (scanf("%d", &a[idx]) != EOF) idx++;
    sort(a, a + idx);
    int okk = a[0];
    for (int i = 1; i < idx; i++) {
        if (a[i] != okk + 1 and a[i] != okk)  res1 = okk + 1;
        else if (a[i] == okk) res2 = okk;
        okk = a[i];
    }
    printf("%d %d\n", res1, res2);
}

signed main() {
    solve();
    return 0;
}

买不到的数据

解题思路

首先因为我们的数据范围很小，题目时限很宽松，我们可以直接暴力枚举所有的情况，然后我们再找最大没有出现的

然后我们还可以采用数论的知识来解决这个问题

简单数学证明

首先这个问题应该是转换为这么一个问题，我们有两个互质的数$m$和$n$, 我们要求取最大不能通过$m$和$n$表示的正整数, 我们可以先设定$m<n$, $n\equiv r(modm)$, 然后因为$m$和$n$互质, 那么我们可以知道$0,n,2n,...,(m?1)n$对于$m$的余数都不一样

所以我们对于不同的余数,可以划分成为不同的集合, 然后当我们想表示一个对$m$的余数为$x$的集合, 我们可以找到一个最小正整数 $b$ 使得 $bn\equiv x(modm)$, 那么根据这个我们可以得到我们用$n$和$m$可以表示的最小的正整数就是$bn$, 我们这里不考虑特殊解, 比如为$0$的情况, 然后我们可知最小满足的前一个肯定是最大不满足的也就是说最大不满足的就是$bn?m$, 然后我们要找到最大不满足, 我们就要把$b$提到最大, 所以$b==m?1$, 所以我们最后的答案就是$(m?1)?n?m$, 化简之后就是$n?m?n?m$, 这里特别鸣谢我的一位朋友, 帮我理清了这个流程

参考了知乎的回答: 传送门

这个博主证明了一下这个，参考了一下这个传送门

代码实现

第一种方法

/*
 * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了
 * @CSDN: https://blog.csdn.net/godhandsjoker?spm=1000.2115.3001.5343
 * @Github: https://github.com/godhandsjoker
 * @QQ: 3124406837
 * @Author: godhands
 * @LastEditTime: 2022-02-15 01:08:31
 */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'

// constexpr int N = 1e6 + 10;
const int N = 1e6 + 10;

void solve() {
    int n, m;
    cin >> n >> m;
    bitset<N> st = 0;
    for (int i = 0; i <= 1000; i++) {
        for (int j = 0; j <= 1000; j++) {
            st[i * n + j * m] = 1;
        }
    }
    for (int i = n * m; i; i--)
        if (st[i] == 0) {
            cout << i << "\n";
            return;
        }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

第二种办法

/*
 * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了
 * @CSDN: https://blog.csdn.net/godhandsjoker?spm=1000.2115.3001.5343
 * @Github: https://github.com/godhandsjoker
 * @QQ: 3124406837
 * @Author: godhands
 * @LastEditTime: 2022-02-15 01:11:59
 */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'

// constexpr int N = 1e6 + 10;
const int N = 1e6 + 10;

void solve() {
    int n, m;
    cin >> n >> m;
    cout << n * m - n - m << "\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

剪格子

解题思路：

这里提前说一下，我们的这个做法可以过掉蓝桥杯的样例，但是事实上并不是很优秀，因我比如我们在中间成环，或者一个$T$字型无法满足

然后抛出这两种情况, 我们这个题目就比较容易发现规律了, 我们可以从左上角的那个点开始$dfs$, 然后如果我们的总和达到了$sum/2$这里的$sum$代表的是整个二维数组的总和, 我们就可以退出, 如果整个的和是奇数就是不存在, 如果大于了也返回, 然后四个方向分别遍历回溯

代码实现:

注意先输入的是$m$!!!

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'

int n, m, res = INT_MAX, sum = 0;
// sum是我们整个二维数组的总和, res是我们最后的最小步数
vector<PII> dir(4);
// 这个是我们的方向向量

inline void dfs(int x, int y, int step, int tmp, vector<vector<int> > &mp,
                vector<vector<bool> > &vis) {
    if (tmp * 2 == sum) {
        res = min(res, step);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i].first, yy = y + dir[i].second;
        if (xx < 0 or xx >= n or yy < 0 or yy >= m or vis[xx][yy]) continue;
        vis[xx][yy] = true;
        dfs(xx, yy, step + 1, tmp + mp[xx][yy], mp, vis);
        vis[xx][yy] = false;
    }
}

void solve() {
    cin >> m >> n;
    vector<vector<int> > mp(n, vector<int>(m, 0));
    vector<vector<bool> > vis(n, vector<bool>(m, false));
    // mp是我们的二维数组, vis是用来标记我们是不是使用过的
    dir[0] = {0, 1}, dir[1] = {1, 0}, dir[2] = {0, -1}, dir[3] = {-1, 0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            sum += mp[i][j];
        }
    }
    if (sum & 1) {
        cout << "0\n";
        return;
    }
    // 因为总和是奇数我们没有办法拆分, 直接返回0
    dfs(0, 0, 1, mp[0][0], mp, vis);
    res == INT_MAX ? cout << "0\n" : cout << res << "\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

大臣的旅费

解题思路

这题我们要分清楚, 我们究竟是要拿到满分还是尽可能的骗分, 因为这个是$OI$赛制, 按照通过的数据点给分, 而不是$ACM$赛制, 必须全部正确才算正确

首先如果我们要想骗分, 我们可以直接套一个$Floyd$算法的板子上去, 这样虽然时间复杂度和空间复杂度都很高, 但是我们可以骗分, 事实上, 我在官网测试, 得到了$75$分, 四个测试点最后一个没有通过

我们正确的解法就是, 随便找一个点, 然后找最远距离的一个点, 然后在通过我们找到的最远距离的点, 再去找一次, 这次的点就是我们最终的答案

代码实现

骗分代码

/*
 * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了
 * @CSDN: https://blog.csdn.net/godhandsjoker?spm=1000.2115.3001.5343
 * @Github: https://github.com/godhandsjoker
 * @QQ: 3124406837
 * @Author: godhands
 * @LastEditTime: 2022-02-15 19:46:11
 */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'

void floyd(int& n, vector<vector<int> >& G) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
void solve() {
    int n;
    cin >> n;
    vector<vector<int> > G(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == j) G[i][j] = 0;
        }
    }
    for (int i = 1; i < n; i++) {
        int p, q, d;
        cin >> p >> q >> d;
        G[p][q] = G[q][p] = min(d, G[p][q]);
    }
    floyd(n, G);
    int maxx = INT_MIN;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (G[i][j] != INT_MAX) maxx = max(maxx, G[i][j]);
        }
    }
    cout << (21 + maxx) * maxx / 2 << "\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

正确的代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'

inline void dfs(int u, int fa, int distance, vector<vector<PII> > &G,
                vector<int> &dist) {
    dist[u] = distance;
    // 更新我们的距离
    for (int i = 0; i < G[u].size(); i++) {
        PII tmp = G[u][i];
        if (tmp.first != fa) {
            dfs(tmp.first, u, distance + tmp.second, G, dist);
            // 如果不是父节点, 我们可以遍历
        }
    }
}
void solve() {
    int n;
    cin >> n;
    vector<vector<PII> > G(n + 1);
    vector<int> dist(n + 1, 0);
    for (int i = 1; i < n; i++) {
        int p, q, d;
        cin >> p >> q >> d;
        G[p].push_back({q, d});
        G[q].push_back({p, d});
    }
    // 临界表建图
    dfs(1, -1, 0, G, dist);
    // 先找到一下最远点
    int u = 1;
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[u]) u = i;
    // 找到最远的点是哪一个
    dfs(u, -1, 0, G, dist);
    u = 1;
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[u]) u = i;
    // 重复找一次
    cout << (21 + dist[u]) * dist[u] / 2 << "\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

带分数

解题思路

其实我们发现他本质就是$09$的一个全排列, 然后我们只需要判断我们这三个数(加号前面的一个, 加号和分号前面的一个, 分号后面的一个), 分别开始点和结束点在哪里就可以了, 所以我们直接使用C++的全排列函数即可, 然后暴力枚举所有位置

然后我们的式子原来是$a+\frac{b}{c}==n$, 然后我们左右同时乘上$c$即可得到这么一个等式$a?c+b=n?c$

代码实现

/*
 * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了
 * @CSDN: https://blog.csdn.net/godhandsjoker?spm=1000.2115.3001.5343
 * @Github: https://github.com/godhandsjoker
 * @QQ: 3124406837
 * @Author: godhands
 * @LastEditTime: 2022-02-15 20:24:22
 */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'

int cal(int l, int r, vector<int> &nums) {
    int res = 0;
    for (int i = l; i <= r; i++) {
        res = res * 10 + nums[i];
    }
    return res;
}
void solve() {
    int n;
    cin >> n;
    vector<int> nums(9);
    for (int i = 0; i < 9; i++) nums[i] = i + 1;
    int res = 0;
    do {
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                int a = cal(0, i, nums);
                int b = cal(i + 1, j, nums);
                int c = cal(j + 1, 8, nums);
                if (a * c + b == c * n) res++;
            }
        }
    } while (next_permutation(nums.begin(), nums.end()));
    cout << res << "\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}