好题

WeLikeStudying · 2021-10-04 20:43:53 · 题解

• 一些巧妙的题目对我的帮助是启发式的。
• 先记下来，因为比较难以分类。

  CF1223G Wooden Raft

  题意

• 给出一个数列 \lbrace a_n\rbrace 代表每段木头的长度，你可以将每段木头锯成任意长度为整数的小段，找到 2 根长为 x 的木头，x 根长度为 y 的木头且满足 x,y\ge 2（容易发现它形成了一个木筏形状），求 x\cdot y 的最大值。

暴力实现

• 我们可以枚举 x,y，再用一个背包判断能否装下，复杂度 \Theta(n^3) 。
• 代码实现。
• 枚举 x 二分 y 复杂度 \Theta(n^2\lg n) 。
• 代码实现。
• 没什么优化空间了，个人认为主要是因为我们用的 DP 太 low 了。

思路

• 显然 \lbrace a_n\rbrace 应该先排序。
• 考虑枚举 y，然后有个比较巧妙的东西。
• 以下是每块模板的长度以 y 的倍数为分界点所形成的图像。
• 妙处在哪？
• 若最大的数字为 A ，第一次最多 A 块，第二次 \lfloor\frac A2\rfloor，第三次 \lfloor\frac A3\rfloor 块……
• 枚举块数的总和是一个调和级数： \sum_{i=1}^n\bigg\lfloor\frac Ai\bigg\rfloor=O(A\ln A)
• 咱们下一段解决一个比较困扰的细节问题，如何这样分块，如果再用朴素的算法显然是不行的。
• 然后我们再试着利用块内的性质。

分块的妙用

• 怎么分？
• 每一块二分结果，总复杂度是 O(A\cdot\ln A\cdot\lg n)。
• 很危险。
• 开一大个桶，b_i 保存值为 i 的元素个数。
• 鉴于后面的一些操作，我们可以再来一个指针查询每个元素的非零前驱，用于找到每块内的最大或次大元素。
• 同样的原因我们会维护一个前缀和用于求块内的区间和。

继续实现细节

• 考虑没有 x 的情况能分多少段 y 。
• 答案是 \sum\lfloor\frac {a_i}y\rfloor，这时候我们对于每块统计个数即可在 \Theta(\lfloor\frac Ay\rfloor) 的时间得到结果。
• 然后考虑两个相等的 x 应该怎么办，这时候我们分两种情况讨论，两个 x 在同一块木板内，或者不在。

两块 x 木板在同一块木板内被切割

• 像这图片一样，木板的选择是贪心的，满足两个条件：长度大于等于 2x，除以 y 的余数最大（还有一个隐形的条件，必须是每块内部的最大值）
• 你也知道该怎么办了吧，枚举每个块，处理后缀模 y 最大值。
• 如果枚举到 ky\le2x<ky+y 后缀和，则 y 的段数显然为 -k+\sum\lfloor\frac {a_i}y\rfloor 两者取 \min 得到合法的 x 。

两块 x 木板分别取自不同木板

• 像这图片一样，木板的选择是贪心的，满足两个条件：长度大于等于 x，除以 y 的余数最大（还有一个隐形的条件，必须是每块内部的最大值或次大值）
• 枚举每个块，处理后缀模 y 最大值和次大值。
• 如果枚举到 ky\le x<ky+y 后缀和（x 应该取次大的），则 y 的段数显然为 -2k+\sum\lfloor\frac {a_i}y\rfloor 两者取 \min 得到合法的 x。
• 还有另外一种情况：（x 取最大的）此时要在更长的一块木头上削去一段（如果存在的话），y 的段数为 -2k-1+\sum\lfloor\frac {a_i}y\rfloor，方法很类似这里就不给出图片了。

代码实现

• 时间复杂度 \Theta(n+A\ln A) 空间复杂度 \Theta(n+A)。
• 常数似乎会比较大，不管了就这么发出来吧。
• 代码实现。