Pre

一道并不难的图论模型题，前提是得要想得到图论。

Solution

Subtask 11：

由于 n≤8n \le 8，直接将卡片的顺序进行全排列，再依次判断是否可行即可，预估时间复杂度为 O(n!×∑ki)O(n! \times \textstyle{\sum k_i})。

Subtask 22：

由于卡片之间地约束条件很多，考虑搜索。理所当然地从上到下考虑，不妨先考虑第一张：第一张可以被选当且仅当该卡片上所有字母都可以和目标串匹配。一旦字符串上的某个位置 SiS_i 被匹配，我们标记掉这个位置，因为后面的卡片不会影响这个位置了。

不难发现，每一张卡片做出贡献的位置一定是目前第一次出现的位置，因此不必注意先后顺序。一旦可以有贡献并且合法，我们就进行下一层的搜索。

尽管理论时间复杂度为指数级别，但是真正的合法状态很少，可以拿到 5050 分。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int n, m;
char target[N];    // 目标字符串
vector<pair<int, char>> vec[N];    // vec[i] 存储第i张卡片的字符信息
int path[N], idx;    // 记录答案
bool vis[N], used[N], temp[N][N];
    // vis: 第i个位置是否覆盖	used：第i张是否使用
void dfs(int cur, int rest)
{
    if (rest == 0)	// 如果没有剩余要覆盖的
    {
        for (int i = 1; i <= idx; i ++)
            cout << path[i] << ' ';
        for (int i = 1; i <= n; i ++)	// 一定要输出完整
            if (!used[i]) cout << i << ' ';
        cout << '\n';
        exit(0);
    }
    if (cur > n)	// 否则无解
    {
        cout << -1 << '\n';
        exit(0);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (used[i]) continue;	// 是否被用过
        bool valid = true;	// 判断当前是否合法
        for (auto [pos, ch] : vec[i])
            if (!vis[pos] && ch != target[pos])
            {
                valid = false;
                break;
            }
        if (!valid) continue;
        memcpy(temp[cur], vis, sizeof vis);
        
        int cnt = 0;
        for (auto [pos, ch] : vec[i])
            if (!vis[pos]) vis[pos] = true, cnt ++;
        used[i] = true, path[++ idx] = i;
        
        dfs(cur + 1, rest - cnt);
        
        idx --, used[i] = false;	// 还原现场
        memcpy(vis, temp[cur], sizeof temp[cur]);
    }
}

Subtask 33

对字符串的一个位置（设为 SiS_i）进行分析，如果 SiS_i 未被覆盖，那么必然有可以覆盖 SiS_i 的卡片在后面出现，因此在可以覆盖 SiS_i 的卡片集合向该位置 ii 各连一条有向边，表示一旦达到某个卡片，位置 ii 就会被更新。

回到之前说的第一张卡片如何选，肯定是选择没有与字符串冲突的卡片，而随着卡片的选择以及字符串的被覆盖，冲突必然会越少，一旦冲突为 00，就表示可以将这张卡片放进去了。

至此做法就明了了，我们采取类似拓扑排序的方式，用已经选择卡片的覆盖字母不断更新未选卡片的冲突大小（冲突大小在图论中表现为一个点的入度），一旦没有冲突（即入度为 00​）就加入队列当中。显然本身没有冲突的点要预先加入图中。

预计时间复杂度为 O(n+m+∑k)O(n + m + \sum k)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010, M = N << 1;
const int INF = 0x3f3f3f3f;

int n, m;
char str[N], ch[10];
int rh[N], h[N], e[M], ne[M], idx;
int que[M], hh = 0, tt = -1;
int ans[N], cnt;    // 记录答案
int indeg[N];    // 入度（冲突值）
bool mark[N], tag[N];

inline void add(int *h, int a, int b) { e[++ idx] = b, ne[idx] = h[a], h[a] = idx; }
// 这里使用邻接表的方式分别记录 第i个卡片可以去更新的点 第i个位置被覆盖后可以删去冲突的卡片

signed main()
{
    memset(h, -1, sizeof h), memset(rh, -1, sizeof rh);
    scanf("%d%d%s", &n, &m, str + 1);
    for (int i = 1, k, pos; i <= n; i ++)
    {
        scanf("%d", &k);
        while (k --)
        {
            scanf("%d%s", &pos, ch);
            if (ch[0] == str[pos]) add(h, i, pos + n);
            else
            {
                add(rh, pos + n, i);
                indeg[i] ++;	// 第i张卡片的冲突增加
            }
            tag[pos] = true;
        }
    }
    for (int ver = 1; ver <= m; ver ++)    // 特判，否则会WA几个点
        if (!tag[ver]) return !puts("-1");
    
    for (int ver = 1; ver <= n; ver ++)
        if (!indeg[ver]) que[++ tt] = ver;
    
    while (hh <= tt)
    {
        int ver = que[hh ++];
        ans[++ cnt] = ver;	// 表示选择了当前卡片
        for (int i = h[ver]; ~i; i = ne[i])	// 更新可以更新的点
        {
            int pos = e[i];
            if (mark[pos]) continue;
            mark[pos] = true;
            for (int j = rh[pos]; ~j; j = ne[j])	// 说明这些点已经被覆盖，让有冲突的卡片减少1
                if (!-- indeg[e[j]]) que[++ tt] = e[j];	// 同拓扑排序
        }
    }
    if (cnt == n)
        for (int i = 1; i <= cnt; i ++)
            printf("%d%c", ans[i], " \n"[i == cnt]);
    else puts("-1");
    
    return 0;
}