欢乐赛#54 T6 题解 100% AC

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;  // 输入01字符串
    int n = s.size();  // 获取字符串长度
    long long minx = LLONG_MAX;  // 初始化最小乘积为最大长整型值

    // 遍历每个字符寻找可翻转的'1'
    for(int i = 0; i < n; i++) {
        if(s[i] == '1') {  // 发现可翻转位
            s[i] = '0';  // 临时翻转1→0
            
            // 计算当前翻转后的0串乘积
            long long x = 1;  // 乘积初始值
            int cnt = 0;     // 连续0计数器
            
            // 扫描整个字符串统计连续0段
            for(char c : s) {
                if(c == '0') {
                    cnt++;  // 连续0计数增加
                }
                else if(cnt > 0) {  // 遇到1且之前有连续0
                    x *= cnt;      // 将连续0段长乘入结果
                    cnt = 0;       // 重置计数器
                }
            }
            
            // 处理末尾可能存在的连续0
            if(cnt > 0) x *= cnt;
            
            // 更新最小乘积
            if(x < minx) minx = x;
            
            s[i] = '1';  // 恢复原始字符（回溯）
        }
    }
    
    cout << minx;  // 输出最小乘积
    return 0;
}

算法核心解析

1. 问题转化：将"翻转1个1→0后求连续0段长度乘积的最小值"转化为$O(n^2)$的暴力搜索问题
2. 关键步骤：
   • 枚举翻转位：遍历每个'1'位置进行临时翻转（第8-10行）
   • 乘积计算：用双指针法统计连续0段长度（第13-22行）
   • 极值维护：通过minx变量动态保持最小乘积（第25行）
3. 数学原理：乘积最小化需要尽可能使各段长度均衡（根据算术-几何平均不等式）

复杂度分析

• 时间复杂度：$O(n^2)$
  • 外层循环：$O(n)$次遍历
  • 内层扫描：每次$O(n)$的字符串遍历
• 空间复杂度：$O(1)$（仅用常数个辅助变量）

示例演算

以输入0000100010000001为例：

1. 翻转第5个字符'1'后得到0000000010000001：
   • 连续0段：8个和6个 → 乘积48
2. 翻转第9个字符'1'后得到0000100000000001：
   • 连续0段：4个和10个 → 乘积40（当前最小值）
3. 最终输出最小乘积40

边界情况处理

1. 全1字符串：题目保证至少存在1个0，无需处理
2. 超大结果：使用long long类型存储乘积（保证$≤9×10^{18}$）
3. 连续0段识别：通过else if(cnt>0)确保只有有效段被计算

该实现严格满足题目所有约束条件，并通过临时翻转→计算→恢复的"试探性"处理保证原始数据不被破坏。