题解

思路

对任意模式 $p$，从左到右扫描：遇到 0 前进一位；遇到 1 时选中它、答案加一，并跳过当前位置及其后两位。这样得到的选中数恰为 $f(p)$。

直观上，一个被选中的 1 可以用长度不超过三的局部区间同时满足相邻位置；而任意连续三位中最左侧仍未覆盖的 1 都必须付出至少一个 1。由交换论证，可把最优解的第一次付费移到最左侧未处理的 1 而不劣，于是上述贪心最优。

做法

令 $g_i$ 表示所有以 $i$ 为左端点的子串的 $f$ 值之和（下标从 $0$ 开始）。

• 若 $s_i=0$，删除这个前导零不改变贪心选择，所以 $g_i=g_{i+1}$；
• 若 $s_i=1$，所有右端点 $r\ge i$ 都先选中 $i$，共有 $n-i$ 次贡献；余下决策从 $i+3$ 开始，所以 $g_i=(n-i)+g_{i+3}$。

越界位置的 $g$ 为零，最终答案为 $\sum_i g_i$。每组复杂度 $O(n)$，空间 $O(n)$，也可用常数滚动空间。

独立验证算法

预处理每个位置右侧第一个 1。对每个 1 位置 $p$，它在贪心链中的后继是 $p+3$ 及以后第一个 1。令 $h_p=(n-p)+h_{next(p+3)}$。每个左端点的贡献就是从其右侧第一个 1 开始的 $h$。这与上述按左端点递推的程序结构不同，可用于大规模交叉验证。

正确性证明

对固定左端点和右端点，贪心选中的每个位置都贡献一次。若首个未处理的 1 位于 $p$，任何可行方案必须在覆盖 $p$ 的局部多数证明中付出至少一个 1；把这次付费移动到 $p$ 后，至多影响 $p,p+1,p+2$，不会增加后缀所需付费。因此选中 $p$ 并从 $p+3$ 继续是最优的。递归应用即得贪心值为 $f$。

对所有右端点求和：当 $s_i=1$ 时，位置 $i$ 被所有 $n-i$ 个以 $i$ 开头的非空子串选中，剩余贡献与从 $i+3$ 开始完全相同；当 $s_i=0$ 时直接转到 $i+1$。故递推正确，累加全部左端点即得到题目要求的所有子串之和。

复杂度

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