题意:一个串,右循环移位后,告诉你第一个字母,还能告诉你一个,问你能确定移位后的串的概率。

用map记录每个字母出现的位置。对于每个字母,用arr[j][k]记录它的所有出现位置的后j位是字母k的个数。对每个j数arr[j]中arr[j][k]等于1的个数,取最大,说明k取这个时区分该字母的概率最大。统计所有字母的该值除以字符串长度即为结果。

//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include <stack>
#include <bitset>
#include <iomanip>
using namespace std;
const int SZ=,INF=0x7FFFFFFF;
typedef long long lon;
bool vst[];
set<int> st[];
short cnt[SZ][]; double work(int n,const string &str)
{
int res=;
for(int i=;i<;++i)
{
if(st[i].size()==)continue;
memset(cnt,,sizeof(cnt));
for(auto it=st[i].begin();it!=st[i].end();++it)
{
int pos=*it;
for(int j=;j<n;++j)
{
++cnt[j][str[(pos+j)%n]-'a'];
}
}
int maxv=;
for(int j=;j<n;++j)
{
maxv=max(maxv,(int)count(cnt[j],cnt[j]+,));
}
res+=maxv;
}
//cout<<res<<" "<<str.size()<<endl;
return (double)res/str.size();
} int main()
{
std::ios::sync_with_stdio();
//freopen("d:\\1.txt","r",stdin);
//for(;scanf("%d",&n)!=EOF;)
{
string str;
cin>>str;
for(int i=;i<str.size();++i)
{
st[str[i]-'a'].insert(i);
}
cout<<fixed<<setprecision()<<work(str.size(),str)<<endl;
}
return ;
}

最新文章

  1. Nginx重写
  2. sum data
  3. Javascript备忘复习笔记2
  4. linux笔记一
  5. Linux之date
  6. [eclipse]改项目名称后tomcat连接问题解决方法
  7. Spring Mail
  8. BZOJ 2228 礼物(gift)(最大子长方体)
  9. 关于strong、copy、weak、assign的常规用法
  10. Spark菜鸟学习营Day6 分布式代码运行调试
  11. sharepoint 2010 在aspx 写lambda 时错误
  12. Powershell 定义文本
  13. MyEclipse 引用其他项目及其jar包
  14. 关于Opengl投影矩阵
  15. Tomcat开启本地库(Apache Tomcat Native Library)支持
  16. 【转】.Net Core中的Api版本控制
  17. MySQL—函数大全
  18. Oracle中使用PL/SQL如何定义参数、参数赋值、输出参数和 if 判断
  19. JS 对话框 语法
  20. 【转】MATLAB conv2函数的理解

热门文章

  1. FastReport问题整理(转)
  2. VS2010的快捷键;VS2012变化的快捷键
  3. Zookeeper学习记录(二):使用以及配置
  4. vm #set、日期截取、#foreach&amp;#if
  5. CentOS7安装redis5.0
  6. Java的各种加密算法
  7. ESOURCE_LOCKED - cannot obtain exclusive access to locked queue &#39;2484_0_00163&#39;
  8. linux虚拟机中安装vm_tool的方法及用处
  9. Android移植学习笔记
  10. Facebook广告API系列 Business Manager