题解：P11088 [ROI 2021 Day 1] 穿孔卡片

· · 题解

尝试贪心地依次选择能放在当前最上面的卡片。即先选择最上面的卡片，然后次上层，次次上层......

显然，卡片 i 能放在最上面的条件是 \sum [ s_{a_{i,j}}\neq c_{i,j} ] = 0。

于是记 f_i=\sum [ s_{a_{i,j}}\neq c_{i,j} ]，并将所有 f_i=0 的卡片 i 放到一个队列 q 中。

假设放置了第一张卡片 i，并将 i 放入答案队列 ans 中，现在需要更新后面的卡片。

具体地，若卡片 i 覆盖了位置 j，那么后面选择的卡片就不需要在乎位置 j 上的字符是否正确，因为位置 j 已经被卡片 i 正确的字母覆盖了。

那么可以提前对于所有字符串下标 r 开一个桶 g_r。输入时对于卡片 w，若有 s_{a_{w,j}}\neq c_{w,j}，将 w 放在桶 g_{a_{w,j}} 中。

此时遍历卡片 i 覆盖的所有位置 j，若位置 j 被之前的卡片覆盖就跳过，否则遍历桶 g_j 内的每一个元素 w，令 f_w\leftarrow f_w-1。

若更新完有 f_w=0，那么将 w 也放到队列 q 中。

同时记录指针 cnt 表示未被覆盖的下标个数，初始有 cnt=m，每次覆盖一个新的位置就令 cnt\leftarrow cnt-1。

若存在某一时刻 cnt=0，就将剩余未选择的卡片随意放入 ans 中，然后遍历 ans 中的元素输出。

若存在某一时刻 cnt\neq 0 且队列 q 为空，则输出无解。

对于遍历每个位置，时间复杂度为 \Theta(\sum k)。

对于遍历所有 g_i，由于每个位置 i 只会被覆盖 1 次，那么时间复杂度也为 \Theta(\sum k)。

总时间复杂度 \Theta(n+\sum k)，可以通过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+15;
int n,m,hd=1,tl,q[N],vist[N],visp[N],f[N];//vist[i]:卡片i是否被使用 visp[i]:位置i是否被覆盖
vector<int>ans,p[N],g[N];//p[i]:卡片i覆盖的位置 g[i]:意义见题解 
char c,s[N];
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int k,j,i=1;i<=n;++i){
        scanf("%d",&k);
        while(k--){
            scanf("%d %c",&j,&c);
            p[i].push_back(j);
            if(s[j]!=c)++f[i],g[j].push_back(i);//模拟
        }
        if(!f[i])q[++tl]=i;//模拟
    }
    int cnt=m;
    for(int w;hd<=tl;){
        ans.push_back(w=q[hd++]),vist[w]=true;//取出一个f值为0的卡片w
        for(int i:p[w]){
            if(visp[i]==true)continue;
            --cnt,visp[i]=true;//遍历w覆盖的所有位置
            for(int j:g[i]){
                if(!--f[j])q[++tl]=j;//更新
            }
        }
        if(!cnt){
            for(int i=1;i<=n;++i){if(!vist[i])ans.push_back(i);}
            for(int i:ans)printf("%d ",i);
            return 0;
        }
    }
    printf("-1");//(cnt!=0 && q.empty()==true)
    return 0;
}