1 条题解

  • 0
    @ 2025-8-24 22:53:27

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Lazy_Labs
    如果你仍思念的话 就回来吧

    搬运于2025-08-24 22:53:27，当前版本为作者最后更新于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;
}
    • 1

    [THUPC 2024 初赛] 机器人

    信息

    ID
    9583
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 24ms