Card Flip 详细题解（对标标程 + 博弈论核心）

这是一道 贪心排序 + 博弈论（Nim 游戏 / 奇偶性判断） 的经典题，数据范围 $n,m \le 5\times10^5$，要求 $O(n\log n + m)$ 算法。

一、题目翻译与规则解析

题意

有 $n$ 张双面牌和 $m$ 张单面牌：

1. 双面牌：正面数字 $a_i$，背面数字 $b_i$；
2. 单面牌：只有正面数字 $c_i$； 所有数字互不重复，且恰好覆盖 $1 \sim 2n+m$。

初始所有牌正面朝上，两人轮流操作（Petya 先手），每回合必须执行恰好一种操作：

1. 移除当前桌上最小数字的牌；
2. 翻转：若当前最小数字的牌是双面牌且正面朝上，可以翻转它（翻面后显示 $b_i$）。

拿走最后一张牌的人获胜，判断谁必胜。

---

二、核心博弈结论（破题关键）

1. 关键观察

• 所有数字严格唯一，全局最小值一定是当前必须处理的牌；
• 单面牌无法翻转，只能被移除；
• 双面牌只有是当前最小值且正面朝上时，才能选择翻转；
• 翻转的本质：把一个小数字替换成一个大数字，推迟它被移除的时间。

2. 终极结论（对标标程）

1. 把双面牌按正面数字 $a_i$ 升序排序；
2. 找到最左侧的关键位置 $lst$：满足 $d[lst].b$ 大于所有右侧双面牌的 $a$（即从 $lst$ 开始，右侧所有双面牌都无法翻转，只能按顺序移除）；
3. 统计单面牌中比 $d[lst].a$ 小的数量 $ans$；
4. 最终判断：
   • 若 $(ans + lst) \% 2 = 1$ → 先手（First）胜；
   • 否则 → 后手（Second）胜。

---

三、标程逻辑逐行拆解

1. 数据结构与输入

struct db{ ll a,b; } d[500010];  // 存储双面牌：a正面，b背面
ll n,m,c[500010];               // c：单面牌
ll lst,ans;

• 存储所有双面牌的 $a_i$（正面）、$b_i$（背面）；
• 存储单面牌 $c_i$。

2. 排序（核心第一步）

sort(d+1,d+n+1,comp);  // 按双面牌正面数字 a_i 升序排序

✅ 必须按正面数字从小到大排序，因为游戏始终处理当前最小值。

3. 找关键位置 $lst$

lst=n;
for(int i=n-1;i>=1;i--)
    if(d[i].b < d[lst].a) lst=i;

• 从右往左遍历，维护最右侧合法位置 $lst$；
• 规则：$d[i].b < d[lst].a$ 时，更新 $lst=i$；
• 含义：$lst$ 左边的牌可以翻转，$lst$ 及右边的牌无法翻转，只能按顺序移除。

4. 统计小单面牌数量

for(int i=1;i<=m;i++)
    if(c[i] < d[lst].a) ans++;

统计比 $d[lst].a$ 小的单面牌数量，这些牌会被优先移除。

5. 胜负判断

if((ans+lst)%2) cout<<"First"<<endl;
else cout<<"Second"<<endl;

• 总可确定步数 = 小单面牌数 $ans$ + 关键位置 $lst$；
• 奇数 → 先手胜，偶数 → 后手胜。

---

四、样例演算（第一个样例）

输入： $n=2,\ m=1$ 双面正面：$5,3$ 双面背面：$1,2$ 单面：$4$

步骤1：排序双面牌（按 $a_i$ 升序）

原双面：$(5,1)$、$(3,2)$ 排序后：$\boldsymbol{(3,2)}$、$\boldsymbol{(5,1)}$

步骤2：找 $lst$

• $lst=2$；
• $i=1$：$d[1].b=2 < d[2].a=5$ → $lst=1$。

步骤3：统计 $ans$

$d[lst].a=3$，单面牌 $4>3$ → $ans=0$。

步骤4：判断

$(0+1)\%2=1$ → First 胜，与样例一致。

---

五、算法复杂度

• 排序双面牌：$O(n\log n)$
• 找 $lst$：$O(n)$
• 统计单面牌：$O(m)$ 总复杂度：$\boldsymbol{O(n\log n + m)}$，完美通过 $5\times10^5$ 数据。

---

六、标程完整注释版

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

// 双面牌：a正面，b背面
struct db{
	ll a,b;
} d[500010];

ll n,m,c[500010];  // c：单面牌
ll lst,ans;        // lst：关键位置，ans：小单面牌数量

// 按正面数字升序排序
bool comp(db a,db b){
	return a.a < b.a;
}

int main(){
	cin>>n>>m;
	// 输入双面牌正面
	for(int i=1;i<=n;i++) cin>>d[i].a;
	// 输入双面牌背面
	for(int i=1;i<=n;i++) cin>>d[i].b;
	// 输入单面牌
	for(int i=1;i<=m;i++) cin>>c[i];

	// 按正面数字排序
	sort(d+1,d+n+1,comp);

	// 找关键位置 lst
	lst = n;
	for(int i=n-1;i>=1;i--)
		if(d[i].b < d[lst].a) lst = i;

	// 统计比 d[lst].a 小的单面牌数量
	ans = 0;
	for(int i=1;i<=m;i++)
		if(c[i] < d[lst].a) ans++;

	// 奇偶性判断胜负
	if((ans + lst) % 2 == 1)
		cout<<"First"<<endl;
	else
		cout<<"Second"<<endl;

	return 0;
}

---

总结

1. 核心思想：排序双面牌 → 找关键不可翻转位置 $lst$ → 统计小单面牌；
2. 胜负规则：$(ans+lst)$ 奇数先手胜，偶数后手胜；
3. 复杂度：$O(n\log n + m)$，通过全部测试点。