问题重述

给定一个长度为 $n$（$1 \le n \le 10^5$）的字符串 $s$，仅包含小写字母 a ~ f。你可以任意交换字符串中的字母（相当于可以任意重排）。同时，有 $m$ 个位置限制：某些位置只能放置特定的字母集合（每个位置允许的字母是 a ~ `f$ 的一个非空子集）。没有限制的位置可以放置任何字母。

目标：找到一个重排后的字符串，满足所有位置限制，并且字典序最小。如果不存在，输出 "Impossible"。

算法核心思想

由于字母种类只有 $6$ 种，我们可以将问题转化为网络流 + 贪心构造。

第一步：建模为二分图匹配 / 网络流

• 左侧节点：字母种类（a ~ `f$），共 $6$ 个节点。
• 右侧节点：位置允许集的类型（即 a ~ `f$ 的所有非空子集），共 $2^6 - 1 = 63$ 种类型（代码中用了 $64$ 种，包含空集但不会出现）。
• 源点 $s$ 连向每个字母节点 $ch$，容量 = 原字符串中该字母的出现次数。
• 每个字母节点 $ch$ 连向所有包含该字母的允许集节点 $mask$，容量为 $+\infty$（代码中取 $100000$ 足够大）。
• 每个允许集节点 $mask$ 连向汇点 $t$，容量 = 有多少个位置要求恰好这个允许集。

求出最大流。如果最大流 $< n$，说明无法满足所有位置，输出 "Impossible"。

第二步：贪心构造最小字典序

关键观察：字典序最小意味着从左到右每个位置尽可能放小的字母。

我们按位置 $0$ 到 $n-1$ 依次决定字母：

• 对于当前位置 $i$，其允许集为 $allowed\_mask[i]$。
• 尝试字母 'a' 到 'f' 中允许的字母。
• 假设我们在位置 $i$ 放入字母 $ch$（满足 $(allowed\_mask[i] \gg ch) \& 1 = 1$），我们需要检查剩余部分是否仍然有解。

检查方法：
我们从当前流网络中暂时扣除一个字母 $ch$，并暂时扣除一个允许集 $mask$ 的容量，然后尝试寻找一条增广路。如果能找到增广路，说明剩余部分仍可完成匹配，就选择该字母；否则不能选该字母。

标程中的 check 函数详解

check(ch, mask) 的作用：判断在当前残留网络中，能否将字母 $ch$ 分配给允许集 $mask$（即当前位置），且剩余部分仍能完美匹配。

网络流节点编号

• 字母节点 a ~ f：编号 $0$ ~ $5$。
• 允许集节点 $mask$：编号 $6$ ~ $6 + 63$。
• 源点 $s = 70$，汇点 $t = 71$。

check 函数的执行流程

1. 合法性检查：若 $ch$ 不在 $mask$ 中，返回 false。
2. 获取关键边：
   • $e1$：源点 $s$ 到字母节点 $ch$ 的边。
   • $e2$：允许集节点 $mask$ 到汇点 $t$ 的边。
3. 如果 $e1$ 或 $e2$ 的当前流量为 $0$：说明没有可分配的字母或该允许集已满，返回 false。
4. 尝试扣除：先将 $e1$ 的流量减 $1$（反向边加 $1$），表示暂用一个字母 $ch$。
5. 寻找匹配路径：
   • 从字母节点 $ch$ 出发，找一条正向边（非反向）且当前流量 $> 0$，走到某个允许集节点 $mask'$，将该边流量减 $1$。
   • 再从 $mask'$ 出发，找一条正向边到汇点 $t$，将该边流量减 $1$。
   • 这样就构成了一条从 $s \to ch \to mask' \to t$ 的路径，流量为 $1$ 被暂时移除。
6. 判断汇点边 $e2$ 的情况：
   • 如果 $e2$ 当前流量 $<$ 容量，说明 $mask$ 还有空位，直接扣减 $e1$ 和 $e2$ 各 $1$ 容量，返回 true。
   • 否则，需要释放一条已有的匹配来为 $mask$ 腾出空间。这要通过反向边增广来实现。
7. 反向边调整（复杂部分）：
   • 从 $mask$ 出发，找一条反向边（流量为负）到某个字母节点 $ch'$，将该边流量加 $1$（即减少反向流量）。
   • 再从 $ch'$ 出发，找一条反向边到源点 $s$，同样调整。
   • 这相当于在残留网络中找一条从 $t$ 到 $s$ 的路径，释放一条旧的匹配。
8. 尝试增广：将 $e1$ 和 $e2$ 的容量各减 $1$，然后调用 dfs(s, 1) 看能否找到增广路（即能否重新分配）。
   • 若能找到，返回 true。
   • 若不能，恢复所有被修改的边，返回 false。

时间复杂度分析

• 最大流：$O(\text{flow} \cdot E)$，这里 $E \approx 6 \times 64 + 64 + 6 = 454$，$flow = n \le 10^5$，但每次增广是 $O(E)$，总 $O(n \cdot E) \approx 4.5 \times 10^7$，可接受。
• 贪心构造：每个位置尝试最多 $6$ 个字母，每次 check 调用 dfs 一次，$O(E)$，总 $O(6nE) \approx 2.7 \times 10^8$，在 2 秒内可勉强通过（常数小）。

示例验证

样例 1

bedefead
5
2 e
1 dc
5 b
7 ef
6 ef

原串字母统计：a:1, b:1, c:0, d:2, e:3, f:1
限制：

• 位置 1（0-based）：允许 dc → mask {c,d} 对应 $2^2+2^3=12$
• 位置 2：允许 e → mask {e} 对应 $2^4=16$
• 位置 4：允许 b → mask {b} 对应 $2^1=2$
• 位置 5：允许 ef → mask {e,f} 对应 $2^4+2^5=48$
• 位置 6：允许 ef → mask {e,f} 对应 $48$

网络流匹配后，贪心构造得到 deadbeef。

样例 2

无限制，直接排序原串得到 aaaabbc。

样例 3

fc
2
1 cfab
2 f

位置 1：允许 c,f,a,b → mask {a,b,c,f} 位置 2：允许 f

原串有 f,c 各一。贪心：

• 位置 1 尝试 a 不行，b 不行，c 可以 → 放 c
• 位置 2 只能放 f → 得到 cf

总结

该题是网络流 + 贪心构造的经典应用。关键点：

1. 用 $6$ 位掩码表示允许集，建图做最大流判断可行性。
2. 贪心时用 check 函数在残留网络中判断能否分配当前字母。
3. 注意网络流边的方向、正向/反向边的处理，以及增广路的查找。

本题的难点在于 check 函数中对已有匹配的调整，需要理解残留网络的反向边作用。