CodeForces 931E Game with String

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+7;
typedef pair<int,int> pll;
const int N = 1e5+5;
char str[N];
int vis[26][26];
int Max[N][26];
int main(){
    scanf("%s", str);
    int ans = 0;
    int len = strlen(str);
    for(int to = 1; to < len; to++){
        memset(vis,0,sizeof(vis));
        int cnt = 0;
        for(int i = 0; i < len; i++){
            int p = str[i]-'a';
            int j = i+to;
            if(j >= len) j -= len;
            if(vis[p][str[j]-'a'] == 0) Max[to][p]++, vis[p][str[j]-'a'] = 1;
            else if(vis[p][str[j]-'a'] == 1) {Max[to][p]--, vis[p][str[j]-'a'] = 2;}
        }
    }
    for(int j = 0; j < 26; j++){
        int cnt = 0;
        for(int i = 0; i < len; i++){
            if(Max[i][j] > cnt) cnt = Max[i][j];
        }
        ans += cnt;
    }
    printf("%f",1.0*ans/len);
    return 0;
}