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

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