题意：
此题出自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）推导参看点击打开链接
