codeforces 930b//Game with String// Codeforces Round #468 (Div. 1)
2024-09-20 00:38:10
题意:一个串,右循环移位后,告诉你第一个字母,还能告诉你一个,问你能确定移位后的串的概率。
用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 ;
}
最新文章
- Nginx重写
- sum data
- Javascript备忘复习笔记2
- linux笔记一
- Linux之date
- [eclipse]改项目名称后tomcat连接问题解决方法
- Spring Mail
- BZOJ 2228 礼物(gift)(最大子长方体)
- 关于strong、copy、weak、assign的常规用法
- Spark菜鸟学习营Day6 分布式代码运行调试
- sharepoint 2010 在aspx 写lambda 时错误
- Powershell 定义文本
- MyEclipse 引用其他项目及其jar包
- 关于Opengl投影矩阵
- Tomcat开启本地库(Apache Tomcat Native Library)支持
- 【转】.Net Core中的Api版本控制
- MySQL—函数大全
- Oracle中使用PL/SQL如何定义参数、参数赋值、输出参数和 if 判断
- JS 对话框 语法
- 【转】MATLAB conv2函数的理解
热门文章
- FastReport问题整理(转)
- VS2010的快捷键;VS2012变化的快捷键
- Zookeeper学习记录(二):使用以及配置
- vm #set、日期截取、#foreach&;#if
- CentOS7安装redis5.0
- Java的各种加密算法
- ESOURCE_LOCKED - cannot obtain exclusive access to locked queue &#39;2484_0_00163&#39;
- linux虚拟机中安装vm_tool的方法及用处
- Android移植学习笔记
- Facebook广告API系列 Business Manager