本文最后更新于：4 years ago
题目链接:点击跳转
Problem Description
Input
Output
For each test case, output one line containing ‘’Yes’’ or ‘’No’’ (without quotes).
Sample Input
1
2
3
4
5
6
7
8
9
10
11
12
13
| 6
1
a
2
aa
3
aab
4
abba
6
abcbcc
8
aaaaaaaa
|
Sample Output
题目大意:求给出的字符串的长度的因子(大于1的),以该因子拆分原串,是否每一串都可以是其他串的循环同构
解题思路:这里用string的substr和find函数来解决的,当然,string的封装方法的效率都相当低,所以需要维护一个前缀和(O(n*26))来优化,因为如果是循环同构,那么每个字符的数量一定是相等的,如果都相等,才需要去比较。找到一个k满足题意就可以退出输出Yes,没有找到则输出No。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
inline void FAST_IO() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int n;
string s;
int fac[50005],tot,sum[26][5000005];
inline void getFac(){
tot=0;
for(int i=2;i*i<=n;i++){
if(n%i==0)fac[tot++]=i;
if(i*i!=n)fac[tot++]=n/i;
}
fac[tot++]=n;
}
signed main(){
FAST_IO();
int Case;
cin>>Case;
while(Case--){
cin>>n>>s;
if(n==1){
cout<<"No"<<endl;
continue;
}
for(int i=0;i<26;i++)sum[i][0]=0;
sum[s[0]-'a'][0]=1;
for(int i=1;i<n;i++){
for(int j=0;j<26;j++){
sum[j][i]=sum[j][i-1];
}
sum[s[i]-'a'][i]++;
}
getFac();
bool f=false;
for(int i=0;i<tot;i++){
f=true;
int k=n/fac[i];
for(int j=k;j<n;j+=k){
if(!f)break;
for(int l=0;l<26;l++){
if(sum[l][j+k-1]-sum[l][j-1]!=sum[l][k-1]){
f=false;
break;
}
}
}
if(!f)continue;
string str=s.substr(0,k);
str+=str;
for(int j=k;j<n;j+=k){
string str1=s.substr(j,k);
if(str.find(str1)==-1){
f=false;
break;
}
}
if(f)break;
}
if(f){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}
|