Codeforces - 476B - Dreamoon and WiFi

Question

题目大意

给你两个字符串 a 、 b ， a 是发送方的字符串， b 是接收方的字符串， a 发送的字符串是确定的，但是 b 接收到的字符串有可能不确定，如果确定是 + ，则距离 +1 ，如果确定是 - ，则距离 -1 ，否则如果是 ? ，就不确定， +1 和 -1 的概率各为 0.5 ，要你判断在 a 确定的情况下， b 最终的距离和 a 相等的概率。

解析

枚举 b 出现的所有情况，看有多少种情况会和 a 的最终结果相同，因为数据范围小，所以可以枚举（暴搜即可)。

import java.io.*;
import java.util.*;

public class Main {

    static class Clazz{
        ArrayList<Double>res;
        double sum;
        double goal;
        String b;

        Clazz(String b){
            this.b = b;
            sum = 0;
            res = new ArrayList<>();
            goal = 0;
        }

        double computer(){
            dfs(0);
            double numerator = 0;         //分子
            int denominator = res.size(); //分母
            for(int i = 0; i < res.size(); i++){
                if(res.get(i) == goal)
                    numerator += 1;
            }
            return numerator/denominator;
        }

        void dfs(int index) {
            if(index == b.length()){
                res.add(sum);
                return;
            }
            char cur = b.charAt(index);
            if(cur == '+'){
                sum += 1;
                dfs(index+1);
                sum -= 1;
            }else if(cur == '-'){
                sum -= 1;
                dfs(index+1);
                sum += 1;
            }else {
                // 枚举两种情况
                sum += 1;
                dfs(index+1);
                sum -= 1;

                sum -= 1;
                dfs(index+1);
                sum += 1;
            }
        }
    }

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        String a = cin.next();
        String b = cin.next();

        Clazz clazz = new Clazz(b);
        for(int i = 0; i < a.length(); i++)
            clazz.goal += a.charAt(i) == '+' ? 1 : (-1);

        out.println(clazz.computer());
    }
}