SCU 4440 Rectangle
Time Limit:0MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Description
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 1000000000Sample Output
8
0
1562562500625000000
一开始以为是dp，但是数据会爆掉，然后放在一边了。。
后来其他题目不会写了后，回过来想这题，想了好久是暴力还是数学计算。。
虽然最后用的是暴力加数学计算。。。
单纯暴力坑定会超时，仔细想了下，可以暴力去枚举一条边，再去考虑另一条的具体情况。
最后在模拟另一条边的情况的时候推算要注意一点。
AC代码：
#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"cstdio"
#include"string"
#include"vector"
#include"queue"
#include"cmath"
#include"map"
using namespace std;
typedef long long LL ;
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define FK(x) cout<<"["<<x<<"]\n"
#define bigfor(T) for(int qq=1;qq<= T ;qq++)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 int main() {
LL n,m,k;
while(cin>>n>>m>>k) {
k>>=1;
LL ans = 0;
for(int i=1; i<=n&&k-i>0; i++) {
LL x=min(k-i,m);
LL a=n-i+1;
LL b=(m+m-x+1)*x/2;
ans+=a*b;
}
cout<<ans<<endl;
}
return 0;
}