题解：ROI 2019 Day2 T1 美丽的01串（Гирлянда）

题目核心分析

美丽的01串定义：可表示为 A1A1A…1A，其中：

• A 是含等量0的子串（可为空）；
• 中间至少有1个1。

等价于：所有1的左右两侧（到相邻1或串首尾）的0数量完全相同。

我们需要从原串中删除尽量少的字符，得到最长的美丽串。

核心思路

1. 提取原串中的1位置：设原串中1的位置为 pos[0], pos[1], ..., pos[k-1]（k是1的总数）。
2. 枚举A的0数量x：x是每个A包含的0的个数（可为0）。
3. 验证x的可行性：对每个x，检查能否在原串中为每个1匹配左右各x个0，最终统计最长长度。

关键观察

• 若选择t个1（t ≥1），则美丽串的长度为 t*1 + (t+1)*x（t个1 + t+1个A）。
• 要最大化长度，需优先选择较多的1 + 较大的x。

具体实现步骤

步骤1：预处理1的位置

遍历原串，记录所有1的索引到数组pos中。若k=0，直接输出空（但题目保证原串是装饰串，至少有1个1）。

步骤2：枚举x的可能值

x的最大可能值为 原串中0的总数除以(t+1)（t是选择的1的数量），但更高效的方式是：

• 对每个1，预处理其左侧和右侧的0的数量，枚举所有可能的x候选（从原串中相邻1之间的0数量中提取）。

步骤3：验证x并计算最长长度

对每个候选x：

1. 检查首尾1的外侧：
   • 第一个1的左侧至少有x个0；
   • 最后一个1的右侧至少有x个0。
2. 检查相邻1之间的0数量：每对相邻1之间至少有2x个0（左右各x个）。
3. 若满足条件，长度为 k*1 + (k+1)*x（选择所有k个1）；若不满足，尝试减少1的数量。

优化策略

• 枚举x的候选集：仅枚举原串中“相邻1之间的0数量的约数” + “首尾1外侧的0数量”，减少枚举量。
• 优先大x和多1：先尝试大x和多1的组合，一旦找到可行解，可提前终止部分枚举。

C++ 代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    vector<int> pos;  // 原串中所有'1'的位置
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') pos.push_back(i);
    }
    int k = pos.size();
    if (k == 0) { cout << 0 << "\n"; return 0; }  // 题目保证至少有1个'1'

    // 预处理相邻1之间的0数量，以及首尾1的外侧0数量
    vector<long long> gaps;
    gaps.push_back(pos[0]);  // 第一个1左侧的0数量
    for (int i = 1; i < k; ++i) {
        gaps.push_back(pos[i] - pos[i-1] - 1);  // 相邻1之间的0数量
    }
    gaps.push_back(n - 1 - pos.back());  // 最后一个1右侧的0数量

    long long max_len = 1;  // 至少选1个'1'
    string best_str = "1";

    // 枚举x的可能值：从大到小，优先大x
    for (long long x = *max_element(gaps.begin(), gaps.end()); x >= 0; --x) {
        bool valid = true;
        for (auto g : gaps) {
            if (g < x) { valid = false; break; }
        }
        if (valid) {
            long long len = k + (k + 1) * x;
            if (len > max_len) {
                max_len = len;
                // 构造结果串
                string res;
                res.append(x, '0');
                for (int i = 0; i < k; ++i) {
                    res += '1';
                    res.append(x, '0');
                }
                best_str = res;
            }
            break;  // x最大，无需再枚举更小的x
        }
    }

    // 处理x=0的情况（所有1直接相连）
    if (k > max_len) {
        max_len = k;
        best_str = string(k, '1');
    }

    cout << max_len << "\n" << best_str << "\n";
    return 0;
}

代码解释

1. 预处理1的位置和间隙：

   • pos存储所有1的索引；
   • gaps存储“第一个1左侧0数、相邻1之间0数、最后一个1右侧0数”。

2. 枚举x：

   • 从最大可能的x（gaps中的最大值）开始枚举，若x满足所有间隙≥x，则构造对应的美丽串。

3. 构造结果：

   • 若x可行，构造串为 x个0 + 1 + x个0 + 1 + ... + x个0；
   • 特殊处理x=0的情况（所有1直接相连）。

复杂度分析

• 时间复杂度：$O(n + k)$（预处理） + $O(M)$（枚举x，M是gaps的最大值，实际中远小于n）。
• 空间复杂度：$O(n)$（存储pos、gaps和结果串）。

注意事项

• 当k=1时，美丽串为 x个0 + 1 + x个0，x取第一个1左侧和右侧0数的较小值；
• 当x=0时，美丽串就是所有1直接相连，长度为k；
• 需处理原串中1数量较少的情况（如样例2中k=3，x=0，长度为3）。