Rectangle

题目链接（点击）

frog has a piece of paper divided into nn rows and mm columns. Today, she would like to draw a rectangle whose perimeter is not greater than kk.

There are 88 (out of 99) ways when n=m=2,k=6n=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 33 integer n,m,kn,m,k (1≤n,m≤5⋅104,0≤k≤1091≤n,m≤5⋅104,0≤k≤109).

Output

For each test, write 11 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

题意：

给出方格的长m和宽n 要求在其中取出一些矩形但要求这每个矩形的周长不能超过k 求出满足条件矩形的个数

思路：

跑两层for循环 i和j 分别表示要构造的矩形竖直方向的边长、水平方向的边长

复杂度 O(n²) 结果肯定是会T

优化：

枚举水平方向的长度为 j 则竖直方向最大长度为 imaxx = k/2 - j

观察竖直方向能构成矩阵的数目可以看出来是一个等差数列：

当imaxx=1时最多可以构成m个矩形

当imaxx=2时最多可以构成m-1个矩形

当imaxx=m时最多可以构成 m-i+1个矩形

所以构成以m为首项以d为公差的等差数列前i项的和sum：

sum=i*（m+m-i+1）/2

当求出最大j对应的imaxx时再去求总的和不就 = (i*（m+m-i+1）/2）*（n-j+1))

其中（n-j+1）表示 j为水平方向的边长时可以构成的矩形个数

这样就可以以O(n)的复杂度实现了

代码(wa)：

还要吐槽多组输入用while(~scanf("%d",&n)){} 好多次都忘记写v符号 ‘ ~ ’ 导致TLE

#include<stdio.h>

typedef long long LL;

int main()

{

    LL n,m,k;

    while(~scanf("%lld%lld%lld",&n,&m,&k)){

        LL sum=0;

        for(int i=1;i<=n;i++){ /// 会T

            for(int j=1;j<=m;j++){

                if(i*2+j*2<=k){

                    sum+=(n-i+1)*(m-j+1);

                }

                else{

                    break;

                }

            }

        }

        printf("%lld\n",sum);

    }

    return 0;

}

AC代码：

代码是用i表示水平方向 j表示竖直方向

#include<stdio.h>

typedef long long LL;

int main()

{

    LL n,m,k;

    while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF){

        LL sum=0;

        for(LL i=1;i<=n;i++){

            LL j=k/2-i;

            if(j<0){

                j=0;

            }

            else if(j>m){

                j=m;

            }

            sum+=(LL)((j*(m+m-j+1))/2)*(n-i+1);

        }

        printf("%lld\n",sum);

    }

    return 0;

}

巴特西

Rectangle【思维+模拟】