2022 RoboCom 世界机器人开发者大赛-本科组（省赛) CAIP 完整版题解

文中代码均可AC, 有任何问题欢迎在评论区留言讨论

RC-u1 不要浪费金币

哲哲最近在玩一个游戏，击杀怪物能获得金币 —— 这里记击杀第 i 个怪物获得的金币数量为 Pi。

然而这个游戏允许拥有的金币数量是有上限的，当超过时，超过上限的部分就会被系统光明正大地吃掉，哲哲就拿不到了。

为了不浪费金币，哲哲决定，当下一个要击杀的怪物可获得的金币会导致自己拥有的金币数量超过上限时，就去消费一次，把自己已有的金币全部用完。

现在给定哲哲将要击杀的一系列怪物对应的金币数量，请你计算一下哲哲去消费了几次。

输入格式:
输入第一行是两个整数 N,M （1≤N≤1e3 ,1≤M≤1e6），表示击杀的怪物数量以及系统允许拥有金币数量的上限。

接下来一行是由空格隔开的 N 个数 Pi（i=1,⋯,N），依次表示击杀第 i 个怪物能获得的金币数量。
假设哲哲是按输入顺序击杀怪物的，并且每个 Pi都是 不超过 1e6的非负整数。

输出格式:
在一行中输出哲哲去消费的次数。

输入样例:

10 10
1 2 3 4 1 2 3 5 11 1

输出样例:

4

样例解释：
消费时间点为：第四个怪物击杀后、第七个怪物击杀后、第八个怪物击杀后、第九个怪物击杀后。

题解

题目很简单, 用循环进行模拟即可.我们在对数组进行求和的过程中, 每当sum加上当前元素的值要超过m, 我们就把sum置0, 同时计数器加1

AC代码

时间复杂度O(n)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int arr[N];

int main()
{
    
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> arr[i];

    int res = 0;
    int sum = 0;
    for(int i=1; i<=n; i++)
    {
    
        if(sum + arr[i] > m)
        {
    
            res++;
            sum = 0;
        }
        sum += arr[i];
    }
    cout << res << endl;
    return 0;
}

RC-u2 智能服药助手

智能看护中很重要的环节是安排需要服药的老年人的服药计划。

已知机器人需要照顾的某位老年人需要服用 N 种药物，但某些药物不宜间隔过短服用 —— 比如降糖药一般遵医嘱日服 3 次，两次之间需要间隔至少 4 小时。当需要服用的药物比较多，医嘱比较复杂时，如何保证每位老人的服药计划是安全合理的，就成为一个挑战。

本题给定一套服药计划，请你检查一下计划是否存在问题。

输入格式:
输入第一行给出两个整数 N,M（1≤N,M≤1e3），表示老人需要服用 N 种药物（药物种类从 1 到 N 编号），对应的服药计划有 M 条记录。

接下来首先在一行中给出 N 个用空格隔开的整数 Ti（−1≤Ti ≤100,Ti !=0)，表示编号为 i 的药物需要间隔至少 Ti个单位时间服用。如果 Ti为 −1，则说明这种药物没有间隔要求。

接下来的 M 行，每行给出一条服药计划中的记录，格式为：首先给出两个非负整数 t 和 k (0≤t≤1e9,0≤k≤N)，
表示服药的时刻为 t，服用了 k 种药物；然后紧接着列出 k 个数，每个数对应 t 时刻要吃的药物种类的编号。一行中的数字之间以空格分隔。

题目保证：记录按照服药时刻 t 的递增顺序给出；每一时刻服用的药物种类各不相同。注意：同一种药物可能需要在不同的时刻重复服用。如果一位老人在 ti时刻和 tj时刻服用了同一种药物，则他服用的间隔时间为 |ti-tj|.

输出格式:
按照输入顺序检查每一条记录中的每一种药物。如果在 Y 时刻不宜服用药物 X，则在一行中输出：

Don't take X at Y!

注意：老人收到提醒后会按照提醒不服用指定的药物。

输入样例:

10 6
1 2 3 4 5 -1 -1 -1 -1 -1
0 1 1
1 2 1 2
2 1 2
3 2 1 3
5 3 1 3 4
6 2 1 4

输出样例:

Don't take 2 at 2!
Don't take 3 at 5!
Don't take 4 at 6!

题解

仍然是简单模拟

记录按照服药时刻 t 的递增顺序给出；每一时刻服用的药物种类各不相同。

这是快速做出这道题的关键, 因为t是递增的, 假设要判断t时刻服用i药是否合理, 只需要判断t和上一次服用i药的时间间隔是否达标即可

不说更多废话, show you code

AC代码(带注释)

时间复杂度: O(m*k)

//
// Created by trudbot on 2022/7/12.
//

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int tim[N];//存放每种药服用的时间间隔
int last[N];//上一次服用某药的时间

int main() {
    
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
    
        cin >> tim[i];
        last[i] = -100;//初始化为一个很小的数， 保证第一次一定可以服用
    }

    int t, k;
    while ( m-- )
    {
    
        cin >> t >> k;
        int i;
        while( k-- )
        {
    
            cin >> i;//i为当前要服用的药
            if(tim[i] == -1)//无间隔要求， 直接跳过
                continue;
            if(t - last[i] >= tim[i])//间隔够大， 可以服用， 更新最后一次服用时间为当前时间
                last[i] = t;
            else
                printf("Don't take %d at %d!\n", i, t);
        }
    }
    return 0;
}

RC-u3 跑团机器人

在桌面角色扮演游戏（TRPG，俗称“跑团”）中，玩家需要掷出若干个骰子，根据掷出的结果推进游戏进度。在线上同样可以跑团，方法是由玩家们向机器人发出指令，由机器人随机产生每个需要掷出的骰子的结果。

玩家向机器人发出的指令是一个仅涉及加法和减法的表达式，即对若干个数字进行一系列加法或减法计算。这些数字可以是直接给出的非负整数（数字不超过 1000），也可以是若干个骰子掷出的结果。

“掷骰子”这个动作对应的指令格式为 xdy，表示摇动 x 个 y 面的骰子（1≤x≤1000,2≤y≤1000）。当 x 为 1 时，1 可以省略。

例如指令 2d3+3-d4的意思是：先掷出 2 个 3 面骰子（你不必考虑现实中是否存在这样的骰子），不妨假设结果为 1 和 3，则 2d3的结果就是两个骰子的面值之和 4；然后计算 4 + 3，得到结果为 7；再掷出 1 个 4 面骰子，不妨假设结果为 2，则计算 7 - 2 得到最终结果 5。

本题就请你计算玩家输入的指令里，不同种类的骰子需要掷出几个，以及可能得到的结果在什么区间范围内。

输入格式:
输入在一行中给出一条符合题目描述的玩家输入机器人的指令。题目保证指令长度不超过 2∗1e4。

输出格式:
首先输出不同种类的骰子分别需要掷出几个。每种骰子的信息占一行，依次输出骰子的面数和投掷的数量，按面数从小到大输出。

输入指令保证至少有一个骰子需要掷出。

最后一行输出两个数，表示根据输入指令可以得到的最小结果和最大结果。

同一行数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例:

d6+3d5+2-2d3+2d5

输出样例:

3 2
5 5
6 1
2 31

题解

运算符只有+/-, 所以我们不用考虑运算符的优先级, 用循环来完成即可.

基本的思想是每次循环处理一个指令(xdy)以及得到下一个指令的符号(正负), 但要注意操作数除了指令还有常量

在代码注释里进行更详细的讲解

AC代码(详细注释)

时间复杂度: O(n)

//
// Created by trudbot on 2022/7/12.
//

#include <bits/stdc++.h>
using namespace std;
map<int, int> num;//存储每种骰子被掷的总数
int Max, Min;//点数的最大最小值

void Solution(string str)
{
    
    //l指向当前要处理指令的第一个字符， sign为当前指令的正负号， 1为正， -1为负
    int r = str.length()-1, l = 0, sign = 1;

    while(l <= r)
    {
    
        int x = 0, y = 0;

        //读取x
        while(l<=r && str[l] != 'd' && str[l] != '+' && str[l] != '-')
            x = x*10 + str[l++] - '0';

        //读取完x后停止在d字符， 说明是一个指令
        if(str[l] == 'd')
        {
    
            if(x == 0) x = 1;//d前面没有字符时， x默认为1
            l++;
            //读取y
            while(l<=r && str[l] != '+' && str[l] != '-')
                y = y*10 + str[l++] - '0';
            num[y] += x;//y面骰子的掷数增加x
            if(sign == 1)
            {
    
                //为正时， Max加上最大数， Min加上最小数
                Max += y*x;//每次都掷y点
                Min += x;//每次都掷1点
            }
            else//为负时， 同上
            {
    
                Max -= x;
                Min -= y*x;
            }
        }
        else//读取完x后停止在+/-或越界， 说明是一个常量， 乘上符号直接加到Max, Min里即可
        {
    
            Max += sign*x;
            Min += sign*x;
        }

        if(l <= r)//此时l要么越界, 要么停在+/-
            sign = str[l++] == '+' ? 1 : -1;//判断下一个操作对象的符号， l后移指向它的第一个字符
    }
}


int main() {
    
    string str;
    cin >> str;
    Solution(str);

    for(auto i : num)
    {
    
        cout << i.first << " " << i.second << endl;
    }
    cout << Min << " " << Max << endl;

    return 0;
}

RC-u4 攻略分队

副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。

在 MMORPG《最终幻想14》里，有一个攻略人数最大达到 56 人的副本“巴尔德西昂兵武塔”，因为有在副本里死亡不能复活、机制比较整蛊等特点，一度被玩家视作洪水猛兽。

在副本的开始，我们会遇到第一个难关：攻略的玩家要分为两组，同时讨伐副本 BOSS “欧文”和“亚特”。

已知以下信息：

1. 玩家会组成 6 支队伍进入副本，其中第 i 队有 Vi位玩家（i=1,⋯,6）。
2. 每支队伍可能会有一些特殊角色：MT（主坦克）、工兵（负责探测陷阱）和指挥（负责指挥玩家）。

我们的任务是合理安排玩家的分组，以最大程度增加副本通过概率。分组的原则如下：

1. 要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组；
2. 每组必须有至少一个 MT（主坦克）。

如果满足上述原则的分组方案不唯一，则按照下列规则确定唯一解：

1. 优先选择每组有至少一个指挥和至少一个工兵的方案；
2. 如果规则 1 无法满足，则优先选择每组至少有一个指挥的方案；
3. 如果所有方案都不满足规则 2，或经过前 2 个规则筛选后，分组方案仍不唯一，则选择两边人数尽可能接近（即两边人数差尽可能小）的方案；
4. 如果满足规则 3 的方案还不唯一，选择讨伐“欧文”的人数比讨伐“亚特”的人数更多的方案；
5. 如果满足规则 4 的方案还不唯一，选择讨伐“欧文”的队伍编号方案中最小的一个。

注: 一个队伍编号方案A = {a1 < ··· < am} 比B = {b1 < ··· bn}小， 当且仅当存在1 <= k <= min(m, n)使得ai = bi， 对所有0 < i < k成立， 且ak < bk.
本题就请你给出满足所有分组原则的分配方案。

输入格式:
输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 V i(0≤Vi≤8,1≤i≤6)。队伍人数为 0 时表示队伍不存在。

随后 6 行，按队伍编号顺序，每行给出一支队伍的特殊角色，格式为 ABC，其中 A 对应 MT，B 对应工兵，C 对应指挥。三种角色对应取值 0 或 1，0 表示没有该角色，1 表示有。

注：由于可能存在一人兼任多个特殊角色的情况，所以一支队伍中的特殊角色数量有可能大于该队伍的玩家数量。

输出格式:
输出分两行，第一行输出讨伐“欧文”的队伍编号，第二行输出讨伐“亚特”的队伍编号。同一行中的编号按升序输出，以 1 个空格分隔，行首尾不得有多余空格。

如果不存在合法的方案，输出GG。

输入样例1:

6 8 7 5 3 0
010
101
110
001
111
000

输出样例1:

2 3
1 4 5

输入样例2:

6 8 7 5 3 0
010
101
010
001
011
000

输出样例2:

GG

题解

概述
这道题思路很简单， 但逻辑处理非常的复杂。
基本思想是暴力搜索， 我们枚举每一种方案， 将方案与目前最优的方案进行比较， 将最优方案更新为两者中最优的方案

枚举
将一组序列（1~6）分为两部分， 我们可以采用dfs+回溯来实现
假设要分为的两组为t1, t2
对于序列中每个数字, 都有两种选择:进入t1或进入t2. 所以我们分别让当前数字进入t1和t2, 然后继续枚举下一个数字, 当六个数字都枚举完成后我们就得到了一种组合, 此时我们再将当前组合与最优组合进行判断

vector<int> tmp1, tmp2;//存放两个组各自的成员

void dfs(int i)//i为队伍编号
{
    
    if(i > 6)//枚举完成, 进行判断
    {
    
        judge();
        return;
    }
    if(num[i] == 0)//当前队伍为空, 直接跳过
    {
    
        dfs(i+1);
        return;
    }
    
    //当i加入t1
    tmp1.push_back(i);
    dfs(i+1);
    tmp1.pop_back();

    //当i加入t2
    tmp2.push_back(i);
    dfs(i+1);
    tmp2.pop_back();
}

判断
太长太复杂, 请跳转到程序注释
为了避免多重嵌套循环, 在程序中大量的使用了return, 每次return都代表着当前判断结束

AC代码(含注释)

虽然很长但都很好懂
时间复杂度: O(n*2ⁿ), 当然n是确定的6, 主要是在判断时常数很大
但不用担心超时, 时间限制400ms, 实测每组样例都是3ms

#include <bits/stdc++.h>

using namespace std;
const int N = 7;
int num[N];//各队伍的人数
bool A[N], B[N], C[N];//各队伍是否有坦克、工兵、指挥
int totalA;//坦克的总数

//目前的最优方案， 1、2 对应 欧文、亚特
vector<int> ans1, ans2;
/* RO, R1, R2对应前三个规则所要求的性质 * R0: 是否满足 每组必须有至少一个 MT（主坦克）。 * R1: 是否满足 每组有至少一个指挥和至少一个工兵 * R2: 是否满足 每组至少有一个指挥 */
bool R0, R1, R2;


vector<int> tmp1, tmp2;//当前要判断的方案

void judge()
{
    
    //所有人都在一组， 不符合分组要求， 直接退出
    if(tmp1.empty() || tmp2.empty()) return;

    //当前方案的r0, r1, r2性质， 以及临时变量t1, t2
    bool r0, r1, r2, t1, t2;

    //判断方案的r0性质
    t1 = t2 = false;
    for(int i : tmp1)
        if( A[i] ) {
    
            t1 = true;
            break;
        }
    for(int i : tmp2)
        if( A[i] ) {
    
            t2 = true;
            break;
        }
    r0 = t1 && t2;
    if(!r0) return;//r0是硬性要求， 不满足直接不考虑

    //判断方案的r2性质, 先判断r2是因为r2是r1的组成部分
    t1 = t2 = false;
    for(int i : tmp1)
        if( C[i] ) {
    
            t1 = true;
            break;
        }
    for(int i : tmp2)
        if( C[i] ) {
    
            t2 = true;
            break;
        }
    r2 = t1 && t2;

    //判断方案的r1性质
    t1 = t2 = false;
    for(int i : tmp1)
        if( B[i] ) {
    
            t1 = true;
            break;
        }
    for(int i : tmp2)
        if( B[i] ) {
    
            t2 = true;
            break;
        }
    r1 = r2 && t1 && t2;

    //规则0, R0为false说明最优方案为空
    if( !R0 )
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }

    //规则1
    if(R1 && !r1) return;
    if(r1 && !R1)
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }

    //都不满足规则1时执行规则2
    if(!R1 && !r1)
    {
    
        if(R2 && !r2) return;
        if(r2 && !R2)
        {
    
            ans1 = tmp1, ans2 = tmp2;
            R0 = r0, R1 = r1, R2 = r2;
            return;
        }
    }

    //规则3
    int an1 = 0, an2 = 0, tn1 = 0, tn2 = 0;//各组人数
    for(int i : ans1) an1 += num[i];
    for(int i : ans2) an2 += num[i];
    for(int i : tmp1) tn1 += num[i];
    for(int i : tmp2) tn2 += num[i];
    
    int d1 = abs(an1 - an2), d2 = abs(tn1 - tn2);//人数差
    if(d1 < d2) return;
    if(d1 > d2)
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }

    //规则四
    t1 = (an1 > an2), t2 = (tn1 > tn2);
    if(t1 && !t2) return;
    if(t2 && !t1)
    {
    
        ans1 = tmp1, ans2 = tmp2;
        R0 = r0, R1 = r1, R2 = r2;
        return;
    }
    
    //规则5
    for(int k=0; k<ans1.size() && k < tmp1.size(); k++)
    {
    
        if(ans1[k] < tmp1[k]) return;
        else if(ans1[k] > tmp1[k])
        {
    
            ans1 = tmp1, ans2 = tmp2;
            R0 = r0, R1 = r1, R2 = r2;
            return;
        }
    }
    /* 可以发现虽然代码长, 但其实都差不多 基本就是: 如果最优方案满足某个规则而当前方案不满足, 判断结束 如果最优方案不满足某个规则而当前方案满足, 则当前方案替换最优方案, 判断结束 如果都满足, 执行下一个规则 */
}

void dfs(int i)
{
    
    if(i > 6)
    {
    
        judge();
        return;
    }
    if(num[i] == 0)
    {
    
        dfs(i+1);
        return;
    }
    tmp1.push_back(i);
    dfs(i+1);
    tmp1.pop_back();

    tmp2.push_back(i);
    dfs(i+1);
    tmp2.pop_back();
}

int main()
{
    
    for(int i=1; i<=6; i++)
        cin >> num[i];
    string ABC;
    for(int i=1; i<=6; i++)
    {
    
        cin >> ABC;
        if(ABC[0] == '1') A[i] = true, totalA++;
        if(ABC[1] == '1') B[i] = true;
        if(ABC[2] == '1') C[i] = true;
    }
    if(totalA < 2)//出现GG的情况有且仅有少于两个队伍有坦克
    {
    
        cout << "GG";
        return 0;
    }
    else
    {
    
        dfs(1);
        for(int i=0; i<ans1.size(); i++)
        {
    
            if(i != 0) cout << " ";
            cout << ans1[i];
        }
        cout << endl;
        for(int i=0; i<ans2.size(); i++)
        {
    
            if(i != 0) cout << " ";
            cout << ans2[i];
        }
    }
    return 0;
}

RC-u5 树与二分图

设 G=(V,E) 是一个无向图，如果顶点集合 V 可分割为两个互不相交的子集 (A,B)，并且每条边 (i,j)∈E 的两个端点 i 和 j 分别属于这两个不同的顶点子集，则称图 G 为一个二分图。

现在给定一棵树 T，要求选择树中两个没有边相连的结点 i 和 j，使得将无向边 (i,j) 加进 T 后能够构成二分图。你的任务是计算满足这个要求的选择方案有多少种。

输入格式:
输入第一行给出一个正整数 N (2≤N≤1e6)，表示树中结点的个数。

接下来 N−1 行，每行给出树中一条边的两端结点编号，以空格分隔。结点编号从 1 开始。题目保证输入给出的是一棵树中所有的边。

输出格式:
在一行中输出方案数。注意：连接 (1,2) 和 (2,1) 视作同一个方案。

输入样例:

7
1 2
2 3
2 4
2 5
2 6
4 7

输出样例:

4

题解

思路分析
二分图, 简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

不难发现, 树一定是二分图. 因为树很重要的一个性质是除根结点外每个结点有且仅有一个父结点, 所以我们可以把树中的每个结点与它的父结点放到两个不同的集合中, 最后整颗树的结点集都可以划分到两个不相交集合中.

所以题意就是, 对于给定的二分图, 最多能加多少边使得它仍是二分图

对于顶点数为n的二分图, 假设划分的两个集合顶点数分别为m , n-m. 显然这个二分图的最大边数为m*(n-m), 即每个顶点与对面集合所有顶点都形成的边.

由此, 我们只需要得出任一集合数量, 就可以算出最大边数, 减去已有边数即为答案

关键点实现

在存储问题上, 虽然题目给的是一棵树, 但我们仍然要将它当成图来看待, N比较大, 所以用邻接表来存图.

int h[N], e[N], ne[N], idx;

void add(int x, int y)
{
    
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

在获取某个集合中顶点数量的问题上, 我们可以用类似染色法的技巧对图进行一次遍历.
用布尔值true/false来代表两种颜色, 只对一种颜色进行计数.
当前顶点的邻接点的颜色一定与当前顶点相反, 即在另一个集合

bool st[N];
ll m;
void dfs(int v, bool color)
{
    
    st[v] = true;
    if(color) m++;
    for(int i=h[v]; i!=-1; i=ne[i])
    {
    
        int j = e[i];
        if(!st[j]) dfs(j, !color);
    }
}

AC代码

时间复杂度: 朴素的图遍历, O(n+m), n是顶点数, m是边数

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1e6 + 10;

ll n;
int h[N], e[N], ne[N], idx;

void add(int x, int y)
{
    
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

bool st[N];
ll m;
void dfs(int v, bool color)
{
    
    st[v] = true;
    if(color) m++;
    for(int i=h[v]; i!=-1; i=ne[i])
    {
    
        int j = e[i];
        if(!st[j]) dfs(j, !color);
    }
}

int main()
{
    
    cin >> n;
    for(int i=1; i<=n; i++) h[i] = -1;
    int x, y;
    for(int i=1; i<n; i++)
    {
    
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    dfs(1, true);//从任一顶点开始遍历
    cout << m*(n-m) - (n-1);
    return 0;
}

注意m不能为int, 否则最后相乘会爆

---

嘿哥们, 都看到这了就点个赞吧~