#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：王胖浩与环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。