首页 > 代码库 > HDU5908 Abelian Period 暴力

HDU5908 Abelian Period 暴力

2024-08-15 11:57:47   221人阅读

题目大意：将一个数组分成长度为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 }
View Code

 

HDU5908 Abelian Period 暴力


联系
我们