企业官网建设流程全解析

L

题面

思路

嗯

朴素 DP

设dp[i]表示修复前i个 bug 的最短时间。

转移时枚举上一次修复到第j个 bug（0≤j<i0 \le j < i0≤j<i），本次修复第j+1j+1j+1到第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≤j<i(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≤j<imin​(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)4=k48 2 \cdot \left(\frac{k}{2}\right)^4 = \frac{k^4}{8}2⋅(2k​)4=8k4​

节省了：

k4−k48=78k4 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）。

因此，只要节省的修复时间大于额外的运行时间，拆分就更优：

78k4>n \frac{7}{8}k^4 > n87​k4>n

解得：

k>8n74 k > \sqrt[4]{\frac{8n}{7}}k>478n​​

对于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这种高次代价，应立刻反应过来：高次代价意味着"集中处理"非常昂贵，拆分成小份更划算。这是一种常见直觉——当代价函数是凸函数且增长很快时，最优解往往不会让单个决策的规模太大。

具体思考步骤：

1. 写出 DP 方程，发现是O(m2)O(m^2)O(m2)。
2. 盯着(i−j)4(i-j)^4(i−j)4看，意识到它增长很快。
3. 问自己：如果一次处理很多个，会不会拆开更好？
4. 构造"拆成两半"的对比，计算出临界值。
5. 得到上界后，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×105，n1/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)=x2，f(x)=x4f(x) = x^4f(x)=x4，f(x)=exf(x) = e^xf(x)=ex。

相反，开口向下的函数叫凹函数（concave），例如f(x)=−x2f(x) = -x^2f(x)=−x2，f(x)=ln⁡xf(x) = \ln xf(x)=lnx。

3. 为什么凸函数在优化中重要？

凸函数有一个关键性质：局部最小值就是全局最小值。

在 DP 优化中，如果代价函数是凸的，那么"把一个大块拆成几个小块"往往会降低总代价。这可以用Jensen 不等式解释：

f(x+y2)≤f(x)+f(y)2 f\left(\frac{x+y}{2}\right) \le \frac{f(x)+f(y)}{2}f(2x+y​)≤2f(x)+f(y)​

即"平均输入的代价 ≤ 平均代价"。所以把大输入拆成小输入，总代价会下降。

在之前的题目中，修复kkk个 bug 的代价是k4k^4k4，这是一个凸函数。所以把kkk拆成两半，总修复代价2⋅(k/2)4=k4/82 \cdot (k/2)^4 = k^4 / 82⋅(k/2)4=k4/8远小于k4k^4k4。这就是为什么最优解不会一次修复太多 bug——拆开更划算。

4. 总结

• 凸函数：开口向上，满足f(平均)≤平均(f)f(\text{平均}) \le \text{平均}(f)f(平均)≤平均(f)。
• 性质：增长越来越快，拆分会降低总代价。
• 在竞赛中：看到平方、四次方、指数等代价，先想它是不是凸的，如果是，就可以考虑"限制转移范围"或"贪心拆分"。

理解凸函数，能帮你快速识别那些"高次代价导致最优解规模受限"的题目。

AC Code

voidsolve(){// for(int i=1;i<=50;i++)// {// cout<<qm(i,4)<<' ';// if(i%5==0)cout<<'\n';// }// cout<<'\n';/* 我们发现 x^4 的花销很大 17^4 > 2e5 所以这道题，最多拖 17 行，和其他 bug一起 de 否则开销就太大了 */intn,m;cin>>n>>m;vector<int>a(m+1,0);for(inti=1;i<=m;i++){cin>>a[i];}vector<int>dp(m+1,INF);//dp做好初始化dp[0]=0,dp[1]=a[1]+1;for(inti=2;i<=m;i++){for(intj=i-1;j>=max(0ll,i-17);j--){dp[i]=min(dp[i],dp[j]+a[i]+qm(i-j,4));}}cout<<dp[m]<<'\n';return;}

M

题面

思路

嗯

AC Code

voidsolve(){intn;cin>>n;vector<int>a(n+1,0),b(n+1,0);// int amx=0,bmx=0;// int ami=INF,bmi=INF;for(inti=1;i<=n;i++){cin>>a[i];// amx=max(amx,a[i]);// ami=min(ami,a[i]);}for(inti=1;i<=n;i++){cin>>b[i];// bmx=max(bmx,b[i]);// bmi=min(bmi,b[i]);}intl=-1,r=1e9+1;autocheck=[&](intk)->int{intnl=0,nr=0;for(inti=1;i<=n;i++){if(i==1){nl=a[i]-k*b[i];nr=a[i]+k*b[i];}else{nl=max(nl,a[i]-k*b[i]);nr=min(nr,a[i]+k*b[i]);}if(nl>nr)return0;}return1;};while(l+1<r){intmid=(l+r)>>1;if(check(mid))r=mid;elsel=mid;}cout<<r<<'\n';return;}

A

题面

思路

嗯

AC Code

学到一招： (to_string (n) ).size()定n的数位

voidsolve(){intn,d;cin>>n>>d;intdig=(to_string(n)).size();intN=1234567890+d;N*=qm(10,dig);// cout<<N<<'\n';intk=(N+n-1)/n;cout<<k<<'\n';return;}