题解

思路

关键观察

记每种类型在整副牌中出现次数为 $c_x$。若不考虑抽牌时序，最多可以配出

$$M=\sum_x\left\lfloor\frac{c_x}{2}\right\rfloor$$

对同类牌。我们改为计算因为时序约束而被迫损失的配对数。

手中始终有 $k$ 张牌（最后牌组耗尽后除外）。只要手中某一类型至少有两张，就可以先打出一对同类牌。真正受阻的唯一情形是：手中 $k$ 张牌的类型两两不同；由于恰有 $k$ 种类型，此时手中每种类型恰好一张。

设 $P_i$ 为前 $i$ 张牌各类型出现次数的奇偶向量。此前打出的同类牌不会改变奇偶性，所以在抽完前 $i$ 张牌后出现上述受阻状态，当且仅当 $P_i$ 的 $k$ 个分量全为 $1$。

在受阻位置 $p$，必须打出两个不同类型 $x,y$。设牌组剩余部分中类型 $x$ 的数量为 $s_x$。打出手中的单张 $x$ 会使可配对数损失

$$\left\lfloor\frac{s_x+1}{2}\right\rfloor-\left\lfloor\frac{s_x}{2}\right\rfloor=s_x\bmod2.$$

因此这次选择的损失为剩余后缀中 $x,y$ 两种类型的奇数个数，即 $0,1$ 或 $2$。

打出 $x,y$ 后继续优先打同类牌。下一个受阻位置 $q$ 满足

$$P_p\oplus P_q=e_x\oplus e_y.$$

也就是两个前缀奇偶向量恰有 $x,y$ 两位不同。对于固定的 $(x,y)$，只能转移到最早满足条件的 $q$；若不存在这样的 $q$，说明之后能够直接完成游戏。

做法

子任务 1：状态搜索

在 $n\le18,k\le12$ 时，用“已抽取位置 + 每种类型的手牌数”作为记忆化搜索状态。枚举手中实际存在的两张牌，计算本回合得分并抽入后两张牌。该算法直接模拟全部合法策略，是小规模独立真值机。

状态数随 $n,k$ 指数增长，适用于子任务 1。

子任务 2：枚举弃牌类型对

保存每个精确前缀奇偶串出现的全部位置。令 $dp_p$ 表示到达受阻位置 $p$ 时最少损失的配对数。

对每个可达的 $p$，枚举 $x<y$：

• 把 $P_p$ 的第 $x,y$ 位翻转，得到目标奇偶串；
• 在该串的位置表中二分查找第一个大于 $p$ 的位置 $q$；
• 若存在，更新 $dp_q$；否则用当前损失更新结束答案。

奇偶串采用确定性字符串表示，不依赖随机哈希。该做法在 $n\le200$ 时足够快。

满分算法：反向枚举后继位置

注意从固定 $p$ 到某个 $q$ 时，若 $P_p\oplus P_q$ 恰有两位为 $1$，对应的弃牌类型对被唯一确定。因此不再枚举 $\binom{k}{2}$ 个类型对，而是枚举后继位置 $q$。

把奇偶向量压成若干个 64 位整数。对每个可达的 $p$：

1. 顺序扫描 $q=p+2,p+4,\ldots,n$；
2. 计算 $P_p\oplus P_q$ 的置位数；只有恰为 $2$ 时才产生一种类型对；
3. 同一类型对只保留最早的 $q$，按后缀奇偶性计算 $0,1,2$ 的损失并转移；
4. 分别统计后缀奇偶性组合为 $0,1,2$ 的类型对总数，以及已经存在后继位置的不同类型对数。若某类中存在没有后继的类型对，就能以对应损失结束游戏。

最后答案为 $M$ 减去最小损失。

正确性证明

优先打出同类牌不会产生损失，也不会改变已抽牌的类型奇偶向量。只要手牌不是每种类型恰好一张，就一定存在同类牌可打；因此所有需要决策的位置恰好是前缀奇偶向量全为 $1$ 的受阻位置。

在受阻位置打出不同类型 $x,y$ 后，类型 $x$ 的潜在配对数恰在剩余数量为奇数时减少一，类型 $y$ 同理，所以转移代价等于两者的后缀奇偶位之和。

之后持续打同类牌，第一次再次无法打出同类牌的位置，恰是最小的 $q>p$，满足 $P_p\oplus P_q$ 只有 $x,y$ 两位为 $1$。因此 DP 的每条转移与一种合法决策一一对应，且不能跳过更早的受阻位置。若这样的 $q$ 不存在，则该选择可直接完成余下游戏。

DP 枚举了每个受阻位置的所有不同类型对，并累加其精确损失，故得到全局最小损失。用离线最大配对数 $M$ 减去它，即为最大硬币数。

复杂度分析

子任务 1 为指数状态搜索。

子任务 2 枚举受阻位置和类型对，并对精确奇偶串做查找；在 $n,k\le200$ 的限制内可通过。

满分算法的时间复杂度为

$$O\!\left(n^2\left(\frac{k}{64}+\log n\right)\right),$$

空间复杂度为 $O(nk/64+n)$。