首页 > 代码库 > 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 }
hdu_5908_Abelian Period(暴力)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。