HDU 5908 Abelian Period 可以直接用multiset

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://acm.hdu.edu.cn/showproblem.php?pid=5908

要求把数组分成k组使得每组中的元素出现次数相同

就是分成k个集合，那么直接用multiset判定就可以

有重载相等运算符的

我被坑了的就是，

对于2个元素一个集合的可以，那么，4,6,8这样分集合也是可以的。

这个很容易理解

但是，你也要能平均分才行啊

就是10的2可以，但是4是一定不可以得。不能平均分

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn];
multiset<int>aa;
multiset<int>bb;
set<int>ans;
void work() {
aa.clear();
// bb.clear();
ans.clear();
int n;
scanf("%d", &n);
bool flag = true;
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if (i >= && a[i] != a[i - ]) flag = false;
}
ans.insert(n);
if (flag) {
for (int i = ; i <= n / ; ++i) {
if (n % i == ) {
ans.insert(i);
}
}
} else {
int begin = , end = -;
for (int i = ; i <= n / ; ++i) {
if (n % i != ) continue;
if (ans.find(i) != ans.end()) continue;
// aa.clear();
end = i;
// cout << begin << " " << end << " " << i << endl;
for (int j = begin; j <= end; ++j) {
aa.insert(a[j]);
}
begin = end + ;
flag = true;
for (int j = * i; j <= n; j += i) {
bb.clear();
for (int k = j; k >= j - i + ; --k) {
bb.insert(a[k]);
}
if (aa != bb) {
flag = false;
break;
}
}
if (!flag) continue;
for (int j = i ; j <= n / ; j += i) {
if (n % j == ) //10的2不代表10的4
ans.insert(j);
}
}
}
// show();
set<int> :: iterator it = ans.begin();
printf("%d", *it);
it++;
for (; it != ans.end(); ++it) {
printf(" %d", *it);
}
printf("\n");
return;
}int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while(t--) work();
return ;
}

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn];
bool isok[maxn];
int n;
int cnt[maxn];
int cmp[maxn];
bool check(int val) {
for (int i = ; i <= val; ++i) {
cnt[a[i]] = ;
}
for (int i = ; i <= val; ++i) {
cnt[a[i]]++;
}
for (int i = * val; i <= n; i += val) {
for (int j = i; j >= i - val + ; --j) {
cmp[a[j]] = ;
}
for (int j = i; j >= i - val + ; --j) {
cmp[a[j]]++;
}
for (int j = ; j <= val; ++j) {
if (cnt[a[j]] != cmp[a[j]]) return false;
}
}
return true;
}
void work() {
scanf("%d", &n);
bool flag = true;
memset(isok, , sizeof isok);
isok[n] = ;
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if (i >= && a[i] != a[i - ]) flag = false;
}
if (flag) {
for (int i = ; i <= n / ; ++i) {
if (n % i == ) {
isok[i] = ;
}
}
} else {
for (int i = ; i <= n / ; ++i) {
if (n % i != || isok[i]) continue;
if (check(i)) {
for (int j = i; j <= n / ; ++j) {
if (n % j == ) isok[i] = ;
}
}
}
}
flag = ;
for (int i = ; i <= n; ++i) {
if (isok[i]) {
if (!flag) {
printf("%d", i);
flag = ;
} else {
printf(" %d", i);
}
}
}
printf("\n");
return;
}int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while(t--) work();
return ;
}