題目鏈接：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[i] == '+') 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[i] == '?') 49 unknown++; 50 else if (str2[i] == '+') 51 known += 1; 52 else if (str2[i] == '-') 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 }

?

轉載于:https://www.cnblogs.com/windysai/p/4023090.html

總結

以上是生活随笔為你收集整理的codeforces 476B.Dreamoon and WiFi 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。