1 条题解
-
0
题意
有一些单、双面有数字的牌。两人轮流取数字最小的牌,可以移除也可以将没翻过的双面牌翻一次,最后没牌的人输。
分析
首先拿到最后一张双面牌的人会赢,因为他可以决定剩下来的牌数量的奇偶。
什么牌会决定最后一张双面牌的归属?一定是正反面都比它小的牌中正面最大的,拿到的人可以决定给不给对方机会拿到最后一张牌的机会(因为可以控制中间牌数的奇偶),那么问题就是谁能拿到这样的牌,把这张牌看成最后一张双面牌,不停向前找到第一张必胜牌。这样的牌一定存在。
正面比第一张必胜牌小的牌就是两人轮流拿最小的牌(对于正面比第一张必胜牌小双面牌来说翻不翻都一样,因为它的反面比必胜牌正面大,会挪到后面,而后面的奇偶性不重要)。谁先拿到第一张必胜牌就赢了。
实现
#include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; pair<int,int> a[N]; int b[N]; int main() { int n,m; cin>>n>>m; for(int i = 1; i <= n; i ++) cin>>a[i].first; for(int i = 1; i <= n; i ++) cin>>a[i].second; for(int i = 1; i <= m; i ++) cin>>b[i]; sort(a + 1,a + n + 1); int p = 0,cnt = 0; for(int i = n; i >= 1; i --) if(!p || a[i].second < a[p].first) p = i; for(int i = 1; i <= m; i ++) cnt += b[i] < a[p].first; if((p + cnt) & 1) cout<<"First\n"; else cout<<"Second\n"; return 0; }
- 1
信息
- ID
- 10203
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者