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

    Powered by:NEFU AB-IN

    Link

    文章目录

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

    • A 互不侵犯

      • 题意

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

        • 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
        • 62
        • 63
        • 64
        • 65

    • 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 
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;
}

        • 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
        • 62
        • 63

    • C 领导者

      • 题意

        小理有 N N N 头奶牛，每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。
        每一头奶牛都有一个名单，第 i i i 头奶牛的名单上记录了从第 i i i 头奶牛到第 E i E_i Ei​ 头奶牛的所有奶牛。
        每一种奶牛都有且仅有一位“领导者”，对于某一头牛 i 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 
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]++;
        else
            s2[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;
}


        • 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
        • 62
        • 63
        • 64
        • 65
        • 66
        • 67
        • 68
        • 69
        • 70
        • 71
        • 72
        • 73
        • 74
        • 75
        • 76
        • 77
        • 78
        • 79
        • 80
        • 81
        • 82
        • 83
        • 84
        • 85

    • D 空调

      • 题意

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

      • 思路

        由于数据量比较小，可以采用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 
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]++;
        else
            s2[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;
}


        • 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
        • 62
        • 63
        • 64
        • 65
        • 66
        • 67
        • 68
        • 69
        • 70
        • 71
        • 72
        • 73
        • 74
        • 75
        • 76
        • 77
        • 78
        • 79
        • 80
        • 81
        • 82
        • 83
        • 84
        • 85

    • E 字符操作变换

      • 题意

        小理给了小赛 Q Q Q 个新字符串 ( 1 ≤ Q ≤ 100 ) (1\le Q\le100) (1≤Q≤100) ，其中只有字符 M 和 O ，他想将 Q Q 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 
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";
        else
            cout << s << '\n';
    }

    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
  • 相关阅读:
    代码与细节（一）
    Python很慢，但它即将变得更快
    java毕业设计云音乐后端内容管理系统Mybatis+系统+数据库+调试部署
    Java学习——基本语法笔记
    135. 分发糖果
    2024.3.28成都AI与机器视觉技术工业应用研讨会
    近似串匹配问题（动态规划）
    面试：单例模式
    【1day】复现宏景OA KhFieldTree接口 SQL注入漏洞
    MIMO 从入门到精通 -科普篇 1 - 5G Massive MIMO
  • 原文地址：https://blog.csdn.net/qq_45859188/article/details/133587944