CF1673B 题解

MatrixGroup · 2022-05-06 19:25:56 · 题解

• 解法

最妙 Div2 B。

引理：符合条件的字符串，令其不同字母数量是 k，那么 s_0,s_1,\cdots,s_{k-1} 两两不同，并且 s_i=s_{i\bmod k}。（0 为初始下标）

证明：

如果 s_i=s_j(i\neq j,0\le i,j<k)，那么一定存在在 s 中出现但不在前 k 个出现的字符 c，那么 (s_i,c) 不符合。

如果 \exists i\text{ s.t. }s_i\neq s_{i\bmod k}，那么对于 i-k+1,i-k+2,\cdots,i 进行论证即可。

于是判断一下就行。复杂度 O(t\times(n+|\alpha|^2))。

• 代码

代码是以 1 作为初始下标的。

#include <bits/stdc++.h>
#define rep1(i,n) for(int i=1,_##i##__end=(n);i<=_##i##__end;++i)
using namespace std;
int t,l,e;
char s[200005];
bool ap[28]; 
void Q()
{
    scanf("%s",s+1);e=0;
    l=strlen(s+1);
    memset(ap,0,sizeof(ap));
    rep1(i,l) ap[s[i]&31]=1;
    rep1(i,26) if(ap[i]) ++e;
    rep1(i,l)
    {
        if(s[i]!=s[(i-1)%e+1])
        {
            puts("no");
            return ;
        }
    }
    rep1(i,e) rep1(j,e) if(s[i]==s[j]&&i!=j)
    {
        puts("No");return ;
    }
    puts("yes");
}
int main()
{
    scanf("%d",&t);
    while(t--)
    Q();
    return 0;
}