题解 CF1553C Penalty

Doubeecat · 2021-07-23 22:16:09 · 题解

CF1553C

有两个球队在比赛，比赛的情况可以视为一个长度为 10 的字符串。

一场比赛结束当且仅当某一队的当前胜场已经超过了另一队的最大可能胜场（即另一球队接下来所有比赛都赢的情况）

现在给出你 T 场比赛的情况，1 表示该队进球了，0 表示该队没有进球，? 表示该队进或没进都可以。两个球队交替踢球，求比赛最早于哪个回合结束。

T \leq 1000

<!-- more -->

解题思路：

暴搜。

观察到这个题的 |s| 非常小，我们实际上可以直接暴搜，时间复杂度仅为 2^{cntof?} \leq 2^{10} = 1024

实现上只需要一个搜索，枚举每一位 ? 的情况，稍微处理一下注意细节即可。

时间复杂度 O(1024T)

代码：

void dfs(int x) {
    //cout << x <<  " ";
    if (x >= 11) return;
    if (x &1) {
        int res = (10-x+1)/2;
        if(tota + res <totb||tota > totb+ res){
            ans = min(ans,x-1);
            return;
        }
        if (a[x] >= 0) {
            if (a[x] == 1) ++tota;
            dfs(x+1);
            if (a[x] == 1) {--tota;}
        }
        else {
            a[x] = 1;
            ++tota;
            dfs(x+1);
            --tota;
            a[x] = 0;
            dfs(x+1);
            a[x] = -1;
        }
    } else {
        int res = (10 - x + 1) / 2;
        if(tota + res < totb || tota > totb+res +1){
            ans = min(ans,x-1);
            return;
        }
        if (a[x] >= 0) {
            if (a[x] == 1) ++totb;
            dfs(x+1);
            if (a[x] == 1) --totb;
        }
        else {
            a[x] = 1;++totb;
            dfs(x+1);--totb;
            a[x] = 0;
            dfs(x+1);
            a[x] = -1;
        }
    }
}

void solve() {
    cin >> s;ans = 10;
    for (int i = 1;i <= 10;++i) (a[i] = (s[i-1] == '0' || s[i-1] == '1') ? (s[i-1] - '0') : -1);
    //for (int i = 0;i < 10;++i) printf("%d ",a[i]);
    dfs(1);
    printf("%d\n",ans);
}