1 条题解

  • 0
    @ 2026-5-6 16:36:26

    题意

    有一些单、双面有数字的牌。两人轮流取数字最小的牌,可以移除也可以将没翻过的双面牌翻一次,最后没牌的人输。

    分析

    首先拿到最后一张双面牌的人会赢,因为他可以决定剩下来的牌数量的奇偶。

    什么牌会决定最后一张双面牌的归属?一定是正反面都比它小的牌中正面最大的,拿到的人可以决定给不给对方机会拿到最后一张牌的机会(因为可以控制中间牌数的奇偶),那么问题就是谁能拿到这样的牌,把这张牌看成最后一张双面牌,不停向前找到第一张必胜牌。这样的牌一定存在。

    正面比第一张必胜牌小的牌就是两人轮流拿最小的牌(对于正面比第一张必胜牌小双面牌来说翻不翻都一样,因为它的反面比必胜牌正面大,会挪到后面,而后面的奇偶性不重要)。谁先拿到第一张必胜牌就赢了。

    实现

    #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
    上传者