CodeForces 931E Game with String

题意：有一个字符串，可以选择从第K位开始，将[K，len(s)-1]的字符都移到前面去，现在给你一个首字母，你可以再选择一位进行观察，然后猜测这个K的值是多少，现在要求求出能猜对K的概率是多少。

题解：处理出每一个字母开头的第K位是什么字符，如果这个字符在这个字母中出现的次数为1，那么表示可以通过这一个位置来区分字符串，cnt++，不为一就说明不能区分，那就将上次的计数删除。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 typedef pair<int,int> pll;

 const int N = 1e5+;

 char str[N];

 int vis[][];

 int Max[N][];

 int main(){

     scanf("%s", str);

     int ans = ;

     int len = strlen(str);

     for(int to = ; to < len; to++){

         memset(vis,,sizeof(vis));

         int cnt = ;

         for(int i = ; i < len; i++){

             int p = str[i]-'a';

             int j = i+to;

             if(j >= len) j -= len;

             if(vis[p][str[j]-'a'] == ) Max[to][p]++, vis[p][str[j]-'a'] = ;

             else if(vis[p][str[j]-'a'] == ) {Max[to][p]--, vis[p][str[j]-'a'] = ;}

         }

     }

     for(int j = ; j < ; j++){

         int cnt = ;

         for(int i = ; i < len; i++){

             if(Max[i][j] > cnt) cnt = Max[i][j];

         }

         ans += cnt;

     }

     printf("%f",1.0*ans/len);

     return ;

 }

巴特西

CodeForces 931E Game with String

最新文章

热门文章