题解：P9966 [THUPC 2024 初赛] 机器人
Recall_cpp · · 题解
看大家都是用指针写的，来篇非指针链表的题解。
对于每一个指令，可以看成是一条链，对于不是 REPLACE 或者 TRIGGER 的指令，这条链上只有一个元素，而对于这两个指令，就可以把后续读入的指令接到前一个指令的后面，形成一个链表。
存指令时，只需要记录该指令的链表的头结点即可。
读入
不是 REPLACE 或者 TRIGGER 的指令，直接读入即可。
这两个指令可以递归读入。
基础指令
SLACKOFF 指令
最简单的一个，直接输出即可。
MOVE 指令
判断一下左右手，把当前手指向的人的编号加上
SWAP 指令
把两条指令对应的链表的头结点交换一下。
MIRROR 指令
把操作中的
REPLACE 指令
基础指令中最难的一个。
一个很基础的想法是，直接把后面的指令的起始结点作为需要替换指令的头节点。
但这样会有一个问题，这两个指令同时指向链表中的同一个结点，对于 MIRROR 指令，会一次修改到两个结点。
正确的方法是把后面的指令复制到一个空的结点里，把需要替换的指令改成新复制的指令。
高级指令
ACTIVATE 指令
非常简单，把目标的所有不是 TRIGGER 的指令都跑一遍就行。
TRIGGER 指令
首先，对于每一条执行完的指令，都要检查一下有没有触发改指令。
第一种触发方式，很简单，直接判断一下就行。
对于第二种，可以设置一个变量，看看是不是由 TRIGGER 指令触发的。
需要注意 ACTIVATE 指令中所执行的指令并不能触发 TRIGGER 指令。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define endl '\n'
#define fi first
#define se second
#define pii pair<int,int>
#define p_q priority_queue
#define iter iterator
#define pb push_back
#define eps 1e-8
#define oper operator
#define mk make_pair
#define ls x<<1
#define rs x<<1|1
int n,m,k,tot=0;
struct node{
int s,s1;
int h,x,y,nxt,z;
}a[1000005];
struct robot{
int l,r;
int head[15];
}r[105];
map<string,int>mp;
int readin(){
tot++;
int x=tot;
string s;
cin>>s;
a[tot].s=mp[s];
if(s=="MOVE"){
cin>>a[tot].h>>a[tot].z;
}
else if(s=="SWAP"){
cin>>a[tot].h>>a[tot].x>>a[tot].y;
}
else if(s=="MIRROR"){
cin>>a[tot].h>>a[tot].x;
}
else if(s=="REPLACE"){
cin>>a[tot].h>>a[tot].x;
a[tot].nxt=readin();
}
else if(s=="ACTIVATE"){
cin>>a[tot].h;
}
else if(s=="TRIGGER"){
string ss,t="";
cin>>ss;
for(int i=0;i<ss.size()-1;i++){
t+=ss[i];
}
a[tot].s1=mp[t];
a[tot].nxt=readin();
}
return x;
}
void Do(int x,int y,bool is_trigger);
void checktrigger(int x,int y,bool is_trigger){
int X=r[x].r;
if(x==X) return ;
for(int i=1;i<=m;i++){
int Y=r[X].head[i];
if(a[Y].s==7){
bool F=0;
if(a[Y].s1==7){
if(is_trigger) F=1;
}else{
if(a[Y].s1==a[y].s) F=1;
}
if(F){
Do(X,a[Y].nxt,1);
return ;
}
}
}
}
void Do(int x,int y,bool is_trigger){
if(k==0) exit(0);
k--;
if(a[y].s==1){
printf("Robot %d slacks off.\n",x);
}else if(a[y].s==2){
printf("Robot %d moves its ",x);
if(a[y].h==0) cout<<"left hand towards Robot ";
else cout<<"right hand towards Robot ";
if(a[y].h==0){
r[x].l=(r[x].l+a[y].z)%n;
cout<<r[x].l;
}
else{
r[x].r=(r[x].r+a[y].z)%n;
cout<<r[x].r;
}
cout<<".\n";
}
else if(a[y].s==3){
int X=r[x].l;
if(a[y].h==1) X=r[x].r;
printf("Robot %d swaps a line of command with Robot %d.\n",x,X);
swap(r[x].head[a[y].y],r[X].head[a[y].x]);
}else if(a[y].s==4){
int X=r[x].l;
if(a[y].h==1) X=r[x].r;
printf("Robot %d modifies a line of command of Robot %d.\n",x,X);
int Y=r[X].head[a[y].x];
if(a[Y].s!=1&&a[Y].s!=7){
a[Y].h^=1;
}else if(a[Y].s==7){
Y=a[Y].nxt;
if(a[Y].s!=1){
a[Y].h^=1;
}
}
}else if(a[y].s==5){
int X=r[x].l;
if(a[y].h==1) X=r[x].r;
printf("Robot %d replaces a line of command of Robot %d.\n",x,X);
tot++;
r[X].head[a[y].x]=tot;
a[tot]=a[a[y].nxt];
int Y=a[y].nxt;
if(a[Y].s==7){
tot++;
a[tot-1].nxt=tot;
a[tot]=a[a[Y].nxt];
}
}else if(a[y].s==6){
int X=r[x].l;
if(a[y].h==1) X=r[x].r;
printf("Robot %d activates Robot %d.\n",x,X);
for(int i=1;i<=m;i++){
if(a[r[X].head[i]].s!=7) Do(X,r[X].head[i],0);
}
}
if(!k) exit(0);
checktrigger(x,y,is_trigger);
}
int main(){
// freopen("5.in","r",stdin);
// freopen("5.out","w",stdout);
mp["SLACKOFF"]=1;
mp["MOVE"]=2;
mp["SWAP"]=3;
mp["MIRROR"]=4;
mp["REPLACE"]=5;
mp["ACTIVATE"]=6;
mp["TRIGGER"]=7;
cin>>n>>m>>k;
for(int i=1;i<=500000;i++){
a[i].h=0;
a[i].nxt=0;
a[i].s=0;
a[i].s1=0;
a[i].x=0;
a[i].y=0;
a[i].z=0;
}
for(int i=0;i<n;i++){
cin>>r[i].l>>r[i].r;
for(int j=1;j<=m;j++){
r[i].head[j]=readin();
}
}
while(1){
for(int i=0;i<n;i++){
for(int j=1;j<=m;j++){
if(a[r[i].head[j]].s!=7) Do(i,r[i].head[j],0);
}
}
}
return 0;
}