题目链接:uva 10561 - Treblecross
题目大意:n个格子排成一排,其中一些格子有'X',两个游戏者轮流操作,在格子中放X,如果此时出现连续3个X,则获胜。给出先手是否可以取胜,取胜方案的第一步该怎么走。
解题思路:一个X可以导致左右两个的两个格子都不能再放X,因为如果出现XX.、.XX、X.X,那么下一个人肯定胜利。所以对于长度为n的格子序列,g(x)=maxg(x−3),g(x−4)...g(2)XORg(n−7).
所以可以预先处理出g数组,然后对于给定的序列,枚举先手下的位置,判断这种情况下,后手是否为必败态。注意如果先手一步即可胜利要特殊考虑。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200;
int g[maxn+5], v[maxn+5];
int SG (int s) {
memset(v, 0, sizeof(v));
for (int i = 1; i <= s; i++) {
int t = 0;
if (s - i - 2 >= 0)
t ^= g[s-i-2];
if (i - 3 >= 0)
t ^= g[i-3];
v[t] = 1;
}
int mv = -1;
while (v[++mv]);
return mv;
}
void init () {
memset(g, 0, sizeof(g));
g[1] = g[2] = g[3] = 1;
for (int i = 4; i <= 200; i++)
g[i] = SG(i);
}
int n, len, pos[maxn+5];
char str[maxn+5];
bool check () {
int pre = -3, ret = 0;
for (int i = 0; i <= len; i++) {
if (str[i] == 'X') {
if (i - pre <= 2)
return false;
int l = max(i - pre - 5, 0);
if (l)
ret ^= g[l];
pre = i;
}
}
int l = max(len - pre - 3, 0);
if (l)
ret ^= g[l];
return ret == 0;
}
bool judge () {
n = 0;
len = strlen(str);
for (int i = 0; i < len; i++) {
if (str[i] == '.') {
str[i] = 'X';
if (check())
pos[n++] = i + 1;
str[i] = '.';
}
if (i && i < len - 1 & str[i-1] == 'X' && str[i+1] == 'X')
pos[n++] = i + 1;
if (i < len - 2 && str[i+1] == 'X' && str[i+2] == 'X')
pos[n++] = i + 1;
if (i >= 2 && str[i-1] == 'X' && str[i-2] == 'X')
pos[n++] = i + 1;
}
return n;
}
int main () {
init();
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%s", str);
printf("%s\n", judge() ? "WINNING" : "LOSING");
if (n)
printf("%d", pos[0]);
for (int i = 1; i < n; i++)
printf(" %d", pos[i]);
printf("\n");
}
return 0;
}
分享到:
相关推荐
Atom-nim-planet.zip,Nim RSS feed planet at https://planet.nim-lang.org尼姆星球,atom是一个用web技术构建的开源文本编辑器。
hts-nim-tools:有用的命令行工具,用于展示hts-nim
msgpack-rpc-nim Nim 的 MessagePack-RPC 实现 API: : 例子作者Akira Hayakawa ( )
matlab开发-NIMgame。NIM游戏的图形用户界面实现
nim-osureplay:osu! 重播用Nim语言编写的解析器-@ nim-lang
nim-datauri:数据URI Base64 UTF-8 Nim模块
jsmn.nim:Jsmn-世界上最快的JSON解析器-纯Nim
repo-template-nim:Nim项目模板
pre-comm-nim:为Nim提交前的挂钩
IBM P系列虚拟化 1.规划和配置 2.划分VIO分区,安装配置VIO 3.划分其他Lpar,安装第一个LPAR 4.配置NIM,安装其他LPAR 5.附录
为 Nim 准备的 SQL 语句生成器。 一个轻量级的 ORM。 特征: 编译时查询检查:检查类型以及表名和列名,运行时没有任何意外! 自动连接生成:Ormin 知道表关系,可以为您计算“自然”连接! 用于查询的基于 Nim ...
The game of nim is played as follows. Some number of sticks are placed in a pile. Two players alternate in removing either one or two from the pile. The player who remove the last stick is the loser....
在Nim中编写NodeJS本机扩展 如果您不喜欢C代码的冗长且感到C ++太复杂,请尝试使用napi-nim来提高NodeJS应用程序的性能。 现在是NodeJS一部分的新n-api使您可以与支持C ABI的任何语言JavaScript代码进行交互。 是...
解题思路如果最后剩下1-3个石头,你肯定是赢家,如果此时剩下4个石头,你无论拿多少个,对方一定会赢。如果此时剩下5个石头,这时你的最佳策略是拿走一个石头,这是对
C Terminal Nim C Terminal Nim有一个不言而喻的名称:这是您可以在终端中玩的Nim游戏。 目前,只有本地两人游戏模式可用。 指示 正在下载 导航到发行页面,并下载适用于您系统的二进制文件(对于Linux是nim ,对于...
gulp-nim Gulp插件来编译文件。 安装 npm i -D gulp-nim 用法 gulpfile.js const { src , dest } = require ( 'gulp' ) const nim = require ( 'gulp-nim' ) exports . default = function ( ) { return src ( '....
gsl-nim nim的这是为nim包装的GNU GSL C Api(使用生成)。安装安装GNU GSL库的Ubuntu 须藤apt-get install libgsl-dev 苹果系统酿造安装gsl 视窗为什么要在Windows上执行此操作? 也许使用WSL。 从源代码构建从下载...
Game-of-Nim
To-ASCII-Nim 一个用于将图像转换为ASCII的命令行工具! 编译/构建 克隆存储库并cd到其中: git clone https://github.com/Iapetus-11/To-ASCII-Nim cd To-ASCII-Nim 编译: nimble install # or nim compile ...
用于Nim的圆锥形(凸锥)优化库。 优化引擎基于 ( )。 支持的圆锥类型 零锥(平等约束) LP(线性不等式约束) 二次锥 旋转二次锥 指数锥 动力锥 要求 BLAS BLAS接口有很多实现。 例如, 。 的Ubuntu sudo ...