当前位置:网站首页>博弈论 AcWing 894. 拆分-Nim游戏
博弈论 AcWing 894. 拆分-Nim游戏
2022-07-05 06:16:00 【T_Y_F666】
博弈论 AcWing 894. 拆分-Nim游戏
原题链接
算法标签
数学知识 博弈论 SG函数
思路
代码
#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105, M = 10005;
int f[M];
int n;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
int sg(int x){
if(f[x]!=-1){
return f[x];
}else{
unordered_set<int> S;
// 第一堆数量要求
rep(i, 0, x){
// 第二堆数量要求
rep(j, 0, i+1){
S.insert(sg(i)^sg(j));
}
}
// mex 函数
for(int i=0;;++i){
if(!S.count(i)){
return f[x]=i;
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(f, -1, sizeof f);
n=read();
int ans=0;
while(n--){
int x=read();
ans^=sg(x);
}
if(ans){
puts("Yes");
}else{
puts("No");
}
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- leetcode-9:回文数
- Chapter 6 relational database theory
- RGB LED infinite mirror controlled by Arduino
- 【Rust 笔记】14-集合(上)
- [rust notes] 17 concurrent (Part 2)
- 高斯消元 AcWing 884. 高斯消元解异或线性方程组
- Usage scenarios of golang context
- A reason that is easy to be ignored when the printer is offline
- Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
- NotImplementedError: Cannot convert a symbolic Tensor (yolo_boxes_0/meshgrid/Size_1:0) to a numpy ar
猜你喜欢
Quickly use Amazon memorydb and build your own redis memory database
MySQL advanced part 1: index
RGB LED infinite mirror controlled by Arduino
Redis publish subscribe command line implementation
Navicat连接Oracle数据库报错ORA-28547或ORA-03135
MySQL怎么运行的系列(八)14张图说明白MySQL事务原子性和undo日志原理
Data visualization chart summary (II)
Simple selection sort of selection sort
1.15 - input and output system
LeetCode 0107.二叉树的层序遍历II - 另一种方法
随机推荐
数据可视化图表总结(一)
Overview of variable resistors - structure, operation and different applications
1.14 - assembly line
A reason that is easy to be ignored when the printer is offline
NotImplementedError: Cannot convert a symbolic Tensor (yolo_boxes_0/meshgrid/Size_1:0) to a numpy ar
leetcode-6109:知道秘密的人数
11-gorm-v2-03-basic query
MIT-6874-Deep Learning in the Life Sciences Week 7
Shutter web hardware keyboard monitoring
【Rust 笔记】16-输入与输出(下)
[leetcode] day95 effective Sudoku & matrix zeroing
Leetcode-6110: number of incremental paths in the grid graph
redis发布订阅命令行实现
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
QQ电脑版取消转义符输入表情
884. Uncommon words in two sentences
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
高斯消元 AcWing 884. 高斯消元解异或线性方程组
Leetcode divide and conquer / dichotomy
Traversal of leetcode tree