翻译有锅
查看原帖
翻译有锅
530180
KingPowers楼主2023/11/4 19:10

如题,出现了一些莫名其妙的问号

单卡和双卡在玩纸牌游戏。每张牌都有两个参数:攻击值和防御值。$s$ 能打败 $t$ 当且仅当 $s$ 的攻击值严格大于 $t$ 的防御值。

Monocarp 有 $n$ 张牌,其中第 $i$ 张的攻击值为 $\mathit{ax}_i$,防御值为 $\mathit{ay}_i$ 。Bicarp有 $m$ 张牌,其中第 $i$ 张的攻击值为 $\mathit{bx}_i$,防御值为 $\mathit{by}_i$。在第一步棋中,Monocarp 选择他的一张牌并打出。Bicarp 必须用他自己的牌来回应,而这张牌要胜过那张牌。之后,Monocarp 必须用一张击败比卡普的牌来回应。之后,轮到 Bicarp,以此类推。

**一张牌被打出后,回到打出该牌的玩家手中。** 这意味着每个玩家总是拥有游戏开始时的同一套牌。
游戏结束时,若当前玩家手中的牌不能击败对手刚刚打出的牌,当前玩家输掉游戏。如果对局持续 $100^{500}$ 步,则宣布平局。

Monocarp 和 Bicarp 都是最佳下法。也就是说,如果棋手无论对手下了多少步棋,都有获胜的策略,那么他就会获胜。否则,如果他有平局策略,他就下平局。要求您计算三个值:

- Monocarp 的起手牌中导致 Monocarp 获胜的牌数;
- Monocarp 的起手牌中导致平局的牌数;
- Monocarp 的起手牌中导致 Bicarp 获胜的牌数。

多组数据,$1 \le t \le 10^4$,$1 \le n \le 3 \cdot 10^5$,$1 \le \mathit{ax}_i,\mathit{ax}_y,\mathit{bx}_i,\mathit{by}_i \le 10^6$,$\sum n,\sum m \leq 3 \cdot 10^5$。

该@谁啊。

2023/11/4 19:10
加载中...