首页 > 代码库 > hdu_5908_Abelian Period(暴力)

hdu_5908_Abelian Period(暴力)

题目链接:hdu_5908_Abelian Period

题意:

给你n个数字,让你找出所有的k,使得把这n个数字分为k分,并且每份的数字种类和个数必须相同

题解:

枚举k,首先k必须是n的约数,然后就能算出每个数字应该出现多少次,O(n)检验即可。

技术分享
 1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4  5 const int N=1e5+7; 6 int t,n,a[N]; 7 map<int,int>A,B; 8 map<int,int>::iterator it; 9 int ans[N],ed;10 11 int main(){12     scanf("%d",&t);13     while(t--)14     {15         scanf("%d",&n),ed=0;16         F(i,1,n)scanf("%d",a+i);17         int be=1;18         while(be<=n)19         {20             while(be<n&&n%be!=0)be++;21             if(n%be==0)22             {23                 A.clear();24                 F(i,1,be)A[a[i]]++;25                 int en=n/be,fg=0;26                 F(i,2,en)27                 {28                     B=A;29                     int s=(i-1)*be+1,t=s+be-1;30                     F(j,s,t)B[a[j]]--;31                     for(it=B.begin();it!=B.end();it++)32                     {33                         if(it->second!=0){fg=1;break;}34                     }35                     if(fg)break;36                 }37                 if(fg==0)ans[++ed]=be;38             }39             be++;40         }41         F(i,1,ed)printf("%d%c",ans[i],i==ed?\n: );42     }43     return 0;44 }
View Code

 

hdu_5908_Abelian Period(暴力)