今日打卡：P2241 统计方形（数据加强版）

呃很抱歉有快大半年没更新了主要是精力有限不过有空的话我都会加紧更哒这么久没来洛谷这……我哩个天翻地覆啊我曾经的洛谷呢已崩溃不过我看洛谷现在的题单挺好的来试试《暴力枚举》嗯兑暴力的艺术今天的运势……好恐怖吓哭了好啦话不多说上题解对于这道题我们先考虑第一个问题一、算正方形的个数1.如果我们固定了正方形的右下角(i,j),你能不能算出此时可能的正方形的个数2.显然此时答案为Min(i,j).3.所以可以枚举右下角计算此时答案求和即可。二、算长方形个数1.其实算长方形并不常见但算矩形大家应该经常遇到所以如果你会算矩形再联系第一个问题那答案就转化为 矩形个数-正方形个数.2.像求解正方形个数一样固定矩形右下角(i,j),显然此时矩形个数为i*j.3.同理求和即可.时间复杂度O(n*m)是挺慢的其实可以写成一个式子代码如下#includecstdio #includeiostream #includecstring #includealgorithm #define ll long long using namespace std; int main() { ll n,m,i,j,sum0,sum10; cinnm; for(i1;in;i) { for(j1;jm;j) { summin(i,j); sum1i*j; } } coutsum sum1-sumendl; return 0; }最后还是向大家道歉嗯对不起求放过