2425: 【普及-】【P2241】统计方形（数据加强版）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：29
解决：17
题目描述
有一个 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。
输入
一行，两个正整数 （）。
输出
一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。
样例输入 复制
2 3样例输出 复制
8 10提示
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //把long long替换成LL以节约录入时间
int main(){
LL n,m,rec=0,squ=0; // LL是已经定义好的long long
scanf("%lld %lld",&n,&m);
for (LL x1 = 0; x1 <n ; x1++)
for (LL y1 = 0; y1 <m; y1++)
for (LL x2 = x1 + 1; x2 <= n; x2++) // x2从x1+1起，不重复不遗漏
for (LL y2 = y1 + 1; y2 <= m; y2++) // 同上
if (x2-x1 == y2-y1) // 正方形，两边长相等
squ++;
else // 长方形
rec++;
printf("%lld %lld",squ,rec);
return 0;
}
思路1：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //把long long替换成LL以节约录入时间
int main(){
LL n,m,rec=0,squ=0; // LL是已经定义好的long long
scanf("%lld %lld",&n,&m);
for (LL x = 0; x <= n; x++)
for (LL y = 0; y <= m; y++) {
LL tmp = min(x, y)+min(y,n-x)+min(n-x,m-y)+min(m-y,x);
squ += tmp;
rec += n * m - tmp;
}
printf("%lld %lld",squ/4,rec/4);
return 0;
}
思路2：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //把long long替换成LL以节约录入时间
int main(){
LL n,m,rec=0,squ=0; // LL是已经定义好的long long
scanf("%lld %lld",&n,&m);
/***
思路2：只需考虑右上角为 (x, y) 的情况，因此计算斜线上的顶点时，只需要向左下角一个方向拓展
***/
for (LL x = 1; x <= n; x++)
for (LL y = 1; y <= m; y++) {
LL tmp = min(x, y);
squ += tmp;
rec += x * y - tmp;
}
printf("%lld %lld",squ,rec);
return 0;
}
思路3：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //把long long替换成LL以节约录入时间
int main(){
LL n,m,rec=0,squ=0; // LL是已经定义好的long long
scanf("%lld %lld",&n,&m);
/***
思路3： 枚举边长 (a, b)。题目变为在 n×m 的长方形中能放置多少个 a×b 的方形。注意 a、b 有序，a×b 和 b×a 不等价。
***/
for (LL a=1;a<=n;a++)
for (LL b=1;b<=m;b++)
if (a==b)
squ+=(n-a+1)*(m-b+1);
else
rec+=(n-a+1)*(m-b+1);
printf("%lld %lld",squ,rec);
return 0;
}
思路4：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //把long long替换成LL以节约录入时间
int main(){
LL n,m,rec=0,squ=0; // LL是已经定义好的long long
scanf("%lld %lld",&n,&m);
for (LL a = 1; a <= min(m, n); a++)
squ += (n-a+1) * (m-a+1);
rec = n * (n+1) * m * (m+1) / 4- squ;
printf("%lld %lld",squ,rec);
return 0;
}