P9868 [NOIP2023] 词典 思路最短题解

· · 题解

众所周知，pbds 里有一个 trie，但是它不能有相同字符串，并且 1s 跑不了 1e5 插入。

但是注意到本题 w_i 互不相同，并且 n \le 3000。

所以直接上 trie 就好了。如何将字符串排序应该不用多说。

应该是本题思维难度 + 代码复杂度双最小做法（？）

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int MAXN = 3030;
trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_order_statistics_node_update> t;
int n,m;
string s[MAXN];

void init() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        cin >> s[i];
        sort(s[i].begin(), s[i].end(),greater<char>());
        t.insert(s[i]);
        reverse(s[i].begin(), s[i].end());
    }
}

int main() { 
    init(); 
    for(int i = 1;i <= n;i++) cout << (t.lower_bound(s[i]) == t.begin());
}