## 长方形

### 50分

枚举四条边的长度（或只枚举较短边 $a$），统计满足条件的方案数，时间复杂度 $O(n)$，可以通过子任务 $1,2$。

核心代码：

```cpp
if (n & 1) { cout << 0 << '\n'; return 0; }
long long s = n / 2, ans = 0;
for (long long a = 1; a < s; ++a) if (a < s - a) ++ans;
cout << ans << '\n';
```

### 100分

设四段长度从小到大为 $a \le b \le c \le d$。要用它们组成矩形，四条边必须两两相等，即 $a = b$ 且 $c = d$；又不能是正方形，所以 $b \neq c$。于是

$$a + b + c + d = 2(a + c) = n$$

记短边为 $x$、长边为 $y$，则 $x + y = \dfrac{n}{2}$ 且 $1 \le x < y$。

- 若 $n$ 为奇数，$2(x+y) = n$ 无整数解，答案为 $0$；
- 否则令 $s = \dfrac{n}{2}$，$x$ 可取 $1, 2, \dots, \left\lfloor \dfrac{s-1}{2} \right\rfloor$，答案就是 $\left\lfloor \dfrac{s-1}{2} \right\rfloor$。

时间复杂度 $O(1)$。

核心代码：

```cpp
long long n;
cin >> n;
if (n & 1) { cout << 0 << '\n'; return 0; }
long long s = n / 2;
cout << (s - 1) / 2 << '\n';
```

### 常见错误

- 忽略 $n$ 为奇数时无解，直接输出 $n / 4$。例如 $n = 11$ 会算成 $2$，正确答案是 $0$。
- 忘记排除正方形：$n = 4t$ 时不能把 $(t,t,t,t)$ 计入，答案应为 $t - 1$ 而不是 $t$。

## 充值会员

### 40分

$n \le 1000$ 时，第 $i$ 天直接回扫所有 $j \le i$，看是否存在 $j+a_j-1 \ge i$ 即可。

时间复杂度 $O(n^2)$。

核心代码：

```cpp
for (int i = 1; i <= n; i++) {
    bool own = false, bor = false;
    for (int j = 1; j <= i; j++)
        if (a[j] && j + a[j] - 1 >= i) own = true;
    for (int j = 1; j <= i; j++)
        if (b[j] && j + b[j] - 1 >= i) bor = true;
    if (own) x++; else if (bor) y++; else z++;
}
```

### 100分

关键观察：第 $i$ 天小明自己有会员，当且仅当存在一个 $j \le i$ 使得 $j+a_j-1 \ge i$。因为所有可选的 $j$ 都满足 $j \le i$，这个条件等价于

$$\max_{j \le i}\bigl(j+a_j-1\bigr) \ge i .$$

所以只需维护两个量：$r_0$ 为已处理过的充值里小明最晚的到期日，$r_1$ 为小红最晚的到期日。扫到第 $i$ 天时先把 $i+a_i-1$、$i+b_i-1$ 更新进去（注意 $a_i=0$ 表示当天没充值，不能更新），再比较即可。

- $r_0 \ge i$：自己有会员，$x$ 加一；
- 否则 $r_1 \ge i$：借小红的，$y$ 加一；
- 否则 $z$ 加一。

时间复杂度 $O(n)$，空间 $O(n)$。

核心代码：

```cpp
int r0 = 0, r1 = 0, x = 0, y = 0, z = 0;
for (int i = 1; i <= n; i++) {
    if (a[i]) r0 = max(r0, i + a[i] - 1);
    if (b[i]) r1 = max(r1, i + b[i] - 1);
    if (r0 >= i) x++;
    else if (r1 >= i) y++;
    else z++;
}
```

### 常见错误

- 把 $a_i=0$ 也拿去更新最晚到期日，凭空多出一天会员期。
- 认为充值会"从下一天开始生效"，本题明确从当天算起，覆盖 $[i,\,i+a_i-1]$。
- 误以为要模拟"到期后重新充值"的叠加，实际上多次充值取最晚到期日就够了。

## 菜品研发

### 30分

$n = 1$ 时答案就是 $\left\lfloor (a_1 + kc)/b_1 \right\rfloor$；答案不超过 $10^4$ 时，从 $0$ 开始一个个枚举答案，每次 $O(n)$ 判定即可。

判定：做 $x$ 道菜需要第 $i$ 种食材 $x b_i$ 个，缺口为 $d_i=\max(0,\,xb_i-a_i)$，每包魔法粉变出 $c$ 个**同一种**食材，所以第 $i$ 种需要 $\lceil d_i/c\rceil$ 包，总和不超过 $k$ 就可行。

时间复杂度 $O(n\cdot \text{答案})$。

核心代码：

```cpp
bool ok(ll x) {
    ll used = 0;
    for (int i = 1; i <= n; i++) {
        ll d = x * b[i] - a[i];
        if (d > 0) { used += (d + c - 1) / c; if (used > k) return false; }
    }
    return used <= k;
}
```

### 100分

能做的菜越多，需要的魔法粉越多，可行性关于 $x$ **单调**，于是二分答案。每次判定 $O(n)$，总复杂度 $O(n\log \text{Ans})$，$\text{Ans}$ 上界取 $4\times 10^{18}$ 足够（答案不超过 $\min_i (a_i+kc)/b_i \le 10^{18}+10^9$）。

注意 $x$ 最大可达 $10^{18}$ 量级，$x\cdot b_i$ 会爆 `long long`。两种稳妥写法：

- 全程用 `__int128` 算 $xb_i-a_i$；
- 或像 std 那样先拆成 $a_i/b_i$ 与 $a_i\bmod b_i$，只在"剩余魔法粉足够"时才去算 $need\cdot b_i$。

时间复杂度 $O(n\log \text{Ans})$。

核心代码($\_\_int128$)：

```cpp
typedef __int128 lll;
bool ok(ll x) {
    lll used = 0;
    for (int i = 1; i <= n; i++) {
        lll d = (lll)x * b[i] - a[i];
        if (d > 0) { used += (d + (lll)c - 1) / (lll)c; if (used > (lll)k) return false; }
    }
    return used <= (lll)k;
}
ll l = 0, r = 4000000000000000000LL;
while (l < r) { ll mid = l + (r - l + 1) / 2; if (ok(mid)) l = mid; else r = mid - 1; }
```

核心代码（先判断再乘防止爆ll）：

```c++
const int maxn = 2e5 + 5;
ll n,m,k,c,ans;
ll a[maxn],b[maxn];
int jud(ll x){
    ll res = k;
    for(int i = 1; i <= n; i++){
        ll need = x - (a[i] / b[i]);
        if(need <= 0) continue;
        if((res * c + a[i] % b[i]) / b[i] < need) return 0;
        res -= (need * b[i] - a[i] % b[i] + c - 1) / c;
    }
    return 1;
}
int main(){
    cin>>n>>k>>c;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) cin>>b[i];
    ll l = 0,r = inf;
    while(l < r){
        ll mid = (l + r) >> 1;
        if(jud(mid)) l = mid + 1,ans = mid;
        else r = mid;
    }
    cout<<ans<<endl;
    return 0;
}
```

### 常见错误

- 用 `int` 存答案。样例 4 的答案是 $10^{18}+1$，必须用 `long long`。
- 把 $k$ 包魔法粉当成 $kc$ 个**任意分配**的食材（那样只需比较总量）。实际上每包只能变同一种，因此必须对每种食材分别上取整后再求和。
- 判定里写 $d_i/c$ 而不是 $\lceil d_i/c\rceil$，会高估可做的菜数。

### 33DAI 的代码

#### 暴力枚举

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
// 表示食材数、魔法粉数、消耗一包魔法粉可以获得的食材数量
int n, k, c;
int a[MAXN + 5]; // 第 i 种食材的数量
int b[MAXN + 5]; // 研发一道菜品需要消耗第 i 种食材的数量。
// 能不能做出来 x 道菜
bool check(long long x)
{
    __int128 cnt = 0; // 记录要用多少魔法粉
    for (int i = 1; i <= n; i++)
    {
        __int128 need = (__int128)x * b[i] - a[i]; // 还要这么多个食材 i
        if (need <= 0)
            continue;
        // 需要 need/c 上取整这么多魔法粉
        cnt += (need + (c - 1)) / c;
    }
    return cnt <= k;
}
int main()
{
    freopen("dish.in", "r", stdin);
    freopen("dish.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> c;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (long long ans = 1;; ans++)
        if (!check(ans)) // ans道菜做不出来
        {
            cout << ans - 1;
            return 0;
        }
    return 0;
}

```


#### 100 分

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
// 表示食材数、魔法粉数、消耗一包魔法粉可以获得的食材数量
int n, k, c;
int a[MAXN + 5]; // 第 i 种食材的数量
int b[MAXN + 5]; // 研发一道菜品需要消耗第 i 种食材的数量。
// 能不能做出来 x 道菜
bool check(long long x)
{
    __int128 cnt = 0; // 记录要用多少魔法粉
    for (int i = 1; i <= n; i++)
    {
        __int128 need = (__int128)x * b[i] - a[i]; // 还要这么多个食材 i
        if (need <= 0)
            continue;
        // 需要 need/c 上取整这么多魔法粉
        cnt += (need + (c - 1)) / c;
    }
    return cnt <= k;
}
int main()
{
    freopen("dish.in", "r", stdin);
    freopen("dish.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> c;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    long long L = 0;
    long long R = 1'000'000'001'000'000'000;
    long long ans = 0;
    while (L <= R)
    {
        long long mid = (L + R) / 2;
        if (check(mid))
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }
    cout << ans;
    return 0;
}

```

## 环形赛场

### 100分

**来源：原创**

**破环成链**：编号最小的开放城市固定为 $x$，故把 $a$ 倍长为 $a_1\ldots a_{2n}$，所有讨论都落在链 $[x,\,x+n]$ 上。

设 $dp_{i,j}$ 表示开放了 $j$ 个城市、其中编号最大的开放城市是 $i$ 时，目标城市在 $[x,i]$ 中的选手消耗的体力之和的最小值。

- 初始化：$dp_{x,1} = 0$；
- 转移：$dp_{i,j} = \min\limits_{x \le p < i}\{dp_{p,j-1} + cost_{p,i}\}$；
- 答案：$\min\{dp_{i,j} + cost_{i,\,n+x}\}$，末段 $[i,n] \cup [1,x]$ 的选手只能从 $i$ 或 $x$ 进入。

注意受 $x$ 的限制，未必能开满 $k$ 个城市，所以要对 $j \le k$ 一并取 $\min$。

**如何求 $cost$**：$cost_{p,i}$ 是从 $p$ 或 $i$ 进入、目标在 $[p,i]$ 的选手的消耗。$[\,p,\lfloor\frac{p+i}{2}\rfloor\,]$ 离 $p$ 更近，其余离 $i$ 更近，所以 $cost_{p,i}$ 等于一段"前缀平方和"拼一段"后缀平方和"，正反各递推一遍即可 $O(n^2)$ 全部预处理。

复杂度 $O(n^2 + n^2k)$，空间 $O(n^2)$（约 $128\,\mathrm{MiB}$）。

**子任务递进**

| 子任务 | 做法 | 复杂度 |
| :---: | --- | :---: |
| $k=1$ | 无需 DP，答案即 $cost_{x,\,n+x}$ | $O(n)$ |
| $k \le 2$ | 枚举第二个开放城市 | $O(n^2)$ |
| $n \le 100$ | $cost$ 用 $O(n^3)$ 朴素三重循环预处理 | $O(n^3)$ |
| 正解 | $cost$ 前缀和 + 后缀和优化 | $O(n^2k)$ |

**常见错误**

1. 当成"恰好 $k$ 个"：受 $x$ 限制可能开不满，必须对所有 $j \le k$ 取 $\min$。
2. 末段算漏：$[i,n]\cup[1,x]$ 的选手在 $i$ 与 $x$ 之间择优，不能只算从 $i$ 进入。
3. 用 `int` 存答案：$n=2\times10^3,\ a_i=10^6$ 时答案可达 $3\times10^{14}$，必须用 `long long`。

核心代码：

```c++
void solve(){
    read(n);read(k);read(x);
	rep(i,1,n){
        read(a[i]);
    }
	rep(i,n + 1,2 * n) a[i] = a[i - n];
	rep(i,1,2 * n){
        c[i] = 0;
		rep(j,i + 1,2 * n){
            c[j] = c[j - 1] + a[j] * (j - i) * (j - i);
			d[i][j] = c[(i + j) / 2];
		}
	}
    dep(i,n * 2,1){
        c[i] = 0;
       	dep(j,i - 1,1){
            c[j] = c[j + 1] + a[j] * (i - j) * (i - j);
			d[j][i] += c[(i + j + 2) / 2];
		}
    }
	rep(i,0,n) rep(j,0,k) dp[i][j] = inf;
    dp[x][1] = 0;
	ll ans = d[x][x + n];
	rep(i,x + 1,n){
		rep(j,2,k){
			dep(pre,i - 1,x){
				add(dp[i][j],dp[pre][j - 1] + d[pre][i]);
			}
		}
        rep(j,2,k) add(ans,dp[i][j] + d[i][n + x]);
	}
	printf("%lld\n",ans);
}
```


## 略策游戏

### 100分

**来源：原创**

#### 关键观察

由于 $A_i,B_j\ge 0$，对固定的行 $i$，小明要让 $C_{i,j}=A_i\times B_j$ 最小，就一定会选该行**未被选过的 $B_j$ 最小**的那一列（题面也明确了这条规则）。

于是每行被反复选中时，被划掉的一定是排好序后最靠前的那几个 $B$。设第 $i$ 行已被选走 $cnt_i$ 次，则它下一次的得分为

$$\text{val}_i=\begin{cases}A_i\times B_{cnt_i+1}, & cnt_i<m\\[4pt] 0,&cnt_i=m\end{cases}$$

其中 $B$ 已按升序排好。

#### 做法

把 $B$ 升序排序，用一棵线段树维护所有行的 $\text{val}_i$，每个节点额外记录取得该最大值时**最小的行号**（合并时平局取左子树，即可保证这一点）。

- 游戏轮 $[x,y]$：在线段树上查询区间最大值及其对应的最小行号 $id$，输出（注意答案要和 $0$ 取 $\max$），然后 $cnt_{id}\gets cnt_{id}+1$ 并单点更新该行。
- 修改轮 $A_x\gets y$：只影响尚未被选过的位置，单点重新计算第 $x$ 行即可；若 $cnt_x=m$，这一行无论怎么改都是 $0$，可跳过。

总复杂度 $O\big((n+q)\log n+m\log m\big)$。

#### 核心代码

```c++
// 合并时平局取左子树，保证 pos 是取得最大值的最小行号
void pu(int rt){
    if(tr[ls].mx >= tr[rs].mx) tr[rt].mx = tr[ls].mx, tr[rt].pos = tr[ls].pos;
    else                       tr[rt].mx = tr[rs].mx, tr[rt].pos = tr[rs].pos;
}

sort(b + 1, b + 1 + m);
rep(i, 1, n) c[i] = 1;                      // c[i] = 下一次会取到第几小的 B
build(1, 1, n);
while(q--){
    read(op); read(x); read(y);
    if(op == 1){
        int id = tr[qry(1, 1, n, x, y)].pos;
        printf("%lld\n", max(0LL, query_max(x, y)));
        c[id]++;
        upd(1, 1, n, id, c[id] <= m ? a[id] * b[c[id]] : 0);
    }else{
        a[x] = y;
        if(c[x] <= m) upd(1, 1, n, x, a[x] * b[c[x]]);
    }
}
```

#### 子任务提示

- 没有修改轮时，每行的 $cnt$ 只会增长、$A$ 不变，静态维护即可（子任务 $2,4$）。
- 有修改轮时才需要在修改后重新计算单行的 $\text{val}$（子任务 $3,5$）。
- $n,m,q\le 10^3$ 时也可以每次线性扫一遍区间，不需要线段树。

#### 边界讨论

- 某行的格子全部被选走后得分为 $0$，它与其他得 $0$ 的行一起参与「行号最小」的比较。
- $B$ 中出现 $0$ 时，所有行首次得分都是 $0$，此时靠「行号最小」选出第 $x$ 行。
- $A_i=0$ 的行得分恒为 $0$。
- $n=1$ 或 $m=1$ 时区间退化，注意 `qry` 返回值的合并写法。

## 亡羊补栏 —— 题解

### 一、题意重述与建模

$n$ 块木板排成一排，第 $i$ 块状态 $a_i \in \{0, 1\}$。买一块长度为 $L$ 的补丁可以盖住一段连续的 $L$ 块，价格为 $\lfloor \sqrt{L} \rfloor$；补丁可以压在完好木板上，但必须完整落在 $[1, n]$ 内。要求**所有 $a_i = 0$ 的位置都被盖住**，求最小总价。

把每一段极长的连续 `0` 称为一个**零段**，设共有 $m$ 段，第 $i$ 段为 $[\ell_i, r_i]$（$1$-indexed，段之间不相邻，$\ell$ 与 $r$ 都严格递增）。

### 二、三条关键引理

#### 引理 1（同价最长）

花费 $c$ 元能买到的补丁长度 $L$ 满足 $\lfloor \sqrt{L} \rfloor = c$，即 $c^2 \le L \le (c+1)^2 - 1$。

**取 $L = (c+1)^2 - 1$ 总是不劣**（盖得更长绝不会更差）。所以"花 $c$ 元"等价于"获得 $(c+1)^2 - 1$ 的覆盖长度"。

> 常见错误：只考虑 $L = c^2$。这样会低估每一档的能力，例如 $L = 8$ 时 $\lfloor\sqrt{8}\rfloor = 2$，但只考虑平方数的人会以为 $2$ 元只能买 $L = 4$，答案偏大。

#### 引理 2（补丁互不重叠，且按左端点有序）

设两块补丁 $A = [a_1, a_2]$、$B = [b_1, b_2]$ 满足 $a_1 \le b_1 \le a_2$（重叠）。把 $B$ 改成 $[a_2 + 1,\ b_2]$：

- 区间 $(a_2, b_2]$ 中的破损点原本由 $B$ 负责，改后仍由 $B$ 负责；
- 区间 $[b_1, a_2]$ 中的破损点已被 $A$ 盖住，不需要 $B$ 再盖；
- 新 $B$ 的长度 $\le$ 原长度，花费不增。

反复做这个操作，可化为**若干块互不重叠、按左端点从左到右排列**的补丁。

#### 引理 3（每块补丁都从某个零段的左端点开始）

在引理 2 的形态下，考虑最靠左的、还没被前面补丁盖住的零段 $[\ell_j, r_j]$。负责盖住 $\ell_j$ 的那块补丁，其左端点 $l \le \ell_j$。把它整体右移到 $l' = \ell_j$：

- $[l, \ell_j)$ 中没有需要它盖的破损点；
- 右端点同步右移，覆盖只会更多，花费不变。

所以每块补丁可以假定**从某个 $\ell_j$ 开始**。

由引理 2、3，最优解必然是：

> 把 $m$ 个零段按先后顺序切成若干**连续的组**，每一组用**一块**补丁，从该组第一段的 $\ell$ 一直盖到该组最后一段的 $r$。

于是问题变成：

$$\mathrm{dp}[i] = \min_{1 \le j \le i}\Big(\mathrm{dp}[j-1] + \big\lfloor\sqrt{r_i - \ell_j + 1}\big\rfloor\Big), \qquad \mathrm{dp}[0] = 0$$

答案即 $\mathrm{dp}[m]$（$m = 0$ 时答案为 $0$）。

### 三、$O(m^2)$ 朴素段 DP —— 过 S1~S3

直接按上式做，见 `savedata.cpp`。

- S3（$n \le 10^3$，$m \le 500$）：$2.5\times 10^5$ 次转移，轻松通过；
- S4（$n \le 3\times 10^4$，$m \le 1.5\times 10^4$）：$2.25\times 10^8$ 次转移，超时。

### 四、$O(m\sqrt{n}\log n)$ 桶优化 —— 过 S1~S4

固定 $j$，随着 $i$ 增大 $r_i$ 单调增大，所以

$$c(j, i) = \big\lfloor\sqrt{r_i - \ell_j + 1}\big\rfloor$$

关于 $i$ **单调不减**。维护每个 $j$ 当前所在的"桶" $\mathrm{cur\_c}[j]$，以及 $\mathrm{bucket}[c] = \{\mathrm{dp}[j-1] \mid \mathrm{cur\_c}[j] = c\}$（有序多重集），则

$$\mathrm{dp}[i] = \min_{c}\ \big(c + \min \mathrm{bucket}[c]\big)$$

**跨桶事件**：段 $j$ 会离开桶 $c$ 当且仅当 $r_i \ge \ell_j + (c+1)^2 - 1$。用优先队列按"触发的 $i$"排序，配合在 $r$ 数组上二分找出触发位置。每个 $j$ 至多跨 $\sqrt{n}$ 次桶，总复杂度 $O(m\sqrt{n}\log n)$。

两个必踩的坑：

1. **入桶时机**：$\mathrm{dp}[j-1]$ 只有在循环走到 $i = j$ 时才已经算好。必须在第 $i$ 步**先**把段 $i$ 入桶，再算 $\mathrm{dp}[i]$。第一版在初始化时就把所有 $\mathrm{dp}[j-1]$ 入桶，结果全是 `INT_MIN`。
2. **一次事件可能连跳多级**：不能写 `new_c = old_c + 1`。因为 $r_i$ 是跳跃增长的，触发时真实代价应该重新计算：

   ```cpp
   int new_c = isq((long long)r[i] - l[j] + 1);   // 正确
   // int new_c = old_c + 1;                      // 错误：会严重低估代价
   ```

   实测反例：$5$.in 的第 $1$ 段 $[\ell_1, r_1] = [1, 10]$ 起步 $c = 3$，当下一段的 $r$ 跳到 $142$ 时真实代价已是 $\lfloor\sqrt{142}\rfloor = 11$，而 `+1` 只得到 $4$，答案从 $25$ 掉到 $8$。

### 五、$O(n)$ 正解 —— 过全部子任务

换个角度，按**总花费**做 DP。

**定义**：$f[v]$ = 总花费不超过 $v$ 时，能从位置 $1$ 起"连续覆盖"到的最右端点，即 $[1, f[v]]$ 内所有 `0` 都已被盖住的最大 $f[v]$。

**转移**：最后一块补丁花 $c$ 元（$1 \le c \le v$）。由引理 1，它能盖 $(c+1)^2 - 1$ 长；由引理 3，它应从上一个还没盖住的 `0` 开始。记

$$\mathrm{nxt}[x] = \text{位置 } x \text{ 及其右侧第一个 } 0 \text{ 的位置（没有则为 } n+1)$$

则这一块的起点 $\mathrm{st} = \mathrm{nxt}[f[v-c] + 1]$，覆盖 $[\mathrm{st},\ \mathrm{st} + L - 1]$，之后第一个可能没盖到的位置是 $\mathrm{st} + L$，于是

$$f[v] = \max\Big(f[v-1],\ \max_{1 \le c \le v}\ \big(\mathrm{nxt}[\mathrm{st} + L] - 1\big)\Big),\qquad L = (c+1)^2 - 1$$

（$\mathrm{st} + L > n$ 时取 $n$。）

**答案**：设 $\mathrm{last}_0$ 是最后一个 `0` 的位置，答案是最小的 $v$ 使 $f[v] \ge \mathrm{last}_0$。没有 `0` 时答案为 $0$。

**为什么 $v$ 只需枚举到 $\lfloor\sqrt{n}\rfloor$**：一块长为 $\mathrm{last}_0 \le n$ 的补丁就能盖住全部破损，代价 $\lfloor\sqrt{\mathrm{last}_0}\rfloor \le \lfloor\sqrt{n}\rfloor$。

**复杂度**：$v$ 上界 $V = \lfloor\sqrt{n}\rfloor$，总转移次数 $\sum_{v=1}^{V} v = O(V^2) = O(n)$。预处理 $\mathrm{nxt}$ 也是 $O(n)$。$n = 10^7$ 时 $V = 3162$，转移约 $5\times 10^6$ 次，实测 **0.15 s**。

**内存**：$n = 10^7$ 时，`char s[n]` 约 10 MiB + `int nxt[n+2]` 约 40 MiB ≈ 50 MiB，256 MiB 足够。**不要**把 `nxt` 也开成 `char` 以外的多个 `int` 大数组，容易爆内存。

#### 两个 off-by-one（重写时实测踩到）

1. **起点必须是"下一个没盖住的 0"，不是 $f[v-c] + 1$**。若 $f[v-c]+1$ 处是 `1`，从那里起贴会白白浪费长度。反例：$n = 9$、`s = ` `100000000`，零段在 $[2, 9]$，正解是 $2$（一块长 $8$ 的补丁贴 $[2,9]$），若从 $1$ 起贴会得到 $3$。
2. **覆盖区间是 $[\mathrm{st}, \mathrm{st}+L-1]$**，所以"第一个可能没盖到的位置"是 $\mathrm{st} + L$，不是 $\mathrm{st} + L + 1$。反例：$n = 9$、`s = ` `000000000`，正解是 $3$（长 $9$ 的补丁），若多算一位会得到 $2$。

### 六、边界与易错点清单

| # | 易错点 | 表现 |
| :---: | --- | --- |
| 1 | 用 $L = c^2$ 而不是 $(c+1)^2 - 1$ | 答案偏大 |
| 2 | 用 $\lceil\sqrt{L}\rceil$ 计算代价 | 答案偏大（应为 $\lfloor\sqrt{L}\rfloor$） |
| 3 | 默认"每个零段单独打一块" | 交替数据上答案爆炸 |
| 4 | 默认"一块盖满全场" | 簇状数据上答案偏大 |
| 5 | 桶优化里 `new_c = old_c + 1` | 答案偏小（最难查的一类） |
| 6 | 桶优化里提前把未算好的 $\mathrm{dp}[j-1]$ 入桶 | 答案为 `INT_MIN` |
| 7 | 补丁起点取 $f+1$ 而非下一个 `0` | 答案偏大 |
| 8 | 覆盖右端点多算/少算 1 | 答案偏大或偏小 |
| 9 | 全 `1` 时未特判 | 未输出 $0$ |
| 10 | 数组大小按 $10^5$ 开 | S5 段错误 |
| 11 | Windows 下用 `fopen(..., "w")` 生成数据 | 数据带 CRLF，Linux 评测机读入异常 |

### 七、参考代码

```c++
const int maxn = 1e7 + 5;
int n,m,k,q;
int a[maxn];
int ans,tmp,cnt;
int dp[maxn],p[maxn];
char s[maxn];
void solve(){
    read(n);
    scanf("%s",s + 1);
    rep(i,1,n) a[i] = (s[i] & 1);
    a[n + 1] = 0;
    p[n + 1] = n + 1;
    dep(i,n,0){
        p[i] = p[i + 1];
        if(!a[i+1]) p[i] = i+1;
    }
    int i = 0,ans = n;
    dp[0] = p[0] - 1;
    while(dp[i] < n){
        i++;
        dep(j,i - 1,0) {
            dp[i] = max(dp[i],p[min(n + 1,dp[j] + (i - j + 1) * (i - j + 1) - 1)] - 1);
        }
    }
    printf("%d\n",i);
}
int main(){
    //ios::sync_with_stdio(0);cin.tie(0);
    int T=1;
    //read(T);
    while(T--) solve();
    return 0;
}
```