当前位置：首页 > article >正文

[NOIP1997 普及组] 棋盘问题

article 2025/3/11 20:39:10

题目背景

NOIP1997 普及组第一题

题目描述

设有一个 N×M 方格的棋盘 (1≤N≤100,1≤M≤100)

求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。

例如：当 N=2,M=3 时：

正方形的个数有 8 个：即边长为 1 的正方形有 6 个；边长为 2 的正方形有 2 个。

长方形的个数有 10 个：

即

2×1 的长方形有 4 个：
1×2 的长方形有 3 个：
3×1 的长方形有 2 个：
3×2 的长方形有 1 个：

输入描述

输入格式

一行两个整数 N,M。

输出描述

输出格式

一行两个整数，表示正方形的个数与长方形的个数。

用例输入 1

2 3

用例输出 1

8 10

看到这里，相信大家已经有思路了，可能会觉得，直接算不接好了吗？但是你想想，长方形怎么求？
所以，我的思路就是，算出来正方形的和总共的，长方形就等于总共的减正方形

接下来我们挨个分析：
输入部分

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,M;
    cin>>N>>M;
}

正方形：

    int zheng=0;
    for (int k=1;k<=min(N,M);k++) zheng+=(N-k+1)*(M-k+1);

总共的：

    int total=0;
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            total+=(N-i+1)*(M-j+1);
        }
    }

长方形（总共的-正方形）：

int chang=total-zheng;

输出：

cout<<zheng<<" "<<chang<<endl;

完整AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,M;
    cin>>N>>M;
    int zheng=0;
    for (int k=1;k<=min(N,M);k++) zheng+=(N-k+1)*(M-k+1);
    int total=0;
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            total+=(N-i+1)*(M-j+1);
        }
    }
    int chang=total-zheng;
    cout<<zheng<<" "<<chang<<endl;
}