自动搬运

查看原文

来自洛谷，原作者为

	M1saka16I72 afo / 我们一定相连着 接近着 能再次相遇的

搬运于2025-08-24 22:59:13，当前版本为作者最后更新于2024-06-08 09:38:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

更可爱的阅读体验

思路

观察到 $|s|$ 只有 $5$，于是考虑状态压缩。

可以枚举一个位数为当前字符串长度的二进制数 $st$，每一位代表这一位是否进行匹配。然后我们就可以根据 $st$ 再进行一次状压，把字符串压成一个 $27$ 进制的数，每一位 $\geq 1$ 时代表字母，是 $0$ 则代表这一位没有被匹配。这个数的最大大小为 $\sum^{4}_{i=0}26^i<1.5\times 10^6$，可以直接开数组统计。

插入时，我们把字符串对应的所有状态曾经对应过的 $x$ 取 $\min$，查找时按匹配度从大到小查询，如果当前答案不为 inf 就直接输出，这题就做完了，复杂度 $\mathcal{O}(2^{|s|}|s|\times q)。$

代码

constexpr int N = 15e6;

int m[N];
vector<int> S[6];

inline int id(int st,string s){
	for(int i=s.length();i<5;i++){
		if(st>>i&1)	return -1;
	}
	int res = 0,b = 1;
	for(int i=0;i<s.length();i++){
		if(st>>i&1)	res+=b*(s[i]-'a'+1);
		b*=27;
	}
	return res;
}

void solve(){
	for(int i=0;i<(1<<5);i++)	S[__builtin_popcount(i)].pb_(i);
	int q;cin>>q;
	while(q--){
		int op;string s;cin>>op>>s;
		if(op==1){
			int x;cin>>x;
			for(int l=0;l<=s.length();l++){
				for(int st:S[l]){
					int now = id(st,s);
					if(now==-1)	continue;
					if(!m[now] || m[now]>x)	m[now] = x;
				}
			}
		}
		else{
			for(int l=s.length();l>=0;l--){
				int res = inf;
				for(int st:S[l]){
					int now = id(st,s);
					if(now==-1)	continue;
					if(m[now]){res = min(res,m[now]);}
				}
				if(res<inf){cout<<res<<"\n";break;}
			}
		}
	}
}