codeforces E. Game with String 概率

题意

这道题目的叙述不好理解：
给你一个字符串ss，小a和小b都知道。现在小b要把字符串的左边一段移动到最右边，生成一个新的字符串s′s′，小a只知道s′s′的首字母是什么，现在小a有权利任意选择新字符串的一个位置并掀开，然后根据这2个字符来猜测新的字符串是什么。
注意！当仅通过这2个字符不能唯一确定一个字符串的话，那么就算失败。
求小a的胜率。

---

样例解释

bbaabaabbb
这个应该输出0.1
因为当首字母是b时候，不管先开任何位置，都不能唯一确定新字符串。
当首字母为a的时候，当只有掀开第4个位置时候，如果被掀开的字母是a，那么可以确定新字符串是把原字符串左边2个b移动到右边形成的。
所以概率 =410∗14=0.1410∗14=0.1

---

题解：

定义 字符c，位置p的辨识度：所有首字母为c掀开位置为p的字符串，p位置出现次数为1的字母的个数。

• 分类将每个字母出现的位置存在各自对应的vector中。
• 然后我们便可枚举首字母是啥，记为c，记录mx[c][0]为···c为起始字符的可能字串，掀开某一个位置，所能得到的最大辨识度···
• 枚举要掀开的位置p，记录一个mx[c][p]变量，记录掀开当前位置所产生的辨识度。
• ans+=mx[c][0]nans+=mx[c][0]n

---

代码

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <unordered_map> using namespace std; const int maxn = 5555; char str[maxn]; vector<int> mp[27]; unordered_map<int,int> vis; int main(){scanf("%s",str);int n = strlen(str);for(int i = 0;i < n;++i){int c = str[i] - 'a';mp[c].push_back(i);}double ans = 0;for(int t = 0;t < 26;++t){if(mp[t].size() == 0) continue;int mx = 0;for(int i = 1;i < n;++i){int mx_tmp = 0;vis.clear();for(int j = 0;j < mp[t].size();++j){int now = str[(mp[t][j]+i)%n]-'a';vis[now] ++;}unordered_map<int,int>::iterator it;for(it = vis.begin();it != vis.end();++it){pair<int,int> p = *it;if(p.second == 1) {mx_tmp++;}}mx = max(mx,mx_tmp);}ans += double(mx)/double(n);}printf("%.10lf\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的codeforces E. Game with String 概率的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。