题目重点：用小规模Minimax区分自己最大收益与合作挑最大，明确先手和配对规则。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 可辨规则是A/B交替选piece，选某配对端点会强制下一步选另一端点，各自最大化本区域总affinity。未给先手、规模和pair能否重叠；练习限定偶数N≤16、pairs互不共享端点、全部piece分完。
- 支持start_a=True/False分别求A收益；参数pair为零基，输入一基要先转换。负affinity合法，不能只选正数或把最优初值设0。
解题路线
- 状态(mask,forced)表示已取集合和下一步是否必须取partner；回合由已取数量奇偶及先手决定。自由步选任一剩piece；配对端点设置下一步forced，该强制步结束后恢复自由。
- A回合在候选的“当前给A收益+未来A收益”取max，B回合取min，因为所有piece总和固定，最大B收益等于最小A收益。这不是两方都协作最大A，也不能只看当前最大值。
- memo避免重复状态。终局A剩余收益0，负值正常参与max/min；强制选择没有其他候选，不为对方凭空提供拒绝或跳过。
- 公开例pairs转零基为(1,3)/(2,5)，选8强制对方拿2，选择−4可能迫使对方拿−7；每个局部选择影响后续轮次与自由piece。用完整序列树反向求值作独立对照。
- 这个指数解法用于验证小合同和探索规律；大N需进一步证明贪心/结构性质。pair重叠会让一次选择强制多个“下一步”，合同矛盾需先澄清，不能 silently选一个partner。
- 互斥pair下可证明快解：每次处理pair消耗两步，随后仍是同一方自由选择，因此不改变unpaired轮次。先手可在第一次取独立piece前处理全部pairs，每pair先取较大值，达到本方所有pair收益上界；后手被强制拿较小值。任何提前放弃pair控制权都不能增加先手的pair部分上界。
- 独立piece只剩双方同偏好的交替选择，排序从大到小轮流拿。归纳剩余局的排序交替和，可证明跳过当前最大值的候选收益差只由若干非负相邻差组成，选最大不劣；负值也满足排序差非负。先手A加各pair最大与free偶数位，先手B时A加pair最小与free奇数位。
- greedy_region_a实现上述同一合同的大规模快解；exact模型保留作校验，600个完整排列prefix-tree案例同时核exact和greedy。若规则允许pair重叠、某些piece不取或收益非零和，证明条件改变，不能沿用。
手动走一遍
affinity[3,2,−4,8,3,−7]，互斥pairs[(2,4),(3,6)]按一基解释：在练习合同A先手最优A总和7，B先手A总和−2。先手会改变答案，不能在缺先手题面下把7说成唯一原题结果。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from functools import lru_cache
def optimal_region_a(affinity,pairs,start_a=True):
"""Small exact training game: disjoint pairs, all pieces taken, selfish turns.
Selecting one endpoint forces partner on immediately following opponent turn.
"""
n=len(affinity)
if n%2 or n>16:raise ValueError('even n <= 16 exact solver')
partner={}
for a,b in pairs:
if not (0<=a<n and 0<=b<n) or a==b or a in partner or b in partner:raise ValueError('disjoint valid pairs')
partner[a]=b;partner[b]=a
full=(1<<n)-1
@lru_cache(None)
def solve(mask,forced):
if mask==full:return 0
is_a=start_a if mask.bit_count()%2==0 else not start_a
choices=[forced] if forced>=0 else [i for i in range(n) if not mask>>i&1]
outcomes=[]
for i in choices:
next_forced=-1 if forced>=0 else partner.get(i,-1)
value=(affinity[i] if is_a else 0)+solve(mask|(1<<i),next_forced)
outcomes.append(value)
return max(outcomes) if is_a else min(outcomes)
return solve(0,-1)
def greedy_region_a(affinity,pairs,start_a=True):
"""Same disjoint-pair complete-all game, scalable solution."""
n=len(affinity)
if n%2:raise ValueError('even n')
used=set();total=0
for a,b in pairs:
if not (0<=a<n and 0<=b<n) or a==b or a in used or b in used:raise ValueError('disjoint valid pairs')
used.update((a,b))
total+=(max if start_a else min)(affinity[a],affinity[b])
free=sorted((value for i,value in enumerate(affinity) if i not in used),reverse=True)
total+=sum(free[0 if start_a else 1::2])
return total
复杂度
保守状态上界O(N·2^N)，每状态至多N候选，时间O(N²·2^N)、memo空间O(N·2^N)，递归深度N。示例限制N≤16避免把指数模型当可扩至大输入；具体可达状态常少于上界。 在相同互斥pair、全部取完和交替合同下，快解扫描pair O(M)、排序独立piece O(F log F)，空间O(N)；不限N16，16只是exact函数保护。
易错点与追问
容易失分的边界
- B也取max A收益，把对抗变合作。
- 只按当前最大affinity贪心，未证明forced后果。
- 重叠pair悄悄覆盖partner字典。
继续深挖
- 如果双方合作最大A而非各自最大收益，为什么不是当前交替greedy？
- pair重叠会让下一步强制要求矛盾，应补充哪项规则？
