字符串 题解
题意
设删去第 (k) 条记录，则要为剩下的 (n-1) 条记录分配串 (s_1,s_2,dots,s_{n-1})，满足：
- (|s_i| = l_i)（长度固定，跳过被删的那条）；
- (s_1 < s_2 < cdots < s_{n-1})（按原顺序，字典序严格递增，规定 (0<1)）；
- 任意两个串互不为前缀。
每个删除位置独立判断，不同位置可以用不同的分配方案。
直接对着"字符串"思考很困难：串的取值有指数多种。突破口是把三个约束全部量化关系，让"串"消失。
第一步转化：串 ( o) 二叉树节点
"任意一个串都不是另一个串的前缀"——这正是前缀编码的限制。把所有 01 串放进一棵满二叉树（Trie）：
- 从根出发，读到
0走左儿子，读到1走右儿子； - 每个串对应树上唯一一个节点，串长就是节点深度。
于是三个约束变成：
| 字符串世界的约束 | 二叉树的含义 |
|---|---|
| (s) 是 (t) 的前缀 | (s) 对应的节点是 (t) 对应节点的祖先 |
| 两两无前缀关系 | 选中的节点互不为祖先 |
| 字典序递增 | 选中的节点从左到右依次排列 |
题目变成：给定各节点的深度序列，删除一个后，能否按原顺序从左到右选出互不为祖先的这些节点？
第二步转化：节点 ( o) 叶子区间
节点之间的"祖先 / 左右"关系还是不够具体。把树补全到深度 60（因为 (l_ile 60)），最底层共有
(U = 2^{60})
片叶子，从左到右编号 (0sim U-1)（叶子从左到右恰好是二进制值 (0,1,2,dots) 递增，与 (0<1) 的规定一致）。
每个节点对应一段连续的叶子区间。 以深度 2 为例，底层叶子依次是 00,01,10,11：
| 串 | 它下面的叶子 | 对应区间 |
|---|---|---|
0 |
00, 01 |
([0,2)) |
01 |
01 |
([1,2)) |
1 |
10, 11 |
([2,4)) |
一般的：长为 (l)、二进制值为 (b) 的串，其子树的叶子恰是所有以它为前缀的 60 位 01 串，即
(left[,bcdot 2^{60-l}, (b+1)cdot 2^{60-l}, ight).)
记 (w_i = 2^{60-l_i})（块宽），那么每条记录对应一段长度为 (w_i)、起点是 (w_i) 的整数倍（对齐） 的区间。这一步"对齐"就是节点区间把 ([0,U)) 均匀切分的体现。
三个关系全部量化：
| 二叉树 | 叶子区间 |
|---|---|
| 祖先 - 后代 | 区间包含 |
| 互不为祖先 | 区间互不相交 |
| 从左到右 | 区间按此顺序排列 |
问题重述：把 (n) 条记录看成 (n) 个块，第 (i) 块长 (w_i = 2^{60-l_i})。删掉一个块后，能否把其余块按原顺序、互不相交地放进 ([0,U))，且每块起点是块宽的倍数？
（可以紧贴：前一块终点 = 后一块起点是允许的，只要不共享叶子——对应"同一片叶子不能同时属于两个被选节点"。）
为什么"总长够"不等于"放得下"
用深度 2（(U=4)）演示：长度 ((2,1,2)) 对应块宽 ((1,2,1))，总宽恰好 4。
- 第一块最早放在 ([0,1))；
- 第二块必须对齐 2 的倍数，最早只能放 ([2,4))；
- 第三块已无处可放。
顺序和对齐缺一不可，这正是本题不能只看 (sum w_i le U) 的原因。
暴力：(O(n^2)) 贪心
枚举删除位置 (k)，对剩下的块从左到右依次放置，每块放在最靠左的合法位置：
设前面所有块已在 ([0,u)) 内放好（(u) 是当前右端点），当前块宽 (w)。合法起点必须是对齐 (w) 且 (ge u) 的最小值，即 (wleftlceil dfrac{u}{w} ight ceil)，故右端点更新为
(u leftarrow wleft(leftlceil frac{u}{w} ight ceil + 1 ight),qquad u ext{ 初始为 } 0.)
若某块放不下（(u > U)）则该 (k) 失败；全部放下则成功。 (O(n^2))
贪心为什么不劣？（交换论证）前面结束得越早，后面所有块的可用空间是 ([u,U)) 的子集式放宽——任何"放得下"的方案中，第 (i) 块的起点 (s) 都满足 (s ge) 贪心的右端点且对齐，所以贪心起点 (le s)，贪心永远不会比某个可行方案更早失败。
正解：前后缀预处理 + (O(1)) 判定
(O(n^2)) 的浪费在于：删不同位置时，相同的左侧前缀被反复重放。左右两段其实与"删谁"无关，可以各预处理一次。
前缀：最靠左贪心 (F)
设 (F_i) = 只放前 (i) 块（原序列的第 (1sim i) 块）时，最靠左放法的右端点；(F_0 = 0)。第 (i) 块宽 (w_i)，合法起点 (ge F_{i-1}) 且对齐，最小起点为 (w_ileftlceil F_{i-1}/w_i ight ceil)，因此
(oxed{,F_i = w_ileft(leftlceil frac{F_{i-1}}{w_i} ight ceil + 1 ight),})
一遍从左到右 (O(n)) 求出。
后缀：最靠右贪心 (G)
对称地，从右往左，把每块放在最靠右的合法位置。设 (G_i) = 只放第 (isim n) 块时最靠右放法的左端点；(G_{n+1} = U)（右边没有约束）。第 (i) 块的右端点须 (le G_{i+1}) 且对齐，最大右端点为 (w_ileftlfloor G_{i+1}/w_i ight floor)，因此
(oxed{,G_i = w_ileft(leftlfloor frac{G_{i+1}}{w_i} ight floor - 1 ight),})
（因为右端点 (-w_i) 后就是左端点：(leftlfloorfrac{G_{i+1}-w_i}{w_i} ight floor = leftlfloorfrac{G_{i+1}}{w_i} ight floor-1)，此处无取整歧义。）一遍从右到左 (O(n)) 求出。
判定：删 (k) 可行 (iff F_{k-1}le G_{k+1})
删掉第 (k) 块后，剩余序列 = 原前缀 ((1sim k-1)) 拼上原后缀 ((k+1sim n))。
总结
本题的思维链条是三层"翻译"：
( ext{串约束} xrightarrow{ ext{前缀编码}} ext{二叉树节点} xrightarrow{ ext{补全到深度 60}} ext{对齐叶子区间} xrightarrow{ ext{贪心极值}} ext{一次线性判定})
- 转化把"存在指数多的串方案"压缩成"区间能否按序放置"；
- 前后缀贪心把 (O(n^2)) 的枚举删除复用成 (O(n)) 的两次递推；
- (F_{k-1}le G_{k+1}) 一个不等式完成判定