第二届全国高校计算机技能竞赛——C++赛道 题解

Powered by:NEFU AB-IN

Link

第二届全国高校计算机技能竞赛——C++赛道

• A 互不侵犯

  • 题意

    在象棋中，车可以攻击和他同一行同一列的棋子。
    现在有一个放置了若干个车的$n\times n$的棋盘，请问这个棋盘中车此时能相互攻击吗？能输出"YES"，不能输出"NO"。
    棋盘中只有车，有车的位置用$1$表示，没有车用$0$表示。

  • 思路

    模拟，一开始理解错题意了，其实是能挨着就行

  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-09-28 19:01:05
    * @FilePath: \Contest\a\a.cpp
    * @LastEditTime: 2023-10-05 18:14:53
    */
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 1e3 + 10, INF = 0x3f3f3f3f;signed main()
    {// freopen("Tests/input_1.txt", "r", stdin);IOS;int n;cin >> n;vector<vector<int>> chessboard(n, vector<int>(n));for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){cin >> chessboard[i][j];}}for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (chessboard[i][j] == 1){for (int k = 0; k < n; ++k){if (chessboard[i][k] == 1 && k != j){cout << "YES" << '\n';return 0;}if (chessboard[k][j] == 1 && k != i){cout << "YES" << '\n';return 0;}}}}}cout << "NO" << '\n';return 0;
    }
    

• B 奖学金

  • 题意

    某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
    任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
    7 279
    5 279
    这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
    5 279
    7 279
    则按输出错误处理，不能得分。

  • 思路

    结构体排序

  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-09-28 19:10:53
    * @FilePath: \Contest\b\b.cpp
    * @LastEditTime: 2023-09-28 19:14:35
    */
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;struct sa
    {int xh, y, s, yy;
    };sa a[N];signed main()
    {// freopen("Tests/input_1.txt", "r", stdin);IOS;int n;cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i].y >> a[i].s >> a[i].yy;a[i].xh = i;}sort(a + 1, a + 1 + n, [&](const sa a, const sa b) {if (a.s + a.y + a.yy != b.s + b.y + b.yy){return a.s + a.y + a.yy > b.s + b.y + b.yy;}else if (a.y != b.y){return a.y > b.y;}else if (a.xh != b.xh){return a.xh < b.xh;};});for (int i = 1; i <= 5; ++i){cout << a[i].xh << " " << a[i].s + a[i].y + a[i].yy << '\n';}return 0;
    }
    

• C 领导者

  • 题意

    小理有 $N$ 头奶牛，每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。
    每一头奶牛都有一个名单，第 $i$ 头奶牛的名单上记录了从第 $i$ 头奶牛到第 $E_i$ 头奶牛的所有奶牛。
    每一种奶牛都有且仅有一位“领导者”，对于某一头牛 $i$，如果它能成为“领导者”仅当它满足以下条件的至少一个：
    其记录的名单上包含它的品种的所有奶牛。
    其记录的名单上记录了另一品种奶牛的“领导者”。
    请求出有多少对奶牛可能成为两种奶牛的领导者，保证存在至少一种。

  • 思路

    差分解决，快速进行区间统计奶牛的种类
    两种方式找到领导者，先是找到第一种，然后通过找到的领导者，找第二种领导者

  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-09-30 11:07:47
    * @FilePath: \Contest\c\c.cpp
    * @LastEditTime: 2023-09-30 11:40:32
    */#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;char input[N];
    int c[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];int main()
    {int n;cin >> n;cin >> (input + 1);for (int i = 1; i <= n; i++)cin >> c[i];for (int i = 1; i <= n; i++){s1[i] = s1[i - 1];s2[i] = s2[i - 1];if (input[i] == 'G')s1[i]++;elses2[i]++;}for (int i = 1; i <= n; i++){int gg = s1[c[i]] - s1[i - 1];int hh = s2[c[i]] - s2[i - 1];if (input[i] == 'G' && gg == s1[n])g[i] = 1;else if (input[i] == 'H' && hh == s2[n])h[i] = 1;}for (int i = 1; i <= n; i++){gs[i] = gs[i - 1], hs[i] = hs[i - 1];if (g[i])gs[i]++;if (h[i])hs[i]++;}for (int i = 1; i <= n; i++){if (input[i] == 'G' && (hs[c[i]] - hs[i - 1]) != 0)g[i] = 1;else if (input[i] == 'H' && (gs[c[i]] - gs[i - 1]) != 0)h[i] = 1;}int countG = 0, countH = 0;for (int i = 1; i <= n; i++){if (g[i])countG++;if (h[i])countH++;}cout << countG * countH << '\n';return 0;
    }

• D 空调

  • 题意

    小理的 $N$ 头奶牛住在一个谷仓里，谷仓里有连续的牛栏，编号为 $1-100$ 。 奶牛 $i$ 占据了编号 $[s_i,t_i]$ 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 $i$ 占用的每个牛栏的温度必须至少降低 $c_i$ 单位。
    谷仓包含 $M$ 台空调，标记为 $1-M$。第 $i$ 台空调需要花费 $m_i$ 单位的金钱来运行，如果运行，第 $i$ 台空调将牛栏 $[a_i,b_i]$ 所有牛栏的温度降低 $p_i$。 空调覆盖的牛栏范围可能会重叠。
    请帮助小理求出满足所有奶牛需求要花费的最少金钱。

  • 思路

    由于数据量比较小，可以采用dfs，把所有空调的情况都枚举一遍

  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-09-30 11:07:47
    * @FilePath: \Contest\c\c.cpp
    * @LastEditTime: 2023-09-30 11:40:32
    */#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;char input[N];
    int c[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];int main()
    {int n;cin >> n;cin >> (input + 1);for (int i = 1; i <= n; i++)cin >> c[i];for (int i = 1; i <= n; i++){s1[i] = s1[i - 1];s2[i] = s2[i - 1];if (input[i] == 'G')s1[i]++;elses2[i]++;}for (int i = 1; i <= n; i++){int gg = s1[c[i]] - s1[i - 1];int hh = s2[c[i]] - s2[i - 1];if (input[i] == 'G' && gg == s1[n])g[i] = 1;else if (input[i] == 'H' && hh == s2[n])h[i] = 1;}for (int i = 1; i <= n; i++){gs[i] = gs[i - 1], hs[i] = hs[i - 1];if (g[i])gs[i]++;if (h[i])hs[i]++;}for (int i = 1; i <= n; i++){if (input[i] == 'G' && (hs[c[i]] - hs[i - 1]) != 0)g[i] = 1;else if (input[i] == 'H' && (gs[c[i]] - gs[i - 1]) != 0)h[i] = 1;}int countG = 0, countH = 0;for (int i = 1; i <= n; i++){if (g[i])countG++;if (h[i])countH++;}cout << countG * countH << '\n';return 0;
    }

• E 字符操作变换

  • 题意

    小理给了小赛 $Q$ 个新字符串 $(1\le Q\le 100)$ ，其中只有字符 M 和 O ，他想将 $Q$ 个字符串都变成 MOO。
    小赛可以用如下的方式改变字符串：
    用相反的字符替换第一个或最后一个字符（将 M 变成 O ，将 O 变成 M ）。
    删除第一个或最后一个字符。
    小赛只想用最少的次数完成改变。请你帮他找到需要的最小改变次数。如果不可能在有限的步数中完成这个任务，请输出 -1 。

  • 思路

    一共四种情况，其中两种情况是可以合并的，既然只能对头尾操作，那么就不用操心中间的情况，那就可以看连起来的某一段字符串的OM情况

  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-09-28 19:50:53
    * @FilePath: \Contest\e\e.cpp
    * @LastEditTime: 2023-09-28 19:55:37
    */
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;signed main()
    {// freopen("Tests/input_1.txt", "r", stdin);IOS;int q;cin >> q;while (q--){string a;cin >> a;int z = SZ(a), s = INF;for (int i = 0; i < z - 2; i++){if (a[i] == 'M' && a[i + 1] == 'O' && a[i + 2] == 'O'){s = z - 3;break;}else if ((a[i] == 'O' && a[i + 1] == 'O' && a[i + 2] == 'O') ||(a[i] == 'M' && a[i + 1] == 'O' && a[i + 2] == 'M')){s = min(s, z - 2);}else if (a[i] == 'O' && a[i + 1] == 'O' && a[i + 2] == 'M'){s = min(s, z - 1);}}if (s == INF)cout << "-1\n";elsecout << s << '\n';}return 0;
    }