2023 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（省赛）_睿抗编程赛道

目录

1、RC-u1 亚运奖牌榜

输入格式:

输出格式:

输入样例:

输出样例:

分析

ac_code

2、RC-u2 出院

输入格式:

输出格式:

输入样例:

输出样例:

分析

ac_code

3、RC-u3 骰子游戏

输入格式:

输出格式:

输入样例:

输出样例:

样例说明:

分析

ac_code

4、RC-u4 相对论大师

输入格式:

输出格式:

输入样例:

输出样例:

提示:

分析

ac_code

5、RC-u5 相对成功与相对失败

输入格式:

输出格式:

输入样例:

输出样例:

样例说明:

分析

ac_code

---

1、RC-u1 亚运奖牌榜

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!

分析

模拟，分别记录金银铜牌的数量然后进行比较

ac_code

#include <iostream>
 
using namespace std;
 
int T;
int a[4],b[4];
 
bool check()
{
    if(a[1]>b[1])    return true;
    if(a[1]<b[1])    return false;
    if(a[2]>b[2])    return true;
    if(a[2]<b[2])    return false;
    if(a[3]>b[3])    return true;
    if(a[3]<b[3])    return false;
}
int main()
{
    cin>>T;
    while(T--)
    {
        int c,p;
        cin>>c>>p;
        if(c==0)    a[p]++;
        else     b[p]++;
    }
    cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
    cout<<b[1]<<" "<<b[2]<<" "<<b[3]<<endl;
    bool st=check();
    if(st)    cout<<"The first win!"<<endl;
    else cout<<"The second win!"<<endl;
    return 0;
}

2、RC-u2 出院

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

分析

使用哈希表存储每个已知的等级的饮料

对于每个需要定级的饮料

1、考虑其是否为已知的饮料的等级，若已知直接输出即可

2、考虑其前缀是否为已知，若为已知，则考虑后缀是否已知，若二者均已知，则拼接次数加一，若拼接次数大于1，则定级为D

ac_code

#include <iostream>
#include <cstring>
#include <map>
 
using namespace std;
 
int n,m;
map<string,string> mp;
 
int main()
{
    cin>>n>>m;    
    for(int i=1;i<=n;i++)
    {
        string a,b;
        cin>>a>>b;
        mp[a]=b;
    }
 
    while(m--)
    {
        string s;
        cin>>s;
        if(mp.count(s))    cout<<mp[s]<<endl;
        else{
            int res=0;
            string tmp;
            for(auto it:mp)
            {
                int len=it.first.size();
                if(len<=s.size())
                {
                    if(s.substr(0,len)==it.first)
                    {
                        if(mp.count(s.substr(len,s.size())))
                        {
                            res++;
                            tmp=it.second+mp[s.substr(len,s.size())];
                        }
                    }
                }
            }
            if(res!=1)    cout<<"D"<<endl;
            else cout<<tmp<<endl;
            
        }
    }
    return 0;
}

3、RC-u3 骰子游戏

在某个游戏中有一个骰子游戏。在游戏中，你需要投掷 5 个标准六面骰子（骰子为一个正方体，6 个面上分别有1、2、3、4、5、6中的一个数字，骰子的质量均匀），投出的点数根据组合会获得一个“获胜等级”。获胜等级从高到低如下：

• 五个同点数 - 五个骰子显示相同的点数
• 四个同点数 - 四个骰子显示相同的点数
• 葫芦 - 一对和一个三个同点数（如1、1、3、3、3）
• 六高顺子 - 投出的点数为 2、3、4、5、6
• 五高顺子 - 投出的点数为 1、2、3、4、5
• 三个同点数 - 三个骰子显示相同的点数（如1、1、1、2、3）
• 两对 - 投出的点数中有两对是相同的（如 1、1、2、2、3）
• 一对 - 投出的点数有一对是相同的（如 1、1、2、3、4）
• 无 - 除去以上的其他情况

给定你已经投出的一次结果，现在假设你可以选择任意个骰子重投一次，请问怎么样操作，才能最大化在重骰后获得更好的获胜等级的概率呢？

注意：更好的获胜等级需要严格地比当前的获胜等级更好，例如 1、1、2、2、3 如果重骰后变为 1、1、3、3、4 并不比当前的获胜等级更好。

输入格式:

输入第一行是一个正整数 T (1≤T≤10)，表示接下来有多少组数据。
每组数据只有一行 5 个数字，表示第一次投出的 5 个骰子的点数。

输出格式:

对于每组数据输出三个整数，其中第一个整数为为了获得最大的概率需要重新骰几个骰子，后面的两个整数为重骰骰子后概率的最简分数，其中第二个整数为分子，第三个整数为分母。如果分子为 0，分母为 1。

如果有多种获得最大概率的情况，取重骰的骰子数最少的方案。

输入样例:

3
1 1 2 2 3
1 1 2 3 4
1 1 1 2 3
 

输出样例:

3 4 9
3 13 18
2 4 9

样例说明:

样例的第一组数据中，一种方案是：重骰最后三个骰子以获得最大的概率（只要重骰的有一个“1”或者三个均相等即可）。

分析

ac_code

4、RC-u4 相对论大师

在某个直播间里，观众常常会发送类似这样的弹幕：

鱼越大，鱼刺越大；鱼刺越大，肉越少；肉越少，鱼越小；所以鱼越大，鱼越小

这样通过一连串推导得出一个搞笑的结论的弹幕发送者被称为“相对论大师”。

现在给定一系列已有的推论，请你从给定的推论中挑选一些，组成一条类似于上面的弹幕，成为一名“相对论大师”。

输入格式:

输入第一行是一个正整数 N (1≤N≤1000），表示总共有多少条推论。

接下来的 N 行，每行有两对四个元素，形如下：

A 0 B 1
每对元素表示一个论点：第一个是一个长度不大于 5 的、只包含大小写字母的字符串，称为论点的核心；第二个数字固定为 0 或者 1，代表论点核心的方向属性。为简单理解，你可以将 0 理解为正面方向，1 理解为负面方向。例如：

YuCi 0 Rou 1

就可以理解为鱼刺大，肉少 。

于是一行中的两个论点就形成一条推论，表示第一个核心某个方向的属性能推出第二个核心的某个方向的属性，即鱼刺越大，肉越少。

输出格式:

按照弹幕格式输出一行，例如：

Yu 0 YuCi 0 YuCi 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

具体格式要求为：在一行中输出从起始论点到最终论点的所有推论，论点格式与输入相同，论点间以1个空格分隔。随后输出等号（等号前后均有1个空格），最后是相互矛盾的起始和终止论点。

如果有多种方案，选择使用推论最少的；推论条数相同的输出任意一种方案均可。

在方案中每条推论仅可使用一次。保证有解，且给定的推论中没有相同的推论。

输入样例:

5
Yu 0 Yuci 0
Rou 1 Yu 1
Yuci 0 Rou 1
Yuci 0 Gutou 0
Gutou 0 Rou 0
 

输出样例:

Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

提示:

本题返回结果若为格式错误均可视为答案错误。

分析

本题难点在于建图，将每个已知推论的起始论点和最终论点分别编号，我们给每一个论点2个未使用的相邻的顶点编号， 并且以较小的编号为基本编号。如yuci的基本编号为1， 那么yuci 0的编号就为1, yuci 1的编号为2。 同时我们记录每个编号的名称， 以及每个名称的基本编号，这样我们就完成了图的建立和相关信息的保存。

然后枚举每个顶点组，使用简单的BFS找到获得路径， 在所有路径中取最短的有效路径为答案

ac_code

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
const int N=21000;
 
int n,cnt=1;
int idx,h[N],ne[N],e[N];
bool st[N];
int ve[N];
unordered_map<string,int> mp;
string name[N];
 
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
vector<int> bfs(int start,int end)
{
    queue<int> q;
    memset(ve,0,sizeof ve);
    q.push(start);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        if(t==end)    break;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(ve[j]==0)
            {
                q.push(j);
                ve[j]=t;//从i到达j
            }
        }
    }
    vector<int> res;
    do {
        res.push_back(end), end = ve[end];
    } while (end != 0);
    //cout<<endl;
    return res;
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        string s1,s2;
        int a1,a2;
        cin>>s1>>a1>>s2>>a2;
        int a,b;
        if(!mp.count(s1))
        {
            mp[s1]=cnt;
            name[cnt]=s1;
            name[cnt+1]=s1;
            cnt+=2;
        }
        if(!mp.count(s2))
        {
            mp[s2]=cnt;
            name[cnt]=s2;
            name[cnt+1]=s2;
            cnt+=2;
        }
        if(a1==0)    a=mp[s1];
        else if(a1==1)    a=mp[s1]+1;
        if(a2==0)    b=mp[s2];
        else if(a2==1)    b=mp[s2]+1;
        add(a,b);
        // cout<<s1<<" "<<a1<<" "<<mp[s1]<<" "<<name[mp[s1]]<<endl;
        // cout<<s2<<" "<<a2<<" "<<mp[s2]<<" "<<name[mp[s2]]<<endl;
    }
    auto t=bfs(1,2);
    cnt-=2;
    vector<int> res(2100);
    for(int i=1;i<=cnt;i+=2)
    {
        auto t1=bfs(i,i+1);
        auto t2=bfs(i+1,i);
        if(res.size()>t1.size()&&t1.size()>1)    res=t1;
        if(res.size()>t2.size()&&t2.size()>1)    res=t2;
    }
    
    //cout<<res.size();
    for(int i=res.size()-1;i>=1;i--)
    {
        //cout<<res[i]<<" "<<endl;
        cout<<name[res[i]]<<" "<<res[i]-mp[name[res[i]]]<<" ";
        cout<<name[res[i-1]]<<" "<<res[i-1]-mp[name[res[i-1]]]<<" ";
    }
    cout<<"= ";
    cout<<name[res[res.size()-1]]<<" "<<res[res.size()-1]-mp[name[res[res.size()-1]]]<<" ";
    cout<<name[res[0]]<<" "<<res[0]-mp[name[res[0]]];
    return 0;
}

5、RC-u5 相对成功与相对失败

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

网上常有人说：看 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 的选手说谎了。

分析

首先根据参加睿抗比赛加1分、没玩手机游戏加1分，计算每个人的得分

然后根据给出的选手成功程度的排序形成一个序列

由题目可知，需要找出最少有多少人在填写情况时说谎了，即在更改最少的人的得分的情况下，使得得分的序列满足排序顺序为从最成功到最失败

分析题目可知，只需找出一个最长的不上升的子序列，然后更改其余的人的成绩即可满足条件

答案为:n-最长的不上升的子序列的长度

ac_code

#include <iostream>
 
using namespace std;
 
const int N=1e5+10;
 
int T,n;
int a[N],b[N];
int q[N];//q[i]表示长度为i的序列的结尾的最小的数
 
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int x,y;
            cin>>x>>y;
            if(x==1)    b[i]++;
            if(y==0)    b[i]++;
        }
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            a[i]=b[x];
            b[x]=0;
            q[x]=0;
        }
        int len=0;
        q[1]=-1e9;
        for(int i=1;i<=n;i++)
        {
            int l=0,r=len;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(q[mid]>=a[i]) l=mid;
                else    r=mid-1;
            }
            len=max(len,r+1);
            q[r+1]=a[i];
        }
        cout<<n-len<<endl;
    }
    return 0;
}