题解：P14648 [POI 2025/2026 #1] 浏览器 / Przeglądarka internetowa

· · 题解

一道不错的贪心。

思路

将所有网址插入 Trie，不难发现可以利用公共前缀来优化不同网址的操作次数。

设上一个读入的网址的结束位置在节点 u，目前要读入的网址位置在节点 v。可以通过一次 TAB 和若干次 BACKSPACE 得到两个网址的公共前缀，即到达 \text{LCA}(u,v)。记 l=\text{LCA}(u,v)，则操作的代价为 dep_u-dep_l+1，当然我们也可以直接输入，代价为 dep_l。故走到 l 的代价为 \min(dep_u-dep_l+1,dep_l)。

每次操作必定处理完整个子树，故我们可以递归处理，对于节点 u，考虑规划一种最优的孩子子树处理顺序。由于代价随上一棵子树结束网址的深度单调不减，并且最后处理的子树不需要支付返回代价，因此将所有儿子按照子树内最深目标网址的深度升序排序，使最深的子树最后处理。

子树内的操作是连续的，后续的操作不会出现在中间插入的情况，于是我们考虑双向链表维护，跑 DFS 从下往上构造每个子树的操作序列，按顺序处理每个子树，再用双向链表将每个子树的操作序列拼接，从而得到完整的操作序列。

代码

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
//#define int long long
#define in(a) a = read()
#define PII pair<int , int>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5 , mod = 998244353 , inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline int read() {
    int x = 0 , ch = getchar() , f = 0;
    while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
    while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
    return f ? -x : x;
}
string s[N];
int trie[N][26] , tot , n , dep[N] , us[N] , fa[N];
void insert(string &x , int id) {
    int u = 0;
    for(int i = 0 ; i < x.size() ; i ++) {
        if(!trie[u][x[i] - 'a']) trie[u][x[i] - 'a'] = ++ tot;
        u = trie[u][x[i] - 'a'];
    }
    us[u] = id;
}
struct node {
    int c = 0 , x = 0 , l = 0 , r = 0;
};
bool cmp(node x , node y) {
    return dep[x.x] < dep[y.x];
}
int ls[N << 1] , rs[N << 1] , cnt , top;
char c[N << 1] , sta[N];
int push_back(int i , char x) {
    rs[i] = ++ cnt , ls[cnt] = i , c[cnt] = x;
    return cnt;
}
int push_front(int i , char x) {
    ls[i] = ++ cnt , rs[cnt] = i , c[cnt] = x;
    return cnt;
}
node dfs(int u , char C) {
    vector<node>vs;
    for(int i = 0 ; i < 26 ; i ++) {
        int v = trie[u][i];
        if(v) {
            fa[v] = u , dep[v] = dep[u] + 1;
            sta[++ top] = char('a' + i);
            vs.push_back(dfs(v , char('a' + i)));
            top --;
        }
    }
    node now;
    now.x = u;
    if(!vs.empty()) {
        sort(vs.begin() , vs.end() , cmp);
        now = vs[0] , now.x = vs.back().x;
        for(int i = 1 ; i < vs.size() ; i ++) {
            int x = vs[i - 1].x;
            now.c += vs[i].c;
            if(dep[x] - dep[u] + 1 < dep[u]) {
                now.r = push_back(now.r , 'T');
                now.c ++;
                while(x != u) {
                    now.r = push_back(now.r , 'B');
                    now.c ++;
                    x = fa[x];
                }
            } else {
                for(int j = 1; j <= top ; j ++) {
                    now.r = push_back(now.r , sta[j]);
                    now.c ++;
                }
            }
            rs[now.r] = vs[i].l , now.r = vs[i].r;
        }    
    }
    if(us[u]) {
        if(now.l == 0) {
            now.l = now.r = ++ cnt , c[cnt] = 'E';
            now.c ++;   
        } else {
            now.l = push_front(now.l , 'T');   
            now.l = push_front(now.l , 'E');
            now.c += 2;   
        }
    }
    now.l = push_front(now.l , C);
    now.c ++;
    return now;
}
signed main() {
    cin_fast;
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> s[i] , insert(s[i] , i);
    node ans = dfs(0 , '#');
    cout << ans.c - 1 << '\n';
    for(int i = rs[ans.l] ; i ; i = rs[i]) cout << c[i];
    return 0;
}