联萌十一大决战之强力热身 E. Rectangle

雨点打透心脏的1/2处 2022-08-09 01:48 69阅读 0赞

\[题目链接\] ([http://www.bnuoj.com/v3/contest\_show.php?cid=6865\#problem/E][http_www.bnuoj.com_v3_contest_show.php_cid_6865_problem_E])  
题目描述：  
E. Rectangle  
Time Limit: 1000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: Main  
Submit Status  
frog has a piece of paper divided into n rows and m columns. Today, she would like to draw a rectangle whose perimeter is not greater than k.  
![这里写图片描述][figure.png]

There are 8 (out of 9) ways when n=m=2,k=6

Find the number of ways of drawing.  
Input  
The input consists of multiple tests. For each test:

The first line contains 3 integer n,m,k (1≤n,m≤5⋅104,0≤k≤109).  
Output  
For each test, write 1 integer which denotes the number of ways of drawing.  
Sample Input  
2 2 6  
1 1 0  
50000 50000 1000000000  
Sample Output  
8  
0  
1562562500625000000  
言简意赅：  
在n\*m的矩阵中画蓝图，要保证使得蓝图为矩形，且该矩形的边长小于等于K，此题也算得上是水题了，整场比赛下来也是正确率偏高的一个题了，但东施般的正常暴力方法是完全不可能过的，因为数据颇大，所以此题应采用暴力一条边的方法，在暴力一条边的同时，另一条边的情况会相应的体现出来，很有技巧的暴力，别样的思维方式，值得学习。  
代码实现如下：

#include<iostream>
    #define  LL long long
    using namespace std;
    int main()
    {
        LL n,m,k;
        while(cin >> n >> m >> k)
        {
            LL ans = 0;
            for(int i=1; i<=n && k/2-i>0; i++)
            {
                LL a,b;
                if (k/2-i<m)
                {
                    a = n-i+1;
                    b = (m+(m-k/2+i+1))*(k/2-i)/2;
                    ans+=a*b;
                }
                else
                {
                    a = n-i+1;
                    b = (m+1)*m/2;
                    ans+=a*b;
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

[http_www.bnuoj.com_v3_contest_show.php_cid_6865_problem_E]: http://www.bnuoj.com/v3/contest_show.php?cid=6865#problem/E
[figure.png]: http://www.bnuoj.com/v3/images/figure.png