洛谷笔记 - P2241 统计方形（数据加强版）

发表于 更新于 本文字数： 321 阅读时长 ≈ 1 分钟

真的，这个题，你扔给高中的我，估计还能有点救。

可惜现在大学了，我只会当傻子 QAQ

题目背景

1997 年普及组第一题

题目描述

有一个 n×mn \times m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 n,mn,m（n≤5000,m≤5000n \leq 5000,m \leq 5000）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

1
2 3

样例输出 #1

1
8 10

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Problem: P2241 统计方形（数据加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2241
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//https://www.luogu.com.cn/record/95107674

#include<iostream>
using namespace std;
int main(){
	long long int n,m;
	cin>>n>>m;
	long long int z=0,c;
	for(long long int i=1;i<=min(n,m);i++){
		z+=(n-i+1)*(m-i+1);
	}
	long long int xxd=0,yxd=0;
	for(long long int i=1;i<=n;i++){
		xxd+=n-i+1;
	}
	for(long long int i=1;i<=m;i++){
		yxd+=m-i+1;
	}
	c=xxd*yxd-z;
	printf("%lld %lld\n",z,c);
	return 0;
}

后记

这道题花了我半个多小时磨各种奇奇怪怪的暴力算法。

后来才发现这玩意…… 它有规律？！

这智商怎么还活回去了呢……