题解：CF1970F3 Playing Quidditch (Hard)

题意简述

有红蓝两队玩寇地奇。队员分别为 R0,R1,...,R9 和 B0,B1,...,B9 （有些队员可以不出现）。场地为一个

N \times M

的长方形。场地上除了有队员以外还有：

.Q，球。
.B，游走球。
.S，金飞贼。
RG 或 BG，分别表示红球门和蓝球门。

每一个时刻

0 \le t<T

，给定一个单位（队员或者游走球），有以下事件：

WASD，单位移动。
C，后面跟一个单位（球或金飞贼），表示单位抓住球或金飞贼。
T，表示单位投球。

在球被队员抓住时，球会跟着队员移动。

程序要按照

t

从小到大依次输出以下类型的事件：

球进球门了。此时球的坐标恰好和一个球门重合且没有被队员抓住。没有被进球门的一方得分加一。并且在这之后球会移动到场中心。
队员被淘汰了。此时队员的坐标恰好和游走球重合。
队员抓到金飞贼了。此时队员抓住金飞贼。抓住金飞贼的得分加十，且立即结束比赛。

在最后，输出红蓝两队的得分。

以上内容仅为题意简述，更多条件见原题面。

题解

~~大模拟的实际难度应该是显示的难度降两档才对。~~

直接按题意模拟事件。我们需要处理：

每个单位的坐标。
球是否被抓住，如果是的话，被谁抓住。
哪些队员活着。
两队的得分。

枚举每一时刻，我们可以先根据发生的事件简单处理坐标更新、球被抓住的状态更新。然后再依次处理每个事件。发生的事件处理如下：

单位移动，直接移动单位即可。题目保证移动到的新坐标一定是有效的。
抓住球或金飞贼，抓住球的话更新球的状态。
投球，更新球的状态。

然后依次处理要求输出的每个事件：

如果球被抓住了，更新球的坐标为队员坐标。
如果球没被抓住，检查球是否在球门，是的话输出，加得分，最后更新球的坐标为场中心。
遍历还活着的球员，检查是否碰到游走球。被游走球抓住的队员手上有球的话同时把手中的球丢弃。
按照字典序输出碰到游走球的队员。
检查金飞贼是否被抓住。是的话输出，加得分，最后结束枚举时刻的循环。
在结束循环后，输出得分。

代码基本是按照上述流程走的。

CPP

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int p,n,m,T;
int scorer,scoreb;
pair<int,int> pos[31];
int gtype[101][101];//=0没有球门，=1红球门，=2蓝球门
vector<int> alive,nxt,elim;
/*
-21 红球门
-11 蓝球门
-1 floor
00-09 R0-R9 
10-19 B0-B9 
21 Quaffle
22 Bludger
23 Golden Snitch
*/
int catching=-1;
int toid(string s){
	if(s=="RG")	return -21;
	if(s=="BG")	return -11;
	if(s==".Q")	return 21;
	if(s==".B")	return 22;
	if(s==".S")	return 23;
	if(s=="..")	return -1;
	if(s[0]=='R')	return s[1]-'0';
	else	return s[1]-'0'+10;
}
string tostr(int id){
	if(id==-1)	return "NONE";
	if(id<10)	return string("R")+char(id%10+'0');
	else	return string("B")+char(id%10+'0');
}
string tmp;
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> tmp;
			int id=toid(tmp);
			if(id>=0){
				pos[id]=make_pair(i,j);
			} else if(id==-21){
				gtype[i][j]=1;
			} else if(id==-11){
				gtype[i][j]=2;
			}
			if(0<=id && id<20){
				alive.push_back(id);
			}
		}
	}
	sort(alive.begin(),alive.end(),[](int x,int y){return tostr(x)<tostr(y);});
	cin >> T;
	for(int t=0;t<T;t++){
		cin >> tmp;
		char op;
		cin >> op;
		int id=toid(tmp),id2=-1;
		if(op=='U'){
			pos[id].first--;
		} else if(op=='D'){
			pos[id].first++;
		} else if(op=='L'){
			pos[id].second--;
		} else if(op=='R'){
			pos[id].second++;
		} else if(op=='T'){
			catching=-1;
		} else if(op=='C'){
			cin >> tmp;
			id2=toid(tmp);
			if(id2==21){
				catching=id;
			}
		}
		if(catching!=-1){
			pos[21]=pos[catching];
		} else{
			int gt=gtype[pos[21].first][pos[21].second];
//			cout << "[debug] Quaffle pos=(" << pos[21].first << ", " << pos[21].second << ").\n";
			if(gt==1){
				cout << t << " BLUE GOAL\n";
				++scoreb;
			} else if(gt==2){
				cout << t << " RED GOAL\n";
				++scorer;
			}
			pos[21]=make_pair((n+1)/2,(m+1)/2);
		}
		nxt.clear();
		elim.clear();
		for(auto &i:alive){
			if(pos[i]==pos[22]){
				elim.push_back(i);
				if(catching==i){
					catching=-1;
				}
				continue;
			}
			nxt.push_back(i);
		}
		swap(nxt,alive);
		for(auto &i:elim){
			cout << t << ' ' << tostr(i) << " ELIMINATED\n";
		}
		int cgs=0;
		if(op=='C' && id2==23){
			if(id<10){
				cgs=1;
			} else{
				cgs=2;
			}
		}
		if(cgs==1){
			cout << t << " RED CATCH GOLDEN SNITCH\n";
			scorer+=10;
			goto ed;
		} else if(cgs==2){
			cout << t << " BLUE CATCH GOLDEN SNITCH\n";
			scoreb+=10;
			goto ed;
		}
		
//		cout << "[debug]at t=" << t << ", now catching=" << tostr(catching) << ", pos R0=(" << pos[0].first << ", " << pos[0].second << "), pos B0=(" << pos[10].first << ", " << pos[10].second << ").\n";
//		cout << "[debug]pos Bludger=(" << pos[22].first << ", " << pos[22].second << ").\n";
	}
	ed:;
	cout << "FINAL SCORE: " << scorer << ' ' << scoreb;
	return 0;
}

tips

注意检查输出格式，例如时刻是从 $0$ 开始的，输出的单词建议复制原文。
球在球门内时还要被队员投掷出去才能算进球。
关于按字典序输出被淘汰的队员，可以一开始按字典序排序还活着的队员。遍历时另开一个数组记录更新后还活着的队员。
给单位一个 $id$ 会更好处理事件。

题解：CF1970F3 Playing Quidditch (Hard)

文章操作

题意简述

题解

tips

相关推荐

评论

题解：CF1970F3 Playing Quidditch (Hard)