NOIP 1997 普及组算法题解

零、背景

1997年举办的NOIP算法比赛，普及组仅有一道题目。
这道题可以用四种不同复杂度的方法来解答，下面将按复杂度从高到低依次介绍。

PS：题解代码已上传至网盘，公众号回复 NOIP-1997-J 获取。

一、棋牌问题

题目：给定一个 n * m 的方格棋盘，问有多少个正方形和多少个长方形。

思路1：暴力枚举所有长方形
复杂度：O(n^4)

ll aa = 0;  // 正方向个数
ll ab = 0;  // 长方形个数
for (int L = 1; L <= n; L++) {
  for (int U = 1; U <= m; U++) {
    for (int R = L; R <= n; R++) {
      for (int D = U; D <= m; D++) {
        if (R - L == D - U) {
          aa++;
        } else {
          ab++;
        }
      }
    }
  }
}

思路2：暴力枚举右下角，计算长方形和正方形的个数
复杂度：O(n^2)
长方形：对于每个右下角 (n,m)，就有 n*m个长方形。
正方向：对于每个右下角 (n,m)，就有 min(n,m)个正方形。

ll aa = 0;  // 正方向个数
ll ab = 0;  // 长方形个数
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
    aa += min(i, j);
    ab += i * j;
  }
}

思路3：找规律
复杂度：O(n)

分析思路2的规律，可以发现一些规律。

对于长方形，每个 i 会乘以所有 j，提取出 i 就是 i*(1+2+3+...+m)。
再提取出 (1+2+3+...+m) 就是 ((1+2+3+...+n)*(1+2+3+...+m)。
简化为公式就是 (1+n)*n/2 * (1+m)*m/2。

对于正方向，可以假设行不大于列，即 n<=m。

则每个右下角的正方向个数如下：

1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3 3
1 2 3 4 4 4 4 4 4
1 2 3 4 5 5 5 5 5
1 2 3 4 5 6 6 6 6

可以发现, 后面的列都是 1~n。
前面 n 行 n 列组成的正方向，不是完整的 1~n。
缺少的数字与 1~n 求差值，提取出来，如下：

0 0 0 0 0 0
1 0 0 0 0 0
2 1 0 0 0 0
3 2 1 0 0 0
4 3 2 1 0 0
5 4 3 2 1 0

可以发现，缺失的数字是有规律的。
第一行缺失 0。
第二行缺失 0+1。
… 第n行缺失 0+1+...+n-1。

故，可以先计算出 m 个 1~n 的和，然后减去缺失的数字即可。

ll Sum(ll n) { return n * (n + 1) / 2; }
ll ab = Sum(m) * Sum(n);
ll aa = m * Sum(n);
for (int i = 1; i <= n; i++) {
  aa -= Sum(i - 1);
}

思路4：数学公式
复杂度：O(1)

思路3已经推导出了规律，涉及到计算前缀和的前缀和。

下面是 ChatGPT 的推导过程。

二、最后

1997年是目前网上能找到的最早一场NOIP算法比赛，题目难度适中，最暴力的方法也可以通过。

如果数据范围在 10^3 以内，选择枚举一个角，O(n^2) 的复杂度效率最优。
如果数据范围在 10^4 ~ 10^6，则需要找规律，O(n) 的复杂度效率更高。
数据范围再大时，就需要直接推导公式，做到 O(1)。

《完》

-EOF-

本文公众号：天空的代码世界

个人微信号：tiankonguse

公众号ID：tiankonguse-code