1 条题解
-
0
套路地建出 trie 树。此时加字符操作相当于往儿子走,
B操作相当于往父亲走,E操作相当于跳到根。结论 :一定按照 dfs 序遍历这棵树,这是显然的。
结论 :
T操作一定从根开始跳,根据按 dfs 序遍历的结论,一定不需要用到除最后一次输入的串之外的其他串。所以从根开始跳可以节省步数。结论 :对一个点 ,遍历所有儿子一定按子树深度顺序,出去一个子树一定从最深的叶子出去。
首先如果刚刚走完 并输入,再跳到 ,有这两种走法:
- 从根到 一个一个字符走。
- 进行
T操作跳到 ,沿着树上 的路径一个一个字符走。
结论 证明:如果还没走完整个子树的话,还要从这个叶子走回来;如果要走完了就不用走回来了。因为叶子越深,走回来的步数越多,所以从最深叶子出去跳出子树省去的步数越多,的总步数越少。
确定了路线,直接模拟走的过程即可,从 跳到 选两种走法中最优的。
#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
信息
- ID
- 9641
- 时间
- 3000ms
- 内存
- 2024MiB
- 难度
- 10
- 标签
- 递交数
- 11
- 已通过
- 1
- 上传者