首页 > 代码库 > 洛谷 P1548 棋盘问题
洛谷 P1548 棋盘问题
题目描述
设有一个N*M方格的棋盘（l<=N<=100,1<=M<=100）(30％)
求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。
例如：当 N=2, M=3时： 
正方形的个数有8个：即边长为1的正方形有6个；
边长为2的正方形有2个。
长方形的个数有10个：
即2*1的长方形有4个：
1*2的长方形有3个：
3*1的长方形有2个：
3*2的长方形有1个：
如上例：输入：2 3
输出：8 10
输入输出格式
输入格式：
N和M
输出格式：
正方形的个数与长方形的个数
输入输出样例
输入样例#1：
2 3
输出样例#1：
代码
8 10
1 说说公式是怎么推导的吧 2 3 找规律: 4 5 正方形: 6 7 边长为1的正方形个数为n*m 8 9 边长为2的正方形个数为(n-1)*(m-1) （自己动手想想）10 11 边长为3的正方形为个数(n-2)*(m-2)12 13 边长为min(n,m)的正方形为个数s1=(n-min(n,m)+1)*(m-min(n,m)+1)14 15 然后从边长为1到min（m，m）的正方形个数全部加起来；16 17 长方形:(包括正方形，好像正方形属于长方形来着？)18 19 长为1的长方形（包括正方形）有n个20 21 长为2的长方形（包括正方形）有n-1个22 23 长为n的长方形（包括正方形）有1个24 25 长为1到n的长方形1+2+...+n个26 27 同理 宽为1的长方形（包括正方形）有m个28 29 宽为2的长方形（包括正方形）有m-1个30 31 宽为m的长方形（包括正方形）有1个32 33 宽为1-m的长方形1+2+...+m个34 35 然后把它们乘起来，根据乘法原理，总数s2=((1+n)*(1+m)*n*m)/4;36 37 题目要求的是“非正方形的长方形”，因此要减去s1;
#include<cstdio>#include<iostream>using namespace std;int n,m,ans1,ans2;inline void read(int&x) { int f=1;x=0;char c=getchar(); while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();} x=x*f;}int main() { read(n);read(m); int i=n,j=m; for(;i>=1&&j>=1;i--,j--) ans1+=i*j; int t1=0,t2=0; for(int k=1;k<=n;k++) t1+=k; for(int k=1;k<=m;k++) t2+=k; ans2=t1*t2; printf("%d %d\n",ans1,ans2-ans1); return 0;}
洛谷 P1548 棋盘问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。