题解 P2180 【摆石子】

· · 题解

基础计数类、基础数学思维类好题。

一看这n,m\le 30000就不是O(n^2)的算法，又不像是O(n)的，怎么办？慢慢分析。

首先，如果面对下面一种情况（一个o对应一个石子）：

oooo oooo ooo

要再放一个石子进去，应该如何放？当然要补在缺口处。这样新放上去的石子就可以和9个位置的石子组成矩形，然而放在别的位置都不能。（证明略）

所以结论就是：将石子阵摆成接近矩形，只有一个缺口的时候最优。

一个矩形石子阵(n\times m)可以有多少不同矩形呢？

\sum_{i=1}^{n}\sum_{j=1}^{m}(i\times j)

就是说有两次求和个矩形右下角可以选择，每一个右下角有i\times j个左上角与之对应，这样就不重不漏了。

化简一下：

=\sum_{i=1}^{n}(i\times\sum_{j=1}^{m}j) =\sum_{i=1}^{n}(\frac{i\times m \times(m+1)}{2}) =\frac{m(m+1)}{2}\sum_{i=1}^{n}i =\frac{m(m+1)}{2} \times \frac{n(n+1)}{2}

好了，那就用类似二维前缀和的方法计算一个不是矩形的石子阵就好了。

注意3\times 3的石子阵长和宽都只能以2带入上面的式子，为什么？请审题。

最后要做的就是枚举不完全矩阵的长度，分别计算。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
    int maxn=0;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        if(k/i>=m)continue;
        int len=k/i;
        int mod=k%i;
        maxn=max(maxn,(i*(i-1)/2*len*(len-1)/2+(len+1)*len/2*mod*(mod-1)/2-(len*(len-1)/2*mod*(mod-1)/2)));
    }
    for(int i=1;i<=m;i++){
        if(k/i>=n)continue;
        int len=k/i;
        int mod=k%i;
        maxn=max(maxn,(i*(i-1)/2*len*(len-1)/2+(len+1)*len/2*mod*(mod-1)/2-(len*(len-1)/2*mod*(mod-1)/2))); 
    }
    cout<<maxn<<endl;
    return 0;
}