HDU 4572 Bottles Arrangement (找规律)

xiaoxiao2021-02-28  9

题意:

此题出自2009年IMO中国国家队选拔考试。

思路:

       考虑到题目要求苛刻,所以如果能构造出可以解释样例的矩阵,我们就能找到其中的规律。

       以 5 8 为例

        

       满足题意的矩阵即:      第一列由 1 ... N 顺序构成      每一行按 1 ... N N ... 1顺序构成        由于答案矩阵本身存在规律        利用规律,我们可以在 O(1) 的时间内求得每行的 sum        一共 N 行,O(N) 得到答案。

代码:

#include <bits/stdc++.h> using namespace std; const int MAXN=10100; const int INF=0x3f3f3f3f3f3f3f3f; long long lopsum,tempsum,fans,ans; int leftt,lop,offset[MAXN]; void ini(){ lopsum=0; fans=ans=0; } int range(int x,int y){ if(x<y) swap(x,y); return (x+y)*(x-y+1)/2; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=-1){ ini(); for(int i=1;i<=n;i++) lopsum+=i; for(int i=1;i<=n;i++){ if(i%2==1) offset[i]=i; else offset[i]=n-offset[i-1]; } for(int i=1;i<=n;i++){ if(i%2==1){ if(offset[i]>=m){ ans=range(i,i-m+1); }else{ ans=range(i,1); leftt=m-offset[i]; //if(i==5001) cout<<offset[i]<<' '<<leftt<<' '<<ans<<endl; lop=leftt/n;ans+=lop*lopsum; //if(i==5001) cout<<lop<<endl; leftt=leftt%n; if(leftt){ if(lop%2==1){ ans+=range(n,n-leftt+1); }else{ ans+=range(1,leftt); } } } }else{ if(offset[i]>=m){ ans=range(i,i+m-1); }else{ ans=range(i,n); leftt=m-offset[i]; lop=leftt/n;ans+=lop*lopsum; leftt=leftt%n; if(leftt){ if(lop%2==1){ ans+=range(1,leftt); }else{ ans+=range(n,n-leftt+1); } } } } fans=max(fans,ans); } cout<<fans<<endl; } } 另有O(1)推导

参看点击打开链接

转载请注明原文地址: https://www.6miu.com/read-1100185.html

最新回复(0)