L题面思路嗯朴素 DP设dp[i]表示修复前i个 bug 的最短时间。转移时枚举上一次修复到第j个 bug0≤ji0 \le j i0≤ji本次修复第j1j1j1到第iii个共i−ji-ji−j个 bug。本次调试需要运行到第aia_iai​行耗时aia_iai​秒修复i−ji-ji−j个 bug 耗时(i−j)4(i-j)^4(i−j)4秒。因此dp[i]min⁡0≤ji(dp[j]ai(i−j)4) dp[i] \min_{0 \le j i}\left(dp[j] a_i (i-j)^4\right)dp[i]0≤jimin​(dp[j]ai​(i−j)4)初始dp[0]0dp[0] 0dp[0]0答案为dp[m]dp[m]dp[m]。直接做是O(m2)O(m^2)O(m2)当m≤2×105m \le 2 \times 10^5m≤2×105时必然超时。观察代价项(i−j)4(i-j)^4(i−j)4增长极快四次方函数增长非常快。如果一次修复kkk个 bug代价是k4k^4k4若将其拆成两次、每次修复k/2k/2k/2个代价为2⋅(k2)4k48 2 \cdot \left(\frac{k}{2}\right)^4 \frac{k^4}{8}2⋅(2k​)48k4​节省了k4−k4878k4 k^4 - \frac{k^4}{8} \frac{7}{8}k^4k4−8k4​87​k4而拆分后多了一次调试额外运行时间最多为ai≤na_i \le nai​≤n每次都要从第 1 行运行到第aia_iai​行且第二次的aia_iai​不会超过nnn。因此只要节省的修复时间大于额外的运行时间拆分就更优78k4n \frac{7}{8}k^4 n87​k4n解得k8n74 k \sqrt[4]{\frac{8n}{7}}k478n​​对于n≤2×105n \le 2 \times 10^5n≤2×105有8n/74≈2.3×1054≈22\sqrt[4]{8n/7} \approx \sqrt[4]{2.3 \times 10^5} \approx 2248n/7​≈42.3×105​≈22。所以最优解中一次修复的 bug 数量不会超过该上界实际实现取 17 更保守。如何想到这个方向赛时看到x4x^4x4这种高次代价应立刻反应过来高次代价意味着集中处理非常昂贵拆分成小份更划算。这是一种常见直觉——当代价函数是凸函数且增长很快时最优解往往不会让单个决策的规模太大。具体思考步骤写出 DP 方程发现是O(m2)O(m^2)O(m2)。盯着(i−j)4(i-j)^4(i−j)4看意识到它增长很快。问自己如果一次处理很多个会不会拆开更好构造拆成两半的对比计算出临界值。得到上界后DP 时只枚举前O(n1/4)O(n^{1/4})O(n1/4)个状态复杂度降到O(m⋅n1/4)O(m \cdot n^{1/4})O(m⋅n1/4)对于n≤2×105n \le 2 \times 10^5n≤2×105n1/4≈22n^{1/4} \approx 22n1/4≈22完全可行。拓展凸包( •̀ ω •́ )✧凸函数convex function是数学中描述开口向上、碗状曲线的一类函数。直观上它的图像像一只碗任意两点之间的连线都在这条曲线的上方或重合。1. 数学定义设fff是定义在某个区间上的函数。如果对任意x,yx, yx,y和任意t∈[0,1]t \in [0,1]t∈[0,1]都有f(tx(1−t)y)≤tf(x)(1−t)f(y) f(t x (1-t) y) \le t f(x) (1-t) f(y)f(tx(1−t)y)≤tf(x)(1−t)f(y)那么fff就是凸函数。左边是函数在x,yx, yx,y之间某点的值右边是f(x)f(x)f(x)和f(y)f(y)f(y)的加权平均。这个不等式说的是函数值不会超过两点连线的值也就是曲线在连线下方。2. 直观理解图像开口向上像字母 U。切线斜率越来越大从左到右。如果函数可导那么f′′(x)≥0f(x) \ge 0f′′(x)≥0。典型例子f(x)x2f(x) x^2f(x)x2f(x)x4f(x) x^4f(x)x4f(x)exf(x) e^xf(x)ex。相反开口向下的函数叫凹函数concave例如f(x)−x2f(x) -x^2f(x)−x2f(x)ln⁡xf(x) \ln xf(x)lnx。3. 为什么凸函数在优化中重要凸函数有一个关键性质局部最小值就是全局最小值。在 DP 优化中如果代价函数是凸的那么把一个大块拆成几个小块往往会降低总代价。这可以用Jensen 不等式解释f(xy2)≤f(x)f(y)2 f\left(\frac{xy}{2}\right) \le \frac{f(x)f(y)}{2}f(2xy​)≤2f(x)f(y)​即平均输入的代价 ≤ 平均代价。所以把大输入拆成小输入总代价会下降。在之前的题目中修复kkk个 bug 的代价是k4k^4k4这是一个凸函数。所以把kkk拆成两半总修复代价2⋅(k/2)4k4/82 \cdot (k/2)^4 k^4 / 82⋅(k/2)4k4/8远小于k4k^4k4。这就是为什么最优解不会一次修复太多 bug——拆开更划算。4. 总结凸函数开口向上满足f(平均)≤平均(f)f(\text{平均}) \le \text{平均}(f)f(平均)≤平均(f)。性质增长越来越快拆分会降低总代价。在竞赛中看到平方、四次方、指数等代价先想它是不是凸的如果是就可以考虑限制转移范围或贪心拆分。理解凸函数能帮你快速识别那些高次代价导致最优解规模受限的题目。AC Codevoidsolve(){// for(int i1;i50;i)// {// coutqm(i,4) ;// if(i%50)cout\n;// }// cout\n;/* 我们发现 x^4 的花销很大 17^4 2e5 所以这道题最多拖 17 行和其他 bug一起 de 否则开销就太大了 */intn,m;cinnm;vectorinta(m1,0);for(inti1;im;i){cina[i];}vectorintdp(m1,INF);//dp做好初始化dp[0]0,dp[1]a[1]1;for(inti2;im;i){for(intji-1;jmax(0ll,i-17);j--){dp[i]min(dp[i],dp[j]a[i]qm(i-j,4));}}coutdp[m]\n;return;}M题面思路嗯AC Codevoidsolve(){intn;cinn;vectorinta(n1,0),b(n1,0);// int amx0,bmx0;// int amiINF,bmiINF;for(inti1;in;i){cina[i];// amxmax(amx,a[i]);// amimin(ami,a[i]);}for(inti1;in;i){cinb[i];// bmxmax(bmx,b[i]);// bmimin(bmi,b[i]);}intl-1,r1e91;autocheck[](intk)-int{intnl0,nr0;for(inti1;in;i){if(i1){nla[i]-k*b[i];nra[i]k*b[i];}else{nlmax(nl,a[i]-k*b[i]);nrmin(nr,a[i]k*b[i]);}if(nlnr)return0;}return1;};while(l1r){intmid(lr)1;if(check(mid))rmid;elselmid;}coutr\n;return;}A题面思路嗯AC Code学到一招 (to_string (n) ).size()定n的数位voidsolve(){intn,d;cinnd;intdig(to_string(n)).size();intN1234567890d;N*qm(10,dig);// coutN\n;intk(Nn-1)/n;coutk\n;return;}