P10564 [ICPC2024 Xi’an I] Rubbish Sorting 题解

思路

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

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

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

代码

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
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;}
            }
        }
    }
}