P9966 [THUPC2024 初赛] 机器人

· · 题解

THUPC 2024 初赛 F 题。

我赛场上写完 C 就来写这题写了三个小时才过，讲一下大致的思路：

首先如果没有 REPLACE，那么所有的操作都可以暴力进行，输入也很简单。TRIGGER 看似是这题核心的复杂操作，其实只是徒增代码的简单玩意罢了，因为注意到 m \le 10 而且 TRIGGER 只会套基础指令，所以 TRIGGER 是可以暴力的。

有 REPLACE 的话，问题就变得复杂了起来。REPLACE 里面还可以套 REPLACE。题目没有限制一条 REPLACE 指令的长度，只限制了总长度。如果我们每次都把一条超长的指令 REPLACE 来 REPLACE 去肯定就炸了。

聪明的你或许已经想到了，我们可以给指令编号，然后只记录被 REPLACE 的指令的编号。REPLACE 的时候只改变机器人指令列表里的指令编号就可以了。实现上讲，对于每个指令，我们可以记录它的 COMMAND 参数（如果有的话）指向的指令编号，存下其他参数。递归读入即可。

struct command{
    int t,h,x,y,to;
}f[2000005];
int tot=0;
// t 表示指令类型，h,x,y 与题意相同（z 是 x），to 表示 REPLACE 和 TRIGGER 指令的子指令。
void readCommand(command &c){
    scanf("%s",tmp);
    c.t=tmp[1];
    if(tmp[1]=='O'){
        c.h=read();
        c.x=read();
    }
    else if(tmp[1]=='W'){
        c.h=read();
        c.x=read();
        c.y=read();
    }
    else if(tmp[1]=='I'){
        c.h=read();
        c.x=read();
    }
    else if(tmp[1]=='E'){
        c.h=read();
        c.x=read();
        c.to=++tot;
        readCommand(f[tot]);//读入 COMMAND 参数
    }
    else if(tmp[1]=='C'){
        c.h=read();
    }
    else if(tmp[1]=='R'){
        scanf("%s",tmp);
        c.x=tmp[1];
        c.to=++tot;
        readCommand(f[tot]);
    }
}
//一种读入指令的方式
// SWAP 和 REPLACE 都只需要对编号进行操作，这里以 REPLACE 为例，cd 指的就是覆盖的操作编号，a[id].cid[] 是 id 号机器人的指令编号列表。
void rEplace(int id,int x,int cd,int from,int g){
    if(k<=0)return;
    --k;
    a[id].cid[x]=cd;
    printf("Robot %d replaces a line of command of Robot %d.\n",from,id);
    if(from!=a[from].r)trytrigger(a[from].r,'E',g);
}

写到这里问题就来了，这题的其他所有操作都不会改变指令本身（包括 REPLACE 本质上也只是动一动编号而已），但是 MIRROR 不是这样。MIRROR 操作之后得到的指令是原来不存在的，因此我们需要对指令本身进行修改。

注意到 MIRROR 机器人 id 的第 x 条指令（编号 cd）的时候，我们不能直接 f[cd].h^=1;，因为这条指令可能同时在被多个机器人使用（比如被 REPLACE 到了很多地方），而你只能改其中的一个。

这时候，我们利用类似可持久化的思路，新建一个和 cd 一样的指令，MIRROR 这个新的指令，并把机器人 id 的第 x 条指令指向这个新的指令就可以了。

注意在 MIRROR 一个 TRIGGER 的时候，由于更改的是基础指令，基础指令和 TRIGGER 我们都需要复制。

void mIrror(int id,int x,int from,int g){
    if(k<=0)return;
    --k;
    int &i=a[id].cid[x];
    if(f[i].t!='R'){
        f[++tot]=f[i];
        f[tot].h^=1;
        i=tot;
    }
    else{
        f[++tot]=f[i];
        f[++tot]=f[f[i].to];
        //新建两个指令
        f[tot].h^=1;
        f[tot-1].to=tot;
        i=tot-1;
    }
    printf("Robot %d modifies a line of command of Robot %d.\n",from,id);
    if(from!=a[from].r)trytrigger(a[from].r,'I',g);
}

然后就是注意一些细节，比如 TRIGGER 不会被自己触发（很奇怪的设计）。以及如果 TRIGGER 触发导致某个基础指令（以 SLACKOFF 为例）运行，那么 TRIGGER TRIGGER: 和 TRIGGER SLACKOFF: 都可以被这个 SLACKOFF 触发。

这题可能会用到声明与定义分离的写法。

我的实现比较丑陋，优雅的实现可能应该有一个 void runCommand(int robotid,command c) 表示运行一条指令。

由于每运行一条指令都只会调用一次 trytrigger，所以时间复杂度是 O(km+|I|)，其中 |I| 是输入大小，|I| \le 5 \times 10^6。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,c=getchar(),f=1;
    while(c<'0' || c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return f==1?x:-x;
}
struct command{
    int t,h,x,y,to;
}f[2000005];
struct robot{
    int cid[15];
    int l,r;
    int hand(int v){
        return v==0?l:r;
    }
}a[105];
int tot=0;
char tmp[15];
int n,m,k;
void readCommand(command &c){
    scanf("%s",tmp);
    c.t=tmp[1];
    if(tmp[1]=='O'){
        c.h=read();
        c.x=read();
    }
    else if(tmp[1]=='W'){
        c.h=read();
        c.x=read();
        c.y=read();
    }
    else if(tmp[1]=='I'){
        c.h=read();
        c.x=read();
    }
    else if(tmp[1]=='E'){
        c.h=read();
        c.x=read();
        c.to=++tot;
        readCommand(f[tot]);
    }
    else if(tmp[1]=='C'){
        c.h=read();
    }
    else if(tmp[1]=='R'){
        scanf("%s",tmp);
        c.x=tmp[1];
        c.to=++tot;
        readCommand(f[tot]);
    }
}
void trytrigger(int,int,int);
void sLackoff(int id,int g){
    if(k<=0)return;
    --k;
    printf("Robot %d slacks off.\n",id);
    if(id!=a[id].r)trytrigger(a[id].r,'L',g);
}
void mOve(int id,int h,int x,int g){
    if(k<=0)return;
    --k;
    if(h==0){
        a[id].l=(a[id].l+x)%n;
        printf("Robot %d moves its left hand towards Robot %d.\n",id,a[id].l);
    }
    else{
        a[id].r=(a[id].r+x)%n;
        printf("Robot %d moves its right hand towards Robot %d.\n",id,a[id].r);
    }
    if(id!=a[id].r)trytrigger(a[id].r,'O',g);
}
void sWap(int id,int id2,int x,int x2,int g){
    if(k<=0)return;
    --k;
    swap(a[id].cid[x],a[id2].cid[x2]);
    printf("Robot %d swaps a line of command with Robot %d.\n",id,id2);
    if(id!=a[id].r)trytrigger(a[id].r,'W',g);
}
void mIrror(int id,int x,int from,int g){
    if(k<=0)return;
    --k;
    int &i=a[id].cid[x];
    if(f[i].t!='R'){
        f[++tot]=f[i];
        f[tot].h^=1;
        i=tot;
    }
    else{
        f[++tot]=f[i];
        f[++tot]=f[f[i].to];
        f[tot].h^=1;
        f[tot-1].to=tot;
        i=tot-1;
    }
    printf("Robot %d modifies a line of command of Robot %d.\n",from,id);
    if(from!=a[from].r)trytrigger(a[from].r,'I',g);
}
void rEplace(int id,int x,int cd,int from,int g){
    if(k<=0)return;
    --k;
    a[id].cid[x]=cd;
    printf("Robot %d replaces a line of command of Robot %d.\n",from,id);
    if(from!=a[from].r)trytrigger(a[from].r,'E',g);
}
void aCtivate(int id,int from,int g){
    if(k<=0)return;
    if(from!=-1){
        printf("Robot %d activates Robot %d.\n",from,id);
        --k;
    }
    for(int i=1;i<=m;i++){
        command c=f[a[id].cid[i]];
        if(c.t=='L')sLackoff(id,0);
        else if(c.t=='O')mOve(id,c.h,c.x,0);
        else if(c.t=='W')sWap(id,a[id].hand(c.h),c.y,c.x,0);
        else if(c.t=='I')mIrror(a[id].hand(c.h),c.x,id,0);
        else if(c.t=='E')rEplace(a[id].hand(c.h),c.x,c.to,id,0);
        else if(c.t=='C')aCtivate(a[id].hand(c.h),id,0);
    }
    if(from!=-1 && from!=a[from].r)trytrigger(a[from].r,'C',g);
}
void trytrigger(int id,int ft,int g){
    if(k<=0)return;
    for(int i=1;i<=m;i++){
        command c=f[a[id].cid[i]];
        if(c.t=='R' && (c.x==ft || (c.x=='R' && g==1))){
            c=f[c.to];
            if(c.t=='L')sLackoff(id,1);
            else if(c.t=='O')mOve(id,c.h,c.x,1);
            else if(c.t=='W')sWap(id,a[id].hand(c.h),c.y,c.x,1);
            else if(c.t=='I')mIrror(a[id].hand(c.h),c.x,id,1);
            else if(c.t=='E')rEplace(a[id].hand(c.h),c.x,c.to,id,1);
            else if(c.t=='C')aCtivate(a[id].hand(c.h),id,1);
            break;
        }
    }

}
int main(){
    n=read();
    m=read();
    k=read();
    for(int i=0;i<n;i++){
        a[i].l=read();
        a[i].r=read();
        for(int j=1;j<=m;j++){
            a[i].cid[j]=++tot;
            readCommand(f[tot]);
        }
    }
    int it=0;
    while(k>0){
        aCtivate(it,-1,0);
        it=(it+1==n?0:it+1);
    }
    return 0;
}