概述
一道博弈论的题目。
特意记录一下是因为，在尝试完成这道题的过程中，使用了之前学习的一些$unordered \ map$的卡常操作。
之前没有记录下来，现在补上。
题目
思路历程
首先，考虑到这场游戏只和奇数和偶数的个数相关，即可以设计状态：
但是，$n$最大可以达到$10^6$，极端情况下数组大小是$10^6*10^6$的规模，没有办法存储，且存在非常大的空间浪费。
于是，考虑使用$map$，利用map<pair<int, int>, int>来表示当前局面的胜负状态，$pair$用于存储奇数和偶数的个数。
再往后，判断转移状态：
可以发现，胜负态的转移跟这五种方式密切相关。
也就是说，假设当前状态为$sta(odd \ num,even \ num)$，只需要：
- $sta(odd \ num,even \ num-1)$为先手必败态（$even \ num \geq 2$）
- $sta(odd \ num - 1,even \ num)$为先手必败态（$odd \ num \geq 1 \ and\ even \ num \geq 1$）
- $sta(odd \ num,even \ num-1)$为先手必败态（$odd \ num \geq 1 \ and \ even \ num \geq 1$）
- $sta(odd \ num-1,even \ num)$为先手必败态（$odd \ num \geq 2$）
- $sta(odd \ num-2,even \ num+1)$为先手必败态（$odd \ num \geq 2$）
满足以上任一条件即可。
然后考虑边界情况，可以列出如下：
1
2
3
4
5
6
|
mp[make_pair(1, 0)] = 1;
mp[make_pair(1, 1)] = 1;
mp[make_pair(2, 0)] = 1;
mp[make_pair(0, 1)] = 0;
mp[make_pair(0, 2)] = 0;
|
然后搭配上转移过程，得到完整代码：
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
| #include <bits/stdc++.h>
using namespace std;
int n, onum, vnum;
map<pair<int, int>, int> mp;
int main(void)
{
mp[make_pair(1, 0)] = 1;
mp[make_pair(1, 1)] = 1;
mp[make_pair(2, 0)] = 1;
mp[make_pair(0, 1)] = 0;
mp[make_pair(0, 2)] = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int tmp;
scanf("%d", &tmp);
(tmp & 1) ? onum++ : vnum++;
if(mp.count(make_pair(onum, vnum))) continue;
int flag = 0;
if(vnum >= 2)
flag |= !mp[make_pair(onum, vnum - 1)];
if(onum && vnum)
flag |= !mp[make_pair(onum - 1, vnum)],
flag |= !mp[make_pair(onum, vnum - 1)];
if(onum >= 2)
flag |= !mp[make_pair(onum - 1, vnum)],
flag |= !mp[make_pair(onum - 2, vnum + 1)];
mp[make_pair(onum, vnum)] = flag;
}
printf(mp[make_pair(onum, vnum)] ? "NiuNiu" : "NiuMei");
return 0;
}
|
这一份代码运行超时，只过了6%的测试数据，考虑使用$unordered \ map$：
由于$pair$没有自带的$Hash$函数，需要自己编写，可以编写如下：
1
2
3
4
5
6
7
8
9
10
| struct pair_hash{
template<class T1, class T2>
std::size_t operator() (const std::pair<T1, T2>& p) const
{
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ h2;
}
};
unordered_map<pair<int, int>, int, pair_hash> mp;
|
这样一份代码，能跑过50%的测试数据。
然后顺便尝试上次从某题学来的手写$unordered \ map$：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| struct FEIHASH{
std::vector<int> key[maxn], val[maxn];
int hash(int x){
return (((long long)x * (x + 1)) ^ x) % maxn;
}
void insert(int x){
int f = hash(x);
for(int i = 0; i < (int)key[f].size(); ++i)
if(key[f][i] == x){
++val[f][i];
return;
}
key[f].push_back(x), val[f].push_back(1);
}
int query(int x){
int f = hash(x);
for(int i = 0; i < (int)key[f].size(); ++i)
if(key[f][i] == x)
return val[f][i];
return 0;
}
}cnt;
|
然后还是炸了。
此时尝试了好几次卡常，但都无功而返，卡不进去。
然后突然发现一个问题，这一份代码的正确性好像不太对！
构造数据如下：
由于输入均为偶数，因此应输出$NiuMei$。
但是，由于$sta(0, 2)$为牛牛的必败态，因此，在转移之后变成了牛牛的必胜态，这样的算法即使时间复杂度合格但也不能通过该题。
（发现这个问题之后我才发现居然还能过一半测试点是什么鬼）
根本原因在于，牛牛与牛妹的胜利条件判定并不一样，因此，使用胜负态转移的方法，并不能很好完成该题，而且$1e6$的数据规模会把我卡到有一半测试点都跑不过去。
到这里，看一眼榜，诶至少过了一千多人，怎么会搞个转移方程出来呢…
考虑规律题，当$n=2$时，牛妹执行动作则必胜。
牛牛的情况见下方笔记：
由此，编写代码如下：
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
| #include <bits/stdc++.h>
const int N = 1e6 + 5;
using namespace std;
int n, onum, vnum;
int main(void)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int tmp;
scanf("%d", &tmp);
(tmp & 1) ? onum++ : vnum++;
}
int win = 0;
if(n == 1)
onum ? win = 1 : win = 0;
else
{
if(n & 1)
win = 0;
else
vnum >= 2 ? win = 0 : win = 1;
}
printf(win ? "NiuNiu" : "NiuMei");
return 0;
}
|
然后就通过了这道题。
这道题给我带来的启发感觉不只在于博弈状态的讨论上，还有奇怪的卡常技巧上…
$mark$一下，以后说不定还会用上 U•ェ•*U