codeforces 476B.Dreamoon and WiFi 解题报告

gacvd

　　题目链接：http://codeforces.com/problemset/problem/476/B
　　题目意思：给出两个字符串str1, str2，其中，str1 只由 '+' 和 '-' 组成，而str2 由 '+'，'-'和'?'组成。初始点在原点0的位置，经过 str1 的变换最终会达到某一个位置，‘+'表示向右移动一个单位（+1），'-'即-1。str2 中 '?'的部分可以填入'+'，'-'其中一个符号。问能填充 '?' 的所有情况中，使得使用 str2 所有的操作，能到达   经过 str1 所有操作后到达的最终位置   的概率是多少。（额....比较拗口= =，俺的...表达能力果然不敢恭维- -!）
　　首先，算出经过 str1 所有的操作后最终到达的位置，这个明显是确定的啦，没有 '?' 嘛。接着算出 str2 除 '?' 外到达的位置，剩下用深搜来填入 '?'，统计等于最终位置的种数。最后用  这个种数 / 问号能填入的所有情况，就是答案啦！！！
　　还有一些特判点，假如str2 没有问号，概率只有两种情况：1 或者 0。其他就要dfs算啦～～
　　粗心过头，wa了两次： 无用%.12lf（又到考眼力的时候了= =） 还有调试 cnt 不记得注释了= =......
　　



1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 using namespace std;
7
8 const int maxn = 10 + 5;
9 char str1[maxn], str2[maxn];
10 int unknown, origin;
11 double cnt, fenmu;
12
13 void dfs(int c, int cur)
14 {
15     if (c == unknown)
16     {
17         if (cur == origin)
18             cnt++;
19         return;
20     }
21     dfs(c+1, cur+1);
22     dfs(c+1, cur-1);
23 }
24
25 int main()
26 {
27     #ifndef ONLINE_JUDGE
28         freopen("input.txt", "r", stdin);
29     #endif
30
31     while (scanf("%s%s", str1, str2) != EOF)
32     {
33         int len = strlen(str1);
34         origin = 0;
35
36         for (int i = 0; i < len; i++)
37         {
38             if (str1 == '+')
39                 origin += 1;
40             else
41                 origin -= 1;
42         }
43
44         int known = 0;
45         unknown = 0;
46         for (int i = 0; i < len; i++)
47         {
48             if (str2 == '?')
49                 unknown++;
50             else if (str2 == '+')
51                 known += 1;
52             else if (str2 == '-')
53                 known -= 1;
54         }
55         if (!unknown)
56         {
57             if (known != origin)
58                 printf("0.000000000000\n");
59             else
60                 printf("1.000000000000\n");
61         }
62         else
63         {
64             cnt = 0;
65             dfs(0, known);
66             fenmu = 1;
67             for (int i = 1; i <= unknown; i++)
68                 fenmu *= 2;
69             printf("%.12lf\n", (double)cnt/(double)fenmu);
70         }
71     }
72     return 0;
73 }