题解：P13938 [EC Final 2019] City

Diary_Of_Young · 2025-09-02 20:04:14 · 题解

题意：

给定一个n行m列的网格，找出所有满足以下条件的线段的数量：

1. 两个端点都是网格点。
2. 线段的中点也是网格点。

思路：

因为 1\le n, m\le 1000。我们直接遍历所有网格点，时间复杂度为O(n*m)。

AC Code:

def main():
    n, m = map(int, input().split())
    ans = 0
    for i in range(n + 1):
        a = 2 * min(i, n - i) + 1
        for j in range(m + 1):
            b = 2 * min(j, m - j) + 1
            ans += (a * b - 1) // 2
    print(ans)

if __name__ == '__main__':
    main()