欢乐赛T6题解

解题思路

可以看到题目要求仅仅是翻转一个"1"为"0"并求结果最小值，我们很容易想到枚举，不要被结果的数据范围唬住，乘法是这样的……我们建立一个vector数组，用于储存所有"1"的位置，然后逐一尝试取最小值即可。

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

int main(){
    long long min_=9e18;    //建立min_变量存储最小结果
    string n;
    cin >> n;
    vector<int> pos;
    pos.push_back(-1);    //为了接下来的计算逻辑正确，先假设字符串的"-1"位置有一个不可翻转的"1"，第14行同理
    //存入字符串中所有1的位置
    for(int i=0;i<n.size();++i)
        if(n[i]=='1')
            pos.push_back(i);
    pos.push_back(n.size());
    for(int i=1;i<pos.size()-1;++i){    //遍历除了我们假设的1外的所有1
        long long sum=1;    //计算乘积和，千万不要开成0了，计算时注意特判相连"1"（中间无"0"会导致乘0，结果白算）
        for(int j=1;j<pos.size();++j){
     		if(j-1==i&&pos[j]-pos[j-2]-1!=0) sum*=pos[j]-pos[j-2]-1;
            else if(j!=i&&pos[j]-pos[j-1]-1!=0) sum*=pos[j]-pos[j-1]-1;
    	}
        min_ = min(sum, min_);    //取最小值
    }
    cout << min_;
}