首页 > 代码库 > HDU 5908 Abelian Period 可以直接用multiset
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 = 100000 + 20;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 = 1; i <= n; ++i) { scanf("%d", &a[i]); if (i >= 2 && a[i] != a[i - 1]) flag = false; } ans.insert(n); if (flag) { for (int i = 1; i <= n / 2; ++i) { if (n % i == 0) { ans.insert(i); } } } else { int begin = 1, end = -1; for (int i = 2; i <= n / 2; ++i) { if (n % i != 0) 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 + 1; flag = true; for (int j = 2 * i; j <= n; j += i) { bb.clear(); for (int k = j; k >= j - i + 1; --k) { bb.insert(a[k]); } if (aa != bb) { flag = false; break; } } if (!flag) continue; for (int j = i ; j <= n / 2; j += i) { if (n % j == 0) //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 0;}
#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 = 100000 + 20;int a[maxn];bool isok[maxn];int n;int cnt[maxn];int cmp[maxn];bool check(int val) { for (int i = 1; i <= val; ++i) { cnt[a[i]] = 0; } for (int i = 1; i <= val; ++i) { cnt[a[i]]++; } for (int i = 2 * val; i <= n; i += val) { for (int j = i; j >= i - val + 1; --j) { cmp[a[j]] = 0; } for (int j = i; j >= i - val + 1; --j) { cmp[a[j]]++; } for (int j = 1; j <= val; ++j) { if (cnt[a[j]] != cmp[a[j]]) return false; } } return true;}void work() { scanf("%d", &n); bool flag = true; memset(isok, 0, sizeof isok); isok[n] = 1; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); if (i >= 2 && a[i] != a[i - 1]) flag = false; } if (flag) { for (int i = 1; i <= n / 2; ++i) { if (n % i == 0) { isok[i] = 1; } } } else { for (int i = 2; i <= n / 2; ++i) { if (n % i != 0 || isok[i]) continue; if (check(i)) { for (int j = i; j <= n / 2; ++j) { if (n % j == 0) isok[i] = 1; } } } } flag = 0; for (int i = 1; i <= n; ++i) { if (isok[i]) { if (!flag) { printf("%d", i); flag = 1; } 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 0;}
HDU 5908 Abelian Period 可以直接用multiset
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。