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

传送门

RC-u1 亚运奖牌榜

题目

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

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

思路

存储、排序

代码

#include<bits/stdc++.h>
using namespace std;
int dp[2][4];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,u,v;
    cin>>t;
    while(t--){
        cin>>u>>v;
        dp[u][v]++;
    }
    for(int j=0;j<2;j++){
        for(int i=1;i<=3;i++){
            cout<<dp[j][i]<<("%c",i==3?'\n':' ');
        }
    }
    for(int i=1;i<=3;i++){
        if(dp[0][i]!=dp[1][i]){
            cout<<("%s",dp[0][i]>dp[1][i]?"The first win!":"The second win!");
            break;
        }
    }
    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

RC-u2 出院

题目

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

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

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

思路

最多两个已知等级组合，所有可能存在map中

代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,string>s1,s2;
string x,y;
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        s1[x]=y;
    }
    for(auto a:s1){
        for(auto b:s1){
            x=a.first+b.first;
            y=a.second+b.second;
            if(s2.find(x)!=s2.end())s2[x]='D';
            else s2[x]=y;
        }
    }
    while(m--){
        cin>>x;
        if(s1.find(x)!=s1.end())cout<<s1[x]<<'\n';
        else{
            if(s2.find(x)!=s2.end())cout<<s2[x]<<'\n';
            else cout<<"D\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

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 并不比当前的获胜等级更好。

思路

根据题目给出的设一个求分数的函数，然后分别求出更改1、2、···、5个骰子的最大获得更好的获胜等级的概率，并保存它的分子分母，然后得出更改几个骰子后的概率最大，并输出此时的分子、分母

代码（没写出来）

int grade(int B[]){     //求分数
    int A[6];
    A[1]=B[1],A[2]=B[2],A[3]=B[3],A[4]=B[4],A[5]=B[5];
    sort(A+1,A+1+5);
    if(A[1]==A[5])return 9;
    if(A[1]==A[4])return 8;
    if(A[1]==A[2]&&A[3]==A[5])return 7;
    if(A[1]==A[3]&&A[4]==A[5])return 7;
    if(A[1]<A[2]&&A[2]<A[3]&&A[3]<A[4]&&A[4]<A[5]){
        if(A[1]==2)return 6;
        if(A[1]==1&&A[5]==5)return 5;
    }
    if(A[1]==A[3]||A[2]==A[4]||A[3]==A[5])return 4;
    if(A[1]==A[2]&&(A[3]==A[4]||A[4]==A[5]))return 3;
    if(A[2]==A[3]&&A[4]==A[5])return 3;
    if(A[1]==A[2]||A[2]==A[3]||A[3]==A[4]||A[4]==A[5])return 2;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

RC-u4 相对论大师

题目

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

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

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

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

思路

每行输入两对，可以理解为路径，前面的元素可以到达后面的元素，然后bfs找出可以实现的推论当中的最短的一条

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=5e6+5;
unordered_map<string,vector<string>>mp;
unordered_map<string,int>num;
unordered_map<string,string>pre;
queue<string>q;
stack<string>p;
int bfs(string st,string ed){
    while(!q.empty())q.pop();
    num.clear();
    q.push(st);
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        if(now==ed)return num[now];
        for(int i=0;i<mp[now].size();i++){
            string p=mp[now][i];
            if(num.find(p)!=num.end())continue;
            num[p]=num[now]+1;
            pre[p]=now;
            q.push(p);
        }
    }
    return -1;
}

unordered_map<string,int>v;

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s1,s2,s3,s4;
        cin>>s1>>s2>>s3>>s4;
        mp[s1+' '+s2].push_back(s3+' '+s4);
        v[s1]=1,v[s3]=1;
    }
    int minx=0x3f3f3f3f;
    string ans1,ans2;
    for(auto it:v){
        string st=it.first+" 0";
        string ed=it.first+" 1";
        int d1=bfs(st,ed);
        int d2=bfs(ed,st);
        if(d1!=-1&&d1<minx){
            minx=d1,ans1=st,ans2=ed;
        }
        if(d2!=-1&&d2<minx){
            minx=d2,ans1=ed,ans2=st;
        }
    }
    bfs(ans1,ans2);
    string now=ans2;
    while(!q.empty())q.pop();
    while(1){
        p.push(now);
        if(now==ans1)break;
        now=pre[now];
    }
    n=p.size();
    while(!p.empty()){
        auto now=p.top();
        p.pop();
        if(p.size()&&p.size()<n-1)cout<<now<<("%c",q.size()==1?'\n':' ');
        cout<<now<<("%c",q.size()==1?'\n':' ');
    }
    cout<<" = "<<ans1<<' '<<ans2;
    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

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

题目

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

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

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

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

思路

根据每个人填写的排序，分数高的排前面，则最长不下降子序列就是最多不散慌的人数

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N],mp[N];
struct node{
    int numb,id;
    bool operator<(const node&x)const{
        return numb>x.numb;
    }
}nb[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            int u,v;
            cin>>u>>v;
            nb[i]={0,i};
            if(u==1)nb[i].numb++;
            if(v==0)nb[i].numb++;
        }
        sort(nb+1,nb+1+n);
        mp[nb[1].id]=1;
        for(int i=2;i<=n;i++){
            if(nb[i].numb==nb[i-1].numb)
                mp[nb[i].id]=mp[nb[i-1].id];
            else
                mp[nb[i].id]=i;
        }
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            b[i]=mp[x];
        }
        int tot=1;a[1]=b[1];
        for(int i=2;i<=n;i++){
            if(b[i]>=a[tot])a[++tot]=b[i];
            else{
                int m=upper_bound(a+1,a+1+tot,b[i])-a;
                a[m]=b[i];
            }
        }
        cout<<n-tot<<'\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