Codeforces Round #712 3-Coloring 博弈+模拟

题意

这道题是交互式的题目。意味着你的输出会影响他的输入,需要在读取了输入之后完成相应的输出之后才会有下一个输入。

给你一个${n}\times{n}$的格子。现在呢两个人玩游戏。每次可以给一个格子涂三种颜色中的一个。

游戏规则是这样的,对于每一轮操作:Alice选择一个颜色,ban掉。接着Bob开始选一个格子涂颜色。要求Bob涂的格子不能是Alice刚刚ban掉的颜色,且这个颜色不能和相邻格子重复。

如果Bob不能找到格子涂的话,则Bob失败。如果Bob最终涂满了整个地图则Bob胜了。

已知,这个游戏Bob必胜。现在你是Bob,然后你和Alice玩,要求根据Alice的输入输出你的应对,并最终获胜。


思路

盯着两个颜色涂。直到其中一个颜色涂满所在的半边地图。之后剩下的半边可以根据输入任意填剩下两种颜色中的一个。

也就是说,一开始根据输入,随便给map[0][0]和map[0][1]填两个颜色。然后,之后Alice的输入最多只能占到两个颜色中的一个。那么对于剩下的一个我们向他四个角扩展。久而久之,必然有其中一个颜色交叉占满了一半的格子。比如下面这个样子:

一个颜色交叉涂满了一半

那剩下格子没涂的格子就Alice给什么,我不涂什么就好。

不知道有没有别的什么做法,这个做法写着稍微有点烦就是了。


代码

WA了一发……Java语法原因,LinkedList如果是空的话,调用removeFirst会抛异常而不是返回null……

Submission #112017962 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论