P9966 [THUPC 2024 初赛] 机器人题解

Lazy_Labs · 2023-12-20 18:40:18 · 题解

-1.HACK

HACK1

输入 1：

2 2 7
1 1
REPLACE 0 1 MOVE 0 1
MIRROR 0 1
0 0
SLACKOFF
REPLACE 0 2 SLACKOFF

输出 1：（着重看最后一行的 left）

Robot 0 replaces a line of command of Robot 1.
Robot 0 modifies a line of command of Robot 1.
Robot 1 moves its right hand towards Robot 1.
Robot 1 replaces a line of command of Robot 0.
Robot 0 replaces a line of command of Robot 1.
Robot 0 slacks off.
Robot 1 moves its left hand towards Robot 1.

错于此，转到 坑点1。

HACK2

输入 2：

2 2 4
1 1
MOVE 0 1
ACTIVATE 0
0 0
SLACKOFF
SLACKOFF

输出 2：（着重看最后一行）

Robot 0 moves its left hand towards Robot 0.
Robot 0 activates Robot 0.
Robot 0 moves its left hand towards Robot 1.
Robot 0 activates Robot 1.

错于此，转到 坑点2。

HACK3

感谢用户 codingwen 在这个贴子中发现的问题。

3 3 11
2 2
SWAP 0 2 2
SWAP 1 2 2
SWAP 1 2 1
1 2
MIRROR 0 2
REPLACE 1 2 SLACKOFF
SLACKOFF
0 2
SLACKOFF
ACTIVATE 1
MIRROR 0 3

问题在于原代码中，Replace 的 update 函数中，当恰好更改到当前的指令时，hrbt 会变化，与 坑点2 的错误一致。

修改方法同 坑点2，提前记录下 hrbt 即可。

（还是 Replace 操作修改到自身的概率太低了，导致我都退役了才被叉）

0.前言

你说得对，但是这篇题解很蠢，可能对继承的理解也不是很深，有更简单的写法可以提出来，shaber 作者学习一下。

1.继承

定义一个 struct Command 表示一个指令的基类。可以共用同名函数（需要用虚函数即 virtual），以及同名变量。

代码如下（变量解释见注释）：

struct Command
{
    int id;//表示指令的类型，实际上也可以不计这个，直接使用typeid或者其他来实现，id 按照题目指令依次为 1~6。
    bool h,tri;//h:这条指令的 h，tri:这条指令是否是trigger触发的
    inline virtual void init()=0;//这条指令的初始化
    inline virtual void update(int rbt,int cid)=0;//执行这条指令
};

下面以 SLACKOFF 来举个例子：

struct Slackoff:Command //:后接继承的函数
{
    inline void update(int rbt,int cid)override//表示 Command 的虚函数
    {
        printf("Robot %d slacks off.\n",rbt);if(!--k)exit(0);//输出
        if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);//检查右手的 trigger 条件
    }
    inline void init()override{id=0;tri=0;}//tri=0 不为 trigger 指令，id 为 0
};

一些实现：

dynamic_cast<Trigger*>cmd

可以强制转化 cmd 为 Trigger 类，此时就可以调用 Trigger 专属的函数。

2.指令类

刚刚介绍过了。

3.机器人类

需要存储这个机器人的所有指令，此时可以直接使用 Command* cmd[10]; 来描述这个机器人的指令。

注意，基类不能直接使用 Command 定义，定义时一定要用像 Slackoff 这样的类定义。

此时继承的方便性就呈现出来了，当你要依次激活这个机器人的指令的时候，只需要：

for(int i=0;i<m;i++)cmd[i]->update(...);//内部填的啥待会再说

就行了。

具体的，机器人类目前要存储：

int rbt; 表示当前机器人的编号；
int hd[2]; 表示机器人的左右手指向；
Command* cmd[10]; 表示机器人的所有指令。

4.基础指令

代码最后会统一给出。

4.1 SLACKOFF 和 MOVE

对于所有指令来说，我们知道它们属于某个固定的机器人，于是在执行 update 时要传入 rbt 表示这个指令是由哪个机器人执行的。

SLACKOFF 刚刚介绍过了，不再阐述。

MOVE 指令要新存一个变量 z，表示和题目相同。

Move 内实现的 init 便需要读入 h 和 z。

对于 Move 的 update，我们要找到这个机器人的 h 手，即 Rbt[rbt].hd[h] （为了方便，我们将其定义为 hrbt），然后将其循环移位即可。注意输出要在移位后执行。

4.2 SWAP，MIRROR，REPLACE

这三个指令是对机器人内部的指令进行修改，具体实现如下：

SWAP

十分简单，直接交换两个机器人的 Command 指针即可。

REPLACE

发现这个指令内部要记一个指令指针 Command* comd，表示这个指令替换时替换成的指令，update 也很好实现：只要把目标位置上的指令指针指向 comd 即可。

坑点3

同坑点2，具体的在 HACK3 中叙述过了。

只是作者代码写的太烂了，估计不算什么坑点。

MIRROR

也很简单，只要把目标指令的 h 值异或一下即可。

吗？

坑点1

考虑一组 hack：

2 2 7
1 1
REPLACE 0 1 MOVE 0 1
MIRROR 0 1
0 0
SLACKOFF
REPLACE 0 2 SLACKOFF

按照我们的想法，最后一句输出：Robot 1 moves its right hand towards Robot 1.，实际上应该是 left hand。

我们发现一件事：当 MIRROR 指令反转的是 REPLACE 过后的指令时，此时直接更改了 REPLACE 指令内部的 comd。然而我们只想要反转真实的指令：

此时就要在机器人类中记一个 h[10] 表示每个指令的“反转标记”，那么，对于所有 update 函数来说，我们就要传入一个 cid 表示当前指令是 rbt 的第几条指令，然后使用 Rbt[rbt].hd[Rbt[rbt].h[cid]^h] 来表示当前指令的手。

PS：其实可以把指令中的 h 和机器人类中的 h 合并的，但是我懒，于是就直接改了。

再次考虑有无其他可能更改 comd 的指令，发现没有，那么考虑适配：

SWAP：要多交换两条指令的 h 数组中的数字。

REPLACE：要将当前指令的 h 数组置为 0。

MIRROR：只要将指向指令的 h 数组取反即可。

于是，我们便完成了基础指令。

5.高级指令

和普通指令没有区别，也是继承基类 Command。

5.1 ACTIVATE

update 中直接执行 for(int i=0;i<m;i++)Rbt[hrbt].cmd[i]->update(hrbt,i); 即可。

吗？

坑点 2

你发现一件事，执行每条指令的 update 时，当前机器人的手可能会动，所以不能直接用 hrbt，而是要在 for 前将指向的机器人存下来。

5.2 TRIGGER

TRIGGER 指令要存储的信息有：type 表示检测的条件，comd 表示执行的指令。

读题，发现 TRIGGER 指令是在每次指令操作结束后都有可能执行，于是对于机器人类定义一个函数，表示查找是否会执行 TRIGGER 指令。代码如下：

inline void check_trigger(Command* comd)
{
    for(int i=0;i<m;i++)if(cmd[i]->id==6)
    if(dynamic_cast<Trigger*>(cmd[i])->type==6)
    {
        if(comd->tri)return dynamic_cast<Trigger*>(cmd[i])->work(rbt,i);
    }
    else if(dynamic_cast<Trigger*>(cmd[i])->type==comd->id)
    return dynamic_cast<Trigger*>(cmd[i])->work(rbt,i);
}

注意到题目中的：其他机器人，所以我们要在所有的 update 后执行：

if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);

其中 dynamic_cast<Trigger*> 为强转为 Trigger 类，且 id 比较也可以用 typeid 来解决。

介于 TRIGGER 并没有实际执行，所以其 update 为空，新开一个 work 函数，作为执行 TRIGGER 时调用的函数。代码：

inline void work(int rbt,int cid){comd->update(rbt,cid);}

至此，我们完成了所有指令。

6.读入指令

定义一个函数 create 表示读入一个指令并且返回一个 Command*。

代码容易实现（可能有更好的实现，你说的对，但是）：

inline Command* create()
{
    string s;cin>>s;Command *comd;
    if(s=="SLACKOFF")comd=new Slackoff;
    else if(s=="MOVE")comd=new Move;
    else if(s=="SWAP")comd=new Swap;
    else if(s=="MIRROR")comd=new Mirror;
    else if(s=="REPLACE")comd=new Replace;
    else if(s=="ACTIVATE")comd=new Activate;
    else if(s=="TRIGGER")comd=new Trigger;
    comd->init();
    return comd;
}

我们来考虑实现每个指令的 init。

6.1 SLACKOFF，SWAP，MIRROR，ACTIVATE

这四种指令的 init 是容易的，直接读入并将 id 和 tri 赋值即可。

6.2 REPLACE

comd=create() 就能完成，剩余部分同上。

6.3 TRIGGER

最前面的 COMMANDNAME 确定 type，剩余部分同上。

至此，所有部分都完成了。

7.完整代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x(0),f(1);char c=getchar();
    while(c<'0'||c>'9')f=c=='-'?-1:1,c=getchar();
    while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
    return x*f;
}
#define hrbt Rbt[rbt].hd[h^Rbt[rbt].h[cid]]
int n,m,k;
struct Command
{
    int id;bool h,tri;
    inline virtual void init()=0;
    inline virtual void update(int rbt,int cid)=0;
};
inline Command* create();
struct Trigger:Command
{
    int type;Command* comd;
    inline void init()override
    {
        string s;cin>>s;
        if(s=="SLACKOFF:")type=0;
        else if(s=="MOVE:")type=1;
        else if(s=="SWAP:")type=2;
        else if(s=="MIRROR:")type=3;
        else if(s=="REPLACE:")type=4;
        else if(s=="ACTIVATE:")type=5;
        else if(s=="TRIGGER:")type=6;
        comd=create();
        id=6;tri=0;comd->tri=1;
    }
    inline void update(int rbt,int cid)override{};inline void work(int rbt,int cid){comd->update(rbt,cid);}
};
struct Robot
{
    int hd[2],rbt;Command* cmd[10];bool h[10];
    inline void check_trigger(Command* comd)
    {
        for(int i=0;i<m;i++)if(cmd[i]->id==6)
        if(dynamic_cast<Trigger*>(cmd[i])->type==6)
        {
            if(comd->tri)return dynamic_cast<Trigger*>(cmd[i])->work(rbt,i);
        }
        else if(dynamic_cast<Trigger*>(cmd[i])->type==comd->id)
        return dynamic_cast<Trigger*>(cmd[i])->work(rbt,i);
    }
}Rbt[110];
struct Slackoff:Command
{
    inline void update(int rbt,int cid)override{printf("Robot %d slacks off.\n",rbt);if(!--k)exit(0);
    if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);}
    inline void init()override{id=0;tri=0;}
};
inline void move(int &x,int y){x=(x+y)%n;}
struct Move:Command
{
    int z;
    inline void init()override{h=read();z=read();id=1;tri=0;}
    inline void update(int rbt,int cid)override
    {
        move(hrbt,z);
        printf("Robot %d moves its %s hand towards Robot %d.\n",rbt,h^Rbt[rbt].h[cid]?"right":"left",hrbt);if(!--k)exit(0);
        if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);
    }
};
template<typename T>
inline void swaps(T &a,T &b,bool &ta,bool &tb){swap(a,b);swap(ta,tb);}
struct Swap:Command
{
    int x,y;
    inline void init()override{h=read();x=read()-1;y=read()-1;id=2;tri=0;}
    inline void update(int rbt,int cid)override
    {
        printf("Robot %d swaps a line of command with Robot %d.\n",rbt,hrbt);if(!--k)exit(0);
        swaps(Rbt[rbt].cmd[y],Rbt[hrbt].cmd[x],Rbt[rbt].h[y],Rbt[hrbt].h[x]);
        if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);
    }
};
struct Mirror:Command
{
    int x;
    inline void init()override{h=read();x=read()-1;id=3;tri=0;}
    inline void update(int rbt,int cid)override
    {
        printf("Robot %d modifies a line of command of Robot %d.\n",rbt,hrbt);if(!--k)exit(0);
        Rbt[hrbt].h[x]^=1;
        if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);
    }
};
struct Replace:Command
{
    int x;Command* comd;
    inline void init()override
    {
        h=read();x=read()-1;
        comd=create();
        id=4;tri=0;
    }
    inline void update(int rbt,int cid)override
    {
        printf("Robot %d replaces a line of command of Robot %d.\n",rbt,hrbt);if(!--k)exit(0);
        // Rbt[hrbt].h[x]=0;Rbt[hrbt].cmd[x]=comd; 感谢 codingwen 发现此行的错误
        int qwq=hrbt;Rbt[qwq].h[x]=0;Rbt[qwq].cmd[x]=comd;
        if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);
    }
};
struct Activate:Command
{
    inline void init()override{h=read();id=5;tri=0;}
    inline void update(int rbt,int cid)override
    {
        printf("Robot %d activates Robot %d.\n",rbt,hrbt);if(!--k)exit(0);
        int qwq=hrbt;for(int i=0;i<m;i++)Rbt[qwq].cmd[i]->update(qwq,i);
        if(Rbt[rbt].hd[1]!=rbt)Rbt[Rbt[rbt].hd[1]].check_trigger(this);
    }
};
inline Command* create()
{
    string s;cin>>s;Command *comd;
    if(s=="SLACKOFF")comd=new Slackoff;
    else if(s=="MOVE")comd=new Move;
    else if(s=="SWAP")comd=new Swap;
    else if(s=="MIRROR")comd=new Mirror;
    else if(s=="REPLACE")comd=new Replace;
    else if(s=="ACTIVATE")comd=new Activate;
    else if(s=="TRIGGER")comd=new Trigger;
    comd->init();
    return comd;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=0;i<n;i++)
    {
        Rbt[i].hd[0]=read(),Rbt[i].hd[1]=read();Rbt[i].rbt=i;
        for(int j=0;j<m;j++)Rbt[i].cmd[j]=create();
    }
    for(int i=0;;(i=i+1)%=n)for(int j=0;j<m;j++)Rbt[i].cmd[j]->update(i,j);
    return 0;
}

P9966 [THUPC 2024 初赛] 机器人 题解