?

題意：

　　有一個環(huán)形序列，可以將其切成連續(xù)的k段子序列，那么gcd( 每段子序列的和 )就是優(yōu)美程度。輸出n個整數(shù)，表示當(dāng)k=[1, n] 時的最大優(yōu)美程度。?

?

思路：

　　觀察一下，當(dāng)切成1段的時候，gcd就是sum[整個序列]，為最大。考慮切成2段，那么最好就是能讓這個環(huán)切成2段和為sum[整個序列]/2的子序列了。考慮切成3段，那么最好就是能讓這個環(huán)切成3段和為sum[整個序列]/3的子序列了。繼續(xù)下去，這不就是求sum[整個序列]的約數(shù)嗎？

　　假設(shè)約數(shù)有k個，從大到小分別為factor[1～R]。那么其中有些因數(shù)是可能組不成的，得去掉那些組不成的。假設(shè)sum[整個序列]最多能切成cnt段和為factor[t]的連續(xù)子序列，那么段數(shù)i<=cnt的，答案都是factor[t]了，取最大即可。

　　問題在于如何求出切成長為factor[t]的最多段數(shù)cnt[t]？當(dāng)前綴和pre%factor=r出現(xiàn)了m次時應(yīng)該是這樣的： ..|xxxx|xxxx|......|xxx|xxxx|.. （共有m個切口|），觀察到除了首尾之外，其他每段都是d的倍數(shù)，且首尾之和也是d的倍數(shù)（因為sum[整個序列]=k*d）。那么對于factor[t]，只需要枚舉r來求出最大的m即可。

?

?

1 #include<bits/stdc++.h> 2 #define pii pair<int,int> 3 #define INF 0x3f3f3f3f 4 #define LL long long 5 using namespace std; 6 const int N=2010; 7 vector<LL> factor, cnt; 8 LL a[N]; 9 map<LL,LL> mapp; 10 int main() 11 { 12 freopen("input.txt","r",stdin); 13 int n; 14 while(~scanf("%d",&n)) 15 { 16 for(int i=1; i<=n; i++) 17 { 18 scanf("%lld",&a[i]); 19 a[i]+=a[i-1]; 20 } 21 for(LL i=1; i*i<=a[n]; i++) 22 { 23 if(a[n]%i==0) 24 { 25 factor.push_back(a[n]/i); 26 factor.push_back(i);//多一個也不影響結(jié)果 27 } 28 } 29 sort(factor.begin(),factor.end()); 30 deque<LL> ans; 31 for(int k=factor.size()-1,i=1; k>=0; k--) 32 { 33 LL big=0, c=factor[k]; 34 mapp.clear(); 35 for(int j=1; j<=n; j++) 36 big=max(big,++mapp[a[j]%c]); 37 while(i<=n&&big>=i) 38 { 39 ans.push_back(c); 40 i++; 41 } 42 } 43 while(!ans.empty()) 44 { 45 printf("%lld\n",ans.front()); 46 ans.pop_front(); 47 } 48 } 49 return 0; 50 } AC代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/xcw0754/p/4930073.html

總結(jié)

以上是生活随笔為你收集整理的hihoCoder #1246 : 王胖浩与环 （数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。