1 条题解

  • 0
    @ 2026-5-8 8:43:56

    套路地建出 trie 树。此时加字符操作相当于往儿子走,B 操作相当于往父亲走,E 操作相当于跳到根。

    结论 11:一定按照 dfs 序遍历这棵树,这是显然的。

    结论 22T 操作一定从根开始跳,根据按 dfs 序遍历的结论,一定不需要用到除最后一次输入的串之外的其他串。所以从根开始跳可以节省步数。

    结论 33:对一个点 uu,遍历所有儿子一定按子树深度顺序,出去一个子树一定从最深的叶子出去。

    首先如果刚刚走完 xx 并输入,再跳到 yy,有这两种走法:

    • 从根到 yy 一个一个字符走。
    • 进行 T 操作跳到 xx,沿着树上 xyx\to y 的路径一个一个字符走。

    结论 33 证明:如果还没走完整个子树的话,还要从这个叶子走回来;如果要走完了就不用走回来了。因为叶子越深,走回来的步数越多,所以从最深叶子出去跳出子树省去的步数越多,的总步数越少。

    确定了路线,直接模拟走的过程即可,从 xx 跳到 yy 选两种走法中最优的。

    #include<bits/stdc++.h>
    #define il inline
    #define ui unsigned int
    #define ll long long
    #define ull unsigned ll
    #define lll __int128
    #define db double
    #define ldb long double
    #define pii pair<int,int>
    #define vi vector<int>
    #define vpii vector<pii>
    #define fir first
    #define sec second
    #define gc getchar
    #define pc putchar
    #define pb push_back
    #define lb lower_bound
    #define ub upper_bound
    #define pct __builtin_popcount
    #define mst(a,x) memset(a,x,sizeof a)
    #define mcp(a,b) memcpy(a,b,sizeof b)
    using namespace std;
    const int N=1e6+10,INF=0x3f3f3f3f,MOD=998244353;
    const ll INFll=0x3f3f3f3f3f3f3f3f;
    il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
    il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
    il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
    il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
    il void wr(int x,const char *s) {wr(x),printf("%s",s);}
    il void wrll(ll x,const char *s) {wrll(x),printf("%s",s);}
    il int vmod(int x) {return x>=MOD?x-MOD:x;}
    il int vadd(int x,int y) {return vmod(x+y);}
    il int vsub(int x,int y) {return vmod(x-y+MOD);}
    il int vmul(int x,int y) {return 1ll*x*y%MOD;}
    il int qpow(int x,int y) {int r=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) r=vmul(r,x); return r;}
    il void cadd(int &x,int y) {x=vmod(x+y);}
    il void csub(int &x,int y) {x=vmod(x-y+MOD);}
    il void cmul(int &x,int y) {x=vmul(x,y);}
    il void cmax(int &x,int y) {x<y&&(x=y);}
    il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
    il void cmin(int &x,int y) {x>y&&(x=y);}
    il void cminll(ll &x,ll y) {x>y&&(x=y);}
    int n,idx,tr[N][26],d[N],mx[N],ps[N];
    string s[N];
    vi vc[N];
    void ins(int x) {
    	int u=0;
    	for(int i=0;i<s[x].size();i++) {
    		int o=s[x][i]-'a';
    		if(!tr[u][o]) tr[u][o]=++idx,d[idx]=d[u]+1;
    		u=tr[u][o];
    	}
    	mx[u]=s[x].size(),ps[x]=u,vc[u].pb(x);
    }
    int ac[N][20];
    void dfs(int u,int fa) {
    	ac[u][0]=fa;
    	for(int i=1;i<20;i++) ac[u][i]=ac[ac[u][i-1]][i-1];
    	for(int i=0;i<26;i++) if(tr[u][i])
    		dfs(tr[u][i],u),cmax(mx[u],mx[tr[u][i]]);
    }
    int lca(int u,int v) {
    	if(d[u]<d[v]) swap(u,v);
    	for(int i=19;~i;i--) if(d[ac[u][i]]>=d[v]) u=ac[u][i];
    	if(u==v) return u;
    	for(int i=19;~i;i--) if(ac[u][i]!=ac[v][i]) u=ac[u][i],v=ac[v][i];
    	return ac[u][0];
    }
    int ln,sq[N];
    string as;
    void sch(int u) {
    	vi tmp;
    	for(int i=0;i<26;i++) if(tr[u][i]) tmp.pb(tr[u][i]);
    	sort(tmp.begin(),tmp.end(),[&](int x,int y) {return mx[x]<mx[y];});
    	for(int i:vc[u]) sq[++ln]=i;
    	for(int i:tmp) sch(i);
    }
    void QwQ() {
    	n=rd();
    	for(int i=1;i<=n;i++) cin>>s[i],ins(i);
    	dfs(0,0),sch(0);
    	for(int i=1;i<=ln;i++) {
    		if(i==1) as+=s[sq[i]],as+='E';
    		else {
    			int p=lca(ps[sq[i-1]],ps[sq[i]]);
    			if(d[ps[sq[i]]]<=d[ps[sq[i-1]]]+d[ps[sq[i]]]-d[p]*2+1) as+=s[sq[i]],as+='E';
    			else {
    				as+='T';
    				for(int j=1;j<=d[ps[sq[i-1]]]-d[p];j++) as+='B';
    				for(int j=s[sq[i]].size()-(d[ps[sq[i]]]-d[p]);j<s[sq[i]].size();j++) as+=s[sq[i]][j];
    				as+='E';
    			}
    		}
    	}
    	cout<<as.size()<<"\n"<<as;
    }
    signed main() {
    //	freopen("ex_26TG01T4_test5.in","r",stdin),freopen("out.out","w",stdout);
    	int T=1; while(T--) QwQ();
    }
    
    • 1

    「POI2026 R1」浏览器 / Przeglądarka internetowa

    信息

    ID
    9641
    时间
    3000ms
    内存
    2024MiB
    难度
    10
    标签
    递交数
    11
    已通过
    1
    上传者