首页 > 代码库 > Abelian Period
Abelian Period
Abelian Period
Accepts: 288
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/131072 K (Java/Others)
问题描述
设SSS是一个数字串，定义函数occ(S,x)occ(S,x)occ(S,x)表示SSS中数字xxx的出现次数。例如：S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1S=(1,2,2,1,3),occ(S,1)=2,occ(S,2)=2,occ(S,3)=1。如果对于任意的iii，都有occ(u,i)=occ(w,i)occ(u,i)=occ(w,i)occ(u,i)=occ(w,i)，那么我们认为数字串uuu和www匹配。例如：(1,2,2,1,3)≈(1,3,2,1,2)(1,2,2,1,3)\approx(1,3,2,1,2)(1,2,2,1,3)≈(1,3,2,1,2)。对于一个数字串SSS和一个正整数kkk，如果SSS可以分成若干个长度为kkk的连续子串，且这些子串两两匹配，那么我们称kkk是串SSS的一个完全阿贝尔周期。给定一个数字串SSS，请找出它所有的完全阿贝尔周期。输入描述
输入的第一行包含一个正整数T(1≤T≤10)T(1\leq T\leq10)T(1≤T≤10)，表示测试数据的组数。对于每组数据，第一行包含一个正整数n(n≤100000)n(n\leq 100000)n(n≤100000)，表示数字串的长度。第二行包含nnn个正整数S1,S2,S3,...,Sn(1≤Si≤n)S_1,S_2,S_3,...,S_n(1\leq S_i\leq n)S?1??,S?2??,S?3??,...,S?n??(1≤S?i??≤n)，表示这个数字串。输出描述
对于每组数据，输出一行若干个整数，从小到大输出所有合法的kkk。输入样例
265 4 4 4 5 486 5 6 5 6 5 5 6
输出样例
3 62 4 8
思路：枚举n的因子，然后我们去检验这个是否符合就可以了；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<set> 7 #include<math.h> 8 #include<map> 9 using namespace std; 10 typedef long long LL; 11 int ans[100005]; 12 int cnt[100005]; 13 int cnt2[100005]; 14 int tx[100005]; 15 int ask[100005]; 16 int main(void) 17 { 18 int T; 19 scanf("%d",&T); 20 while(T--) 21 { 22 int n; 23 scanf("%d",&n); 24 int i,j; 25 for(i = 1; i <= n; i++) 26 { 27 scanf("%d",&ans[i]); 28 } 29 int cn = 0; 30 for(i = 1; i <= sqrt(1.0*n); i++) 31 { 32 int v = 0; 33 if(n%i==0) 34 { 35 int k = n/i; 36 for(j = 1; j <= i; j++) 37 { 38 if(!cnt[ans[j]]) 39 { 40 tx[v++] = ans[j]; 41 } 42 cnt[ans[j]]++; 43 } 44 bool flag = false ; 45 int x = i+1; 46 while(true) 47 { 48 for(j = x; j <= i+x-1&& j<=n; j++) 49 { 50 if(!cnt[ans[j]]) 51 { 52 flag = true; 53 break; 54 } 55 cnt2[ans[j]]++; 56 } 57 x = j; 58 for(j = 0; j < v; j++) 59 { 60 if(cnt[tx[j]]!=cnt2[tx[j]]) 61 { 62 flag = true; 63 } 64 cnt2[tx[j]] = 0; 65 } 66 if(flag || x == n+1) 67 { 68 break; 69 } 70 } 71 for(j = 0; j < v; j++) 72 { 73 cnt[tx[j]] = 0; 74 } 75 if(!flag)ask[cn++] = i; 76 if(i!=n/i) 77 { 78 v = 0; 79 for(j = 1; j <= k; j++) 80 { 81 if(!cnt[ans[j]]) 82 { 83 tx[v++] = ans[j]; 84 } 85 cnt[ans[j]]++; 86 } 87 bool flag = false ; 88 int x = k+1; 89 while(true) 90 { 91 for(j = x; j <= k+x-1&& j<=n; j++) 92 { 93 if(!cnt[ans[j]]) 94 { 95 flag = true; 96 break; 97 } 98 cnt2[ans[j]]++; 99 }100 x = j;101 for(j = 0; j < v; j++)102 {103 if(cnt[tx[j]]!=cnt2[tx[j]])104 {105 flag = true;106 }107 cnt2[tx[j]] = 0;108 }109 if(flag || x == n+1)110 {111 break;112 }113 }114 for(j = 0; j < v; j++)115 {116 cnt[tx[j]] = 0;117 }118 if(!flag)ask[cn++] = k;119 }120 }121 }122 ask[cn++] = n;123 sort(ask,ask+cn);124 printf("%d",ask[0]);125 for(i = 1; i < cn; i++)126 {127 printf(" %d",ask[i]);128 }129 printf("\n");130 }131 return 0;132 }
Abelian Period
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。