自动搬运

查看原文

来自洛谷，原作者为

	Hollow_knight_ -Silk Song is a lie-

搬运于2025-08-24 23:04:09，当前版本为作者最后更新于2024-10-22 16:54:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

显然，卡片 $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;
}