专栏文章

题解：P13938 [EC Final 2019] City

封封禁用户
P13938题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio172u2
此快照首次捕获于
2025/12/02 11:41
3 个月前
此快照最后确认于
2025/12/02 11:41
3 个月前
查看原文

题意：

给定一个n行m列的网格，找出所有满足以下条件的线段的数量：
  1. 两个端点都是网格点。
  2. 线段的中点也是网格点。

思路：

因为 1≤n,m≤10001\le n, m\le 1000。我们直接遍历所有网格点，时间复杂度为O(n∗m)O(n*m)。
AC Code:
PYTHON
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()

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...