概述
一道博弈论的题目。
特意记录一下是因为,在尝试完成这道题的过程中,使用了之前学习的一些$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