HihoCoder 1246：王胖浩与环

#1246 : 王胖浩与环

时间限制:6000ms 单点时限:1000ms 内存限制:256MB

描述

王胖浩有一个环，环上有n个正整数。他有特殊的能力，能将环切成k段，每段包含一个或者多个数字。

对于一个切分方案，王胖浩将以如下方式计算优美程度，

首先对于每一段，求出他们的数字和。然后对于每段的和，求出他们的最大公约数，即为优美程度。

他想通过合理地使用他的特殊能力，使得切分方案的优美程度最大。

输入

第一行一个整数n，表示环上的数字个数。

接下来一行包含n个正整数，第i个数ai表示环上第i个数。

数据范围:

1<=n<=2000,1<=ai<=5*107

输出

输出n行，第i行表示切成i段时的最大优美程度。

样例输入

7 2 3 3 3 3 3 3

样例输出

20 5 2 2 1 1 1

官方题解：首先d一定是所有数总和的约数，这样的数并不多。接着判断一个d是否可能为k段和的约数，只要将前缀和按模d分类即可，看相同的个数是否大于等于k。

又学到了新姿势。。。一堆数的公共约数，实际上一定在 这堆数和 的约数里面找。因为很简单的道理，a%x=0 b%x=0，(a+b)是肯定%x=0的。

然后就是将约数从大到小排序，看它们在前缀和里面出现的次数，这里的做法也感觉太亮了。果然自己做题还是太少了啊。。。

代码：

#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #pragma warning(disable:4996) using namespace std;typedef long long ll;ll n; ll val[2005]; ll num[5000]; ll ans[2005];int main() {//freopen("i.txt","r",stdin);//freopen("o.txt","w",stdout);ll i, j, nu;scanf("%lld", &n);val[0] = 0;for (i = 1; i <= n; i++){scanf("%lld", val + i);val[i] = val[i - 1] + val[i];}sort(val + 1, val + n + 1);nu = 0;for (i = 1; i *i <= val[n]; i++){if (val[n] % i==0){if (i*i == val[n]){num[nu++] = i;continue;}num[nu++] = i;num[nu++] = val[n] / i;}}sort(num, num + nu);ll temp, k, m;k = 1;for (i = nu - 1; i >= 0; i--){temp = num[i];map<ll, ll>cnt;m = 0;for (j = 1; j <= n; j++){m = max(m, ++cnt[val[j] % temp]);}while (k <= m){ans[k] = temp;k++;}}for (i = 1; i <= n; i++){printf("%lld\n", ans[i]);}//system("pause");return 0; }

总结

以上是生活随笔为你收集整理的HihoCoder 1246：王胖浩与环的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。