首页 > 代码库 > HDU5908 Abelian Period 暴力
HDU5908 Abelian Period 暴力
题目大意:将一个数组分成长度为k的几个连续区间,如果每个区间内各个元素出现的次数相同,则称k为一个阿贝尔周期,从小到大打印所有阿贝尔周期,数据间加空格。
题目思路:map+暴力
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<stdio.h> 6 #include<stdlib.h> 7 #include<queue> 8 #include<math.h> 9 #include<map>10 #define INF 0x3f3f3f3f11 #define MAX 10000512 #define Temp 100000000013 14 using namespace std;15 16 int a[MAX],vis[MAX];17 18 int check(int k,int n)19 {20 map<int ,int> map1,map2;21 for(int i=1; i<=k; i++)22 map1[a[i]]++;23 for(int i=k+1; i<=n-k+1; i+=k)24 {25 map2.clear();26 for(int j=0; j<k; j++)27 {28 int num=a[i+j];29 map2[num]++;30 }31 if(map1!=map2)32 return 0;33 }34 return 1;35 }36 37 int main()38 {39 int T,n,ans;40 scanf("%d",&T);41 while(T--)42 {43 memset(vis,0,sizeof(vis));44 scanf("%d",&n);45 for(int i=1; i<=n; i++)46 {47 scanf("%d",&a[i]);48 }49 50 for(int i=1; i<=n/2; i++)51 {52 if(!vis[i] && n%i==0)//如果2成立,那么如果2的倍数m能被n整除,则m也成立53 {54 if(check(i,n))55 {56 for(int j=i; j<=n/2; j+=i)57 {58 if(j!=n && n%j==0)59 {60 vis[j]=1;61 }62 }63 }64 }65 }66 for(int i=1; i<n; i++)67 {68 if(vis[i])69 printf("%d ",i);70 }71 printf("%d\n",n);72 }73 return 0;74 }
HDU5908 Abelian Period 暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。