[BZOJ 1874] [BeiJing2009 WinterCamp] 取石子游戏 【博弈论 | SG函数】
2024-10-04 09:41:21
题目链接:BZOJ - 1874
题目分析
这个是一种组合游戏,是许多单个SG游戏的和。
就是指,总的游戏由许多单个SG游戏组合而成,每个SG游戏(也就是每一堆石子)之间互不干扰,每次从所有的单个游戏中选一个进行决策,如果所有单个游戏都无法决策,游戏失败。
有一个结论,SG(A + B + C ... ) = SG(A)^SG(B)^SG(C) ...
这道题每堆石子不超过 1000 , 所以可以把 [0, 1000] 的 SG 值暴力求出来,使用最原始的 SG 函数的定义, SG(u) = mex(SG(v)) E(u -> v) 。
注意 m <= 10 所以一个状态 i 的后继状态不超过 10 个,那么它的 SG 值不会超过 10 。
然后将每一堆的 SG 值异或起来。如果必胜,就按照顺序枚举一下所有初始方案,找到必胜的就输出并退出。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; const int MaxNum = 1000 + 5, MaxN = 10 + 5; int n, m, Mark_Index;
int A[MaxN], B[MaxN], SG[MaxNum], Mark[MaxN]; void Calc_SG() {
SG[0] = 0;
Mark_Index = 0;
memset(Mark, 0, sizeof(Mark));
for (int i = 1; i <= 1000; ++i) {
++Mark_Index;
for (int j = 1; j <= m; ++j) {
if (B[j] > i) continue;
Mark[SG[i - B[j]]] = Mark_Index;
}
for (int j = 0; j <= 10; ++j) {
if (Mark[j] != Mark_Index) {
SG[i] = j;
break;
}
}
}
} int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
scanf("%d", &m);
for (int i = 1; i <= m; ++i) scanf("%d", &B[i]);
Calc_SG();
int Temp = 0;
for (int i = 1; i <= n; ++i) Temp ^= SG[A[i]];
if (Temp == 0) printf("NO\n");
else {
printf("YES\n");
bool Flag = false;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (B[j] > A[i]) continue;
if ((Temp ^ SG[A[i]] ^ SG[A[i] - B[j]]) == 0) {
Flag = true;
printf("%d %d\n", i, B[j]);
break;
}
}
if (Flag) break;
}
}
return 0;
}
最新文章
- Android 控件属性介绍
- Android高性能ORM数据库DBFlow入门
- SQL Server DBA日常查询视图_数据库对象视图
- C++函数模版
- 苹果原生NSURLSession的上传和下载
- LightOj_1027 A Dangerous Maze
- c++ namespace命名空间详解
- PHP获取客户端和服务器端IP(转)
- Luogu5289 十二省联考2019皮配(动态规划)
- Hadoop Mapreduce 调优
- weblogic报错----Received exception while creating connection for pool ";TDMSKD";: The Network Adapter could not establish the connection
- 【原创】数据库基础之Mysql(3)mysql删除历史binlog
- Effective Java 第三版——65. 接口优于反射
- 认识正则RegExp;
- doT.js模板和pagination分页应用
- 使用JS获取当前地理位置方法汇总
- 牛客红包OI赛 C 小可爱表白
- Python 练习题:计算 MAC 地址
- javascript实现八大排序
- Docker 安装Hadoop集群
热门文章
- 为Android GridView 设置行背景
- Eclipse的修改编码插件使用
- Java基础知识强化之集合框架笔记33:Arrays工具类中asList()方法的使用
- css考核点整理(十一)-响应式开发经验,响应式页面的三种核心技术是什么
- inverse 相关设置
- TFS 服务器更换后工作区无法绑定
- c# try..... catch
- Android开发常见错误类型一览表
- 多线程lock(instance)中instance的选择.
- oracle官方文档- length篇