2023 Robocom CAIP 省赛（本科组） 赛后总结_caip个人编程赛2023

个人题解

（比赛的原题已经在PTA教育超市上线。可以前往PTA的OJ上进行提交）

1、亚运奖牌榜   

2022 年第 19 届亚运会即将在杭州召开，杭州已经做好准备欢迎全亚洲的观众一同参与亚运盛会了！

你正在开发一款跟亚运奖牌计算相关的 App。给定两个国家的获奖情况，你的任务是计算这两个国家/地区的奖牌情况，并确定哪个国家/地区要排在奖牌榜的前面。

输入格式:

输入第一行是一个正整数 N (1≤N≤1000)，表示总共有 N 条获奖记录。

接下来的每一行都是形如以下的一条记录：

Ci​,Pi​

其中 Ci​=0,1，0 表示是第一个国家/地区，1 表示是第二个国家/地区；Pi​=1,2,3，1 表示金牌，2 表示银牌，3 表示铜牌。

输出格式:

首先输出两行，第一行是第一个国家/地区的金牌、银牌、铜牌获得数，用空格隔开；第二行是第二个国家/地区的奖牌获奖情况，要求与格式同第一个国家/地区。

最后一行，如果是第一个国家/地区排在前面，输出 The first win!，否则输出 The second win!。

排在前面的定义是：先比较金牌数，金牌数较大的排在前面；如金牌数相等，比较银牌数，银牌数较大的在前面；如金牌银牌数都相等，则比较铜牌数，铜牌数较大的在前面。

保证数据不存在奖牌数完全相同的情况。

输入样例:

15
0 1
0 2
0 3
0 1
0 1
0 2
0 3
1 3
1 3
1 3
1 3
1 2
1 1
1 1
1 1
 

输出样例:

3 2 2
3 1 4
The first win!

【思路】 

简单的热身题，详见代码。

【代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
const int maxn = 1e3 + 10;
const ll INF = 0x3f3f3f3f3f3f3f;
struct node {
    int jin, yin, tong;
} a[2];
int n;
 
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int c, p;
        cin >> c >> p;
        if (p == 1) {
            a[c].jin++;
        }
        if (p == 2) {
            a[c].yin++;
        }
        if (p == 3) {
            a[c].tong++;
        }
    }
    cout << a[0].jin << " " << a[0].yin << " " << a[0].tong << endl;
    cout << a[1].jin << " " << a[1].yin << " " << a[1].tong << endl;
    bool win = 0;
    if (a[0].jin == a[1].jin) {
        if (a[0].yin == a[1].yin) {
            if (a[0].tong < a[1].tong) {
                win = 1;
            } else {
                win = 0;
            }
        } else {
            if (a[0].yin < a[1].yin) {
                win = 1;
            } else {
                win = 0;
            }
        }
    } else {
        if (a[0].jin < a[1].jin) {
            win = 1;
        } else {
            win = 0;
        }
    }
    if (win == 0) {
        cout << "The first win!\n";
    } else {
        cout << "The second win!\n";
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);
 
    solve();
    return 0;
}

2、出院

A：最近出了一个饮料营养等级你们知道吗？例如无糖的饮料是 A 级，可乐是 D 级……
B：那……无糖可乐是什么级别？
C：AD 级吧。
A：出院！
B：出什么院，你也给我进去！

以上是某群中一段有趣的对话。请你按照里面的逻辑，在已知某些饮料的等级的情况下，给饮料定级。定级的方法是：

• 如果是已知等级的饮料，直接输出等级；
• 对于一个新饮料的名字，你需要将名字拆成两个已知等级的部分，然后输出这个级别。例如：Diet是A，Coke是D，那么DietCoke就是AD；
• 如果新饮料无法拆解或者有多种拆解方法，统一定为 D 级。

输入格式:

输入第一行是两个正整数 N,M (1≤N,M≤100)，表示已知的饮料有 N 种，需要定级的饮料有 M 种。

接下来首先是 N 行，每行是一个字符串和一个字符，表示一种饮料的名字和对应的等级，等级只有 A,B,C,D 四种。

然后是 M 行，每行是一个字符串，表示需要定级的饮料的名字。

所有饮料名字只包含有大小写字母，长度不超过 30，给定拥有等级的饮料的名字不会重复。

输出格式:

对于每一个需要定级的饮料，输出定好的定级。

输入样例:

5 6
Diet A
LowSugarTea B
Milk C
Coke D
Water A
DietCoke
Pepsi
Milk
CokeWater
GoodMilk
dietCoke
 

输出样例:

AD
D
C
DA
D
D

【思路】

输入的同时用map记录每个原始定级键值，然后两两配对生成复合定级，和原始定级一起放进新的map，遇到之前已经有过的复合定级则将其值改为”D“。输出时遇到不存在的键也输出”D“。

【代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
const int maxn = 1e3 + 10;
const ll INF = 0x3f3f3f3f3f3f3f;
map<string, string> mp;       // 原始定级
map<string, string> nmp;      // 复合定级
int n, m;
 
void solve() {
    cin >> n >> m;
    // 输入并记录原始定级，用map存储
    for (int i = 1; i <= n; i++) {
        string s;
        string c;
        cin >> s >> c;
        mp[s] = c;
    }
    // 将原始定级以及原始定级两两之间形成的复合定级放入新的map
    for (auto e1: mp) {
        nmp[e1.first] = e1.second;
        for (auto e2: mp) {
            if (!nmp.count(e1.first + e2.first))
                nmp[e1.first + e2.first] = e1.second + e2.second;
            else
                nmp[e1.first + e2.first] = "D";
        }
    }
    // 输出
    while (m--) {
        string s;
        cin >> s;
        if (nmp.count(s))
            cout << nmp[s] << endl;
        else
            cout << "D" << endl;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);
 
    solve();
    return 0;
}

5、相对成功与相对失败

注意：题面内容表达纯属娱乐，与现实无关！

网上常有人说：看 XX 只能度过一个相对成功/失败的人生。不妨假设把这个句式套用在“参加睿抗比赛“以及“玩手机游戏”上，那么有：

• “参加睿抗比赛”必然比“不参加睿抗比赛”要成功；
• “玩手机游戏“必然比“不玩手机游戏”要失败。

现在有 N 个人，已知这些人自己填写的是否参加了睿抗比赛以及是否玩手机游戏的情况，以及他们实际上的成功程度的排序顺序，请问最少有多少人在填写情况时说谎了？

输入格式:

输出第一行为一个正整数 T (1≤T≤5)，表示数据组数。

每组数据第一行是一个正整数 N (1≤N≤105)，表示总共的人数。

接下来的 N 行，第 i 行有两个数字 Ai​,Bi​，表示第 i 位参赛选手是否参加了睿抗比赛以及是否玩手机游戏，0 为没有参加/没有玩，1 为参加了/玩了。

最后一行有 N 个数，为一个选手编号 1 到 N 的排列，表示选手成功程度的排序。排序顺序从最成功到最失败。

选手编号从 1 开始。

输出格式:

对于每组数据，输出一个整数，表示最少的说谎人数。

输入样例:

3
5
1 0
1 0
0 0
0 0
0 1
1 2 3 4 5
5
1 0
1 0
0 0
0 0
0 1
5 4 3 2 1
5
1 0
0 1
0 0
0 1
1 1
4 2 1 3 5
 

输出样例:

0
3
2

样例说明:

对于样例中的第三组数据，一种可能是编号为 4 的选手和编号为 2 的选手说谎了。

【思路】

把每个人自己填写的分值排名求出来，然后输入实际排名的时候求出填写时排名的最长不下降子序列，用n减去最长不下降子序列即为答案（最长不下降子序列即最多有多少人说了实话）。

【代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
const int maxn = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f;
struct node {
    int id;
    int score;
} stu[maxn];
map<int, int> mp;  // 每个队员的排名 mp[1]=2代表第一位成员排名为2
int rk[maxn];
int dp[maxn];   // dp[i]=j代表长度为i的最长不下降子序列以j为结尾
int n;
 
bool cmp(node &a, node &b) {
    return a.score > b.score;
}
 
// 最长不下降子序列
void DP() {
    int p = 1;
    dp[1] = rk[1];
    for (int i = 2; i <= n; i++) {
        if (rk[i] >= dp[p]) {
            dp[++p] = rk[i];
        } else {
            int pos = upper_bound(dp + 1, dp + 1 + p, rk[i]) - dp;
            dp[pos] = rk[i];
        }
    }
    cout << n - p << endl;
}
 
void solve() {
    mp.clear();
    cin >> n;
    bool flag = true;   // 是否全相等
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        stu[i].id = i;
        int sc = 0;
        if (a == 1) {
            sc++;
        } else {
            sc--;
        }
        if (b == 1) {
            sc--;
        } else {
            sc++;
        }
        stu[i].score = sc;
        if (i != 1 && stu[i].score != stu[i - 1].score) {
            flag = false;
        }
    }
 
    sort(stu + 1, stu + 1 + n, cmp);
 
    mp[stu[1].id] = 1;
    for (int i = 2; i <= n; i++) {  // 注意这里一定要从2开始，mp[stu[1].id]在循环开始前就进行赋值
        if (stu[i].score == stu[i - 1].score) {
            mp[stu[i].id] = mp[stu[i - 1].id];  // 之前把这里写成了 mp[stu[i].id] = i - 1，这样是错误的
        } else {
            mp[stu[i].id] = i;
        }
    }
 
    for (int i = 1; i <= n; i++) {
        int id;
        cin >> id;
        rk[i] = mp[id];
    }
 
    if (flag) {
        cout << 0 << endl;
        return;
    }
 
    DP();
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

 

小结：题目风格和天梯赛相似。比赛两小时一共AC了ABE三道题，结束时全国排名300+（本科组一共4900+参赛选手）。前半小时解决AB，接着看CDE，D题看完没有头绪，C题也心里没底，最后觉得E题比较有把握拿下，随即开E题，纸上稍微模拟了一下很直接的想到了最长不下降子序列的解法，在最后成功解决。策略上没有什么大问题，该跳该舍弃的果断舍弃，没有顾此失彼因小失大，今年是第三次参加robocom，第一次参加时拿了国三。第二次参加也就是去年，因为死磕三分的数据点导致最后大分没拿，以至于差1分进国赛。今年暑假重心转移到折腾unity以及投简历找工作上了，算法就随缘了，只是在比赛前两天做了真题保持手感，结果反而发挥得很好。赛前想的是能保住省二进一个国赛即可，现在省一应该是有了（省一是前15%，还得看湖北省的情况，但看全国的榜单应该也不会差太多）。看来心态+状态>训练。国赛希望能有所突破吧，然后不留遗憾地退役。