题解：P14801 [CCPC 2024 哈尔滨站] 造计算机

思路

递归构造公共后缀。（本质是有限状态自动机）

考虑直接暴力？造二叉树即可，但节点过多不可以。

但我们有一堆子树是重复的，共用即可。具体细节看代码。

实现

check_maxlen 函数

void check_maxlen(int l,int r,int ll,int rr){int mid=l+r>>1;if(l==ll&&r==rr){int len=0;int tmp=r-l+1;  // 区间长度while(tmp){len++;tmp>>=1;}if(len>ma) ma=len;  // 更新最大长度return;}if(rr<=mid)check_maxlen(l,mid,ll,rr);else if(ll>mid)check_maxlen(mid+1,r,ll,rr);else{check_maxlen(l,mid,ll,mid);check_maxlen(mid+1,r,mid+1,rr);}
}

计算区间 \([ll,rr]\) 在满二叉树结构 \([0,2^{20})\) 中对应节点需要的最大二进制长度。（脑子不太好使，其实可以一个 for 解决，但结构和构造一样就不改了）

复杂度：\(O(\log R)\)。

build 函数 - 构造

void build(int x,int l,int r,int ll,int rr,int zero,pair<int,int> las){int mid=l+r>>1;if(l==ll&&r==rr){  // 当前区间完全在目标区间内int len=0;int tmp=r-l+1;while(tmp){len++;tmp>>=1;}v[las.first].push_back(make_pair(len,las.second));return;}if(zero) x=++top;  // 需要创建新节点if(zero&&las.first) v[las.first].push_back(make_pair(x,las.second));if(ll>mid)build(x,mid+1,r,ll,rr,1,make_pair(x,1));else if(rr<=mid)build(x,l,mid,ll,rr,zero,make_pair(x,0));else{build(x,l,mid,ll,mid,zero,make_pair(x,0));build(x,mid+1,r,mid+1,rr,1,make_pair(x,1));}
}

解释：

• x: 当前处理的节点编号；
• l,r: 当前考虑的数值范围；
• ll,rr: 目标区间 [L,R]；
• zero: 是否需要创建新节点；
• las: 上一个状态（节点编号，边权）。

逻辑：

1. 完全覆盖情况：如果当前区间 \([l,r]\) 完全在 \([ll,rr]\) 内，直接连接到后缀链中对应的长度节点。
2. 部分覆盖情况：
   • 如果目标区间完全在右半：创建新节点（zero=1），边权为 \(1\)；
   • 如果目标区间完全在左半：可能重用节点，边权为 \(0\)；
   • 如果跨越中点：分别处理左右两部分。

复杂度: \(O(\log R)\)。

主函数

signed main(){cin>>L>>R;ma=0;check_maxlen(0,(1<<20)-1,L,R);// 构建后缀共享链top=ma;for(int i=2;i<=ma;i++){v[i].push_back(make_pair(i-1,0));v[i].push_back(make_pair(i-1,1));}top++;build(top,0,(1<<20)-1,L,R,0,make_pair(0,0));cout<<top<<'\n';for(int i=1;i<=top;i++){cout<<v[i].size()<<' ';for(int j=0;j<v[i].size();j++){cout<<v[i][j].first<<' '<<v[i][j].second<<' ';}cout<<'\n';}return 0;
}

总复杂度：\(O(\log R)\)。