首页 > 其他 > 详细

hdu_5908_Abelian Period(暴力)

时间:2016-10-02 00:10:58      阅读:484      评论:0      收藏:0      [点我收藏+]

题目链接: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(暴力)

原文:http://www.cnblogs.com/bin-gege/p/5926483.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!