[TOC]
题目
有n堆石头，第i堆有ai石头。 两人轮流出手。 Tokitsukaze首先移动。玩家在每个回合中选择一个非空堆，并从堆中取出恰好一块石头。 如果某玩家在移动前所有堆都是空的，或者在移走石头后，两个堆（可能是空的）包含相同数量的筹码，则此玩家将输。 假设双方都完全理性，谁将赢得比赛？
题解
引子
此题乍看不好模拟,实际上可以转化为如下问题:
有一个一维棋盘,上面坐落一些棋子,第i个棋子下标为ai,然后棋盘最左端的位置是0.两个人轮流出手,每次只能移动一个棋子将其向左移动一格,然后所有棋子不能重叠.当无法移动或者移动后棋子发生重叠者输.
分析:这个比较方便在头脑中模拟,我们发现由于棋子不能翻越其他棋子,所以棋子之前的先后顺序不会发生改变,也就是说最后的终态是确定的,棋子会从0依次往后排列.
当然还要考虑到最开始就发生棋子重叠的情况.
- 0号上有至少两个棋子
- 某一个位置上有至少三个棋子
- 某一个位置上至少有两个棋子且其左侧的位置至少有一个棋子
这三种情况下先手必败.
然后由于每个棋子的终点在开局就确定了,所以总共能够移动的步数也是确定的.因此只需要将所有步数加起来判断奇偶性即可,奇数先手赢,偶数后手赢.
回到正题
回到这个题,我们发现这两个题其实没有区别,只是要发现,堆的大小关系也是最开始就定好的,可以反证一下:如果存在初始时ai>aj,结束时ai<aj则中途一定有一瞬间是ai==aj,这是谁都不会走的一步.所以大小关系就确定了,每个堆的终点也确定了.进而确定了最终的步数,也确定了胜负.(别忘了上面那个问题的特判).
但是这个题还有一个坑就是ai 范围,所以一定要加的时候就对2取模,否则会溢出
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
int a[100000 + 10];
unordered_map<int, int> mp;
int main() {
int n;
ios::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
++mp[a[i]];
}
if (mp[0] > 1) {
cout << "cslnb" << endl;
return 0;
}
for (auto iter = mp.begin(); iter != mp.end(); ++iter) {
if ((*iter).second >= 3 ||
((*iter).second > 1 && mp[(*iter).first - 1] > 0)) {
cout << "cslnb" << endl;
return 0;
}
}
int tow_cnt = 0;
for (auto iter : mp) {
if (iter.second >= 2) {
++tow_cnt;
}
if (tow_cnt >= 2) {
cout << "cslnb" << endl;
return 0;
}
}
sort(a, a + n);
int res = 0;
for (int i = 0; i < n; ++i) {
res += (a[i] - i) % 2;
}
if (res % 2 == 0) {
cout << "cslnb" << endl;
} else {
cout << "sjfnb" << endl;
}
return 0;
}
