- 两个玩家
- 一个状态集合
- 游戏规则是指明玩家从一个状态可以移动到哪些状态
- 玩家轮流进行移动
- 如果当前处于的状态无法移动，则说明游戏结束
- (大部分时候)无论玩家如何选择，游戏会在有限步操作内结束
只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个.最后取光者得胜
枚举m，进行倒推打表
比如:
m = 1
0(P) <—— 1(N) <—— 2(P) <—— 3(N) .....
m = 2
0(P) <—— 1(N) <—— 2(N) <—— 3(P) .....
m = 3
0(P) <—— 1(N) <—— 2(N) <—— 3(N) <—— 4(P).....
然后我们可以初步的确定结论为
if(num % (m + 1) == 0) num 为 P 态
else num 为 N 态
最后可以去确定n的状态，判断先手是赢还是输
#include<iostream>
#include<algorithm>
using namespace std;
int t;
void solve()
{
int n,k;
cin >> n >> k;
if(n % (k + 1)) puts("A");
else puts("B");
}
int main()
{
cin >> t;
while(t --) solve();
return 0;
}
#include<iostream>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int,bool> mp;
vector<int> device;
void get(int x)
{
for(int i = 2; i * i <= x; i ++)
if(x % i == 0)
{
device.push_back(i);
device.push_back(x / i);
}
}
int main()
{
for(int i = 0; i <= 200; i++)
{
device.clear();
get(i);
if(device.empty()) mp[i] = 1;
else
{
bool flag = true;
for(int d : device)
if(mp[i - d])
{
flag = false;
break;
}
mp[i] = flag;
}
}
fstream fstrm("output.txt");
for(int i = 1; i <= 200; i++) fstrm << i << ' ' << (mp[i]? 'P':'N') << endl;
fstrm.close();
return 0;
}
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t;
void solve()
{
int n;
cin >> n;
if(n % 2) puts("Bob");
else
{
int cnt = 0,pos = -1;
for(int i = 0; i < 32; i++)
if(n >> i & 1)
{
cnt ++;
if(cnt == 1) pos = i;
}
//cout << cnt << ' ' << pos << endl;
if(cnt == 1 && pos & 1) puts("Bob");
else puts("Alice");
}
}
int main()
{
cin >> t;
while(t--) solve();
return 0;
}
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
unordered_map<string,bool> mp;
string s;
int n;
bool dfs(string x)
{
// cout << x << endl;
if(mp.count(x)) return mp[x];
bool flag = true;
for(int i = 0; i < x.size(); i++)
{
int y = x[i] - '0';
if(!y)
{
if(dfs(x.substr(0,i))) flag = false;
}
else
{
for(int j = 0; j < y; j++)
{
string z = x.substr(0,i);
z += '0' + j;
z += x.substr(i + 1);
if(dfs(z)) flag = false;
}
}
}
return mp[x] = flag;
}
void solve()
{
cin >> s;
mp[""] = 1;
dfs(s);
if(mp[s]) puts("No");
else puts("Yes");
}
int main()
{
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
string s;
bool sg[N];
int pow[8];
int n,t;
int getlen(int x)
{
int res = 0;
while(x)
{
res ++;
x /= 10;
}
return res;
}
int get_num()
{
int res = 0;
for(int i = 0; i < s.size(); i++)
res = res * 10 + (s[i] - '0');
return res;
}
void get_sg(int x)
{
int l = getlen(x);
for(int i = 0; i < l; i++)
{
int y = x;
int tem = x / pow[i] % 10;
for(int j = tem; j < 9; j++)
{
y += pow[i];
sg[y] = 1;
}
}
for(int i = 1; i + l <= 6; i++)
{
int y = x * pow[i];
for(int j = 0; j < pow[i - 1]; j++)
{
sg[y + j] = 1;
// cout << y + j << ' ' << sg[y + j] << endl;
}
}
}
void init()
{
sg[0] = 1;
pow[0] = 1;
for(int i = 1; i < 8; i++) pow[i] = pow[i - 1] * 10;
for(int i = 1; i < 1000000; i++)
if(!sg[i]) get_sg(i);
}
void solve()
{
cin >> s;
if(s[0] == '0') puts("Yes");
else
{
int x = get_num();
// cout << x << endl;
if(sg[x]) puts("Yes");
else puts("No");
}
}
int main()
{
cin >> t;
init();
while(t--) solve();
return 0;
}
啊，其实这题和上一题得解题思路是一样的，不过又要比上一题麻烦很多
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 21000000;
bool sg[N];
int a[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int y,m,d;
int t;
int get_year(int x)
{
return x / 10000;
}
int get_mon(int x)
{
return x % 10000 /100;
}
int get_day(int x)
{
return x % 100;
}
int get_num(int year,int mon,int day)
{
return year * 10000 + mon * 100 + day;
}
bool check(int x)
{
int year = get_year(x);
int mon = get_mon(x);
int day = get_day(x);
if(!day || !mon) return false;
if(mon > 12) return false;
if(year % 400 == 0 || (year % 100 == 0 && year % 4))
{
if(mon == 2 && day > 29) return false;
else if(day > a[mon]) return false;
}
else if(day > a[mon]) return false;
return true;
}
void get_sg(int x)
{
int year = get_year(x);
int mon = get_mon(x);
int day = get_day(x);
if(mon == 1)
{
int b = get_num(year - 1,12,day);
if(check(b)) sg[b] = true;
}
else
{
int b = get_num(year,mon - 1,day);
if(check(b)) sg[b] = true;
}
if(day == 1)
{
int b;
if(mon == 1) b = get_num(year - 1,12,31);
else b = get_num(year,mon - 1,a[mon - 1]);
if(check(b)) sg[b] = true;
}
else
{
int b = get_num(year,mon,day - 1);
if(check(b)) sg[b] = true;
}
}
void init()
{
sg[20011104] = 0;
sg[20011004] = 1;
sg[20011103] = 1;
for(int i = 20011102; i >= 19000101; i--)
if(!sg[i] && check(i)) get_sg(i);
}
void solve()
{
cin >> y >> m >> d;
int x = get_num(y,m,d);
if(sg[x]) puts("YES");
else puts("NO");
}
int main()
{
init();
cin >> t;
while(t --) solve();
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int res=0;
while(n--)
{
int a;
cin>>a;
res^=a;
}
if(res) puts("Yes");
else puts("No");
return 0;
}
我们就在题目给出的图上做分析：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int main()
{
cin >> n >> m;
int res = 0;
while(n --)
{
int l,r;
cin >> l >> r;
res ^= abs(r - l) - 1;
}
if(res) puts("I WIN!");
else puts("BAD LUCK!");
return 0;
}
简单的nim游戏，但是呢这题说，先手要从第k堆石子里那；
根据nim游戏结论的证明过程可知:
如果，res = a1 ^ a2 ^ …^ ak ^ … ^an == 0,那不管先手从哪一堆先拿，结果都是输
如果不为零的话，从ak中先拿，就必须使得剩下 ak’ 让 a1 ^ a2 ^ …^ ak’ ^ … ^an == 0 即 ak’ = ak ^ res < ak
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n,k,t;
void solve()
{
cin >> n >> k;
int res = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
res ^= a[i];
}
if(res == 0) puts("No");
else
{
res ^= a[k];
if(res < a[k]) puts("Yes");
else puts("No");
}
}
int main()
{
cin >> t;
while(t--) solve();
return 0;
}
思路上的话，我觉得博客园有篇文章写得挺好的，我就直接放链接了
就是说nim游戏是一堆石子不能增加的游戏，要不断地从其中的一堆石子中取走一些石子，然后台阶nim游戏就是说，把奇数层的阶梯维护成一个nim游戏，根据nim游戏的规则，当奇数层的异或和不为0的时候，先手胜，因为如果后手将偶数层的石子移动到奇数层，先手可以将该奇数层被移过来的石子，又移到下一层偶数层，此时奇数层的状态不受影响，后手想改变状态的话，就要将奇数层的石子移到偶数层，那这时异或和由0变为正整数，先手始终能从奇数层上一部分石子，使得异或和又变成零。如果一开始奇数层的异或和为0的话，同理，但会是后手胜
为什么这样是对的呢?
首先如果移动的是同一对棋子中的左边棋子,那下一个玩家可以以同样的步数移动右边棋子,此时对游戏结果不会造成任何影响
如果移动的是右边棋子,就相当于减少了石子的个数
这样就将问题转化成nim游戏了
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> a;
int t,n;
void solve()
{
cin >> n;
a.clear();
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
a.push_back(x);
}
if(n % 2) a.push_back(0);
sort(a.begin(),a.end());
int res = 0;
for(int i = 0; i < a.size() - 1; i+=2) res ^= a[i + 1] - a[i] - 1;
if(res) puts("Georgia will win");
else puts("Bob will win");
}
int main()
{
cin >> t;
while(t--) solve();
return 0;
}
为什么这样是对的呢?
首先如果移动的是同一对棋子中的左边棋子,那下一个玩家可以以同样的步数移动右边棋子,此时对游戏结果不会造成任何影响
如果移动的是右边棋子,就相当于减少了石子的个数
这样就将问题转化成nim游戏了
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> a;
int t,n;
void solve()
{
cin >> n;
a.clear();
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
a.push_back(x);
}
if(n % 2) a.push_back(0);
sort(a.begin(),a.end());
int res = 0;
for(int i = 0; i < a.size() - 1; i+=2) res ^= a[i + 1] - a[i] - 1;
if(res) puts("Georgia will win");
else puts("Bob will win");
}
int main()
{
cin >> t;
while(t--) solve();
return 0;
}
