专栏文章

题解：P13938 [EC Final 2019] City

UUNNN
P13938题解参与者 2已保存评论 1

文章操作

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

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

题意

给定一个 n×mn \times m 的网格，问有多少条线段，使得该线段两端点在网格点上，且该线段中点也在网格点上。

思路

由于线段可以斜着画，所以我们不妨枚举所有网格点，求出以该网格点为中点的所有满足条件的线段数量。
我们以下图的红点为例，可以发现，如果以该红点为中点，那么可以构造出的线段的最大宽度为 66 格，最大高度为 66 格。
因此，我们可以构造出如下图的部分线段(如蓝色的线所示)。
上图线段数量的计算方式也很简单，我们设从中点横向延伸的长度(即线段最大宽度的一半)为 ww，纵向延伸的长度(最大高度的一半)为 hh。那么上面三个图的线段数量即为 h×(2w+1)h \times (2w + 1)。
同时，我们还需要加上没有纵向延伸的线段，显然，仅横向的线段数量就是 ww。
因此，以该点为中点的线段总数为 h×(2w+1)+wh \times (2w + 1) + w，累加在 ansans 中即可。
那么如何计算 ww 和 hh 呢？从该点开始左右或上下延伸，一旦碰到了边界，那么该延伸长度就是 ww 和 hh。
若假设网格左上角的点为 (1,1)(1, 1)，右下角为 (m+1,n+1)(m + 1, n + 1)，那么显然，对于一个网格点 (i,j)(i, j)，有 w=min⁡{i−1,m+1−i}w = \min\{i - 1, m + 1 - i\}，h=min⁡{j−1,n+1−j}h = \min\{j - 1, n + 1 - j\}。
由于计算结果可能很大，所以需要使用 long long。

Code

CPP
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n, m, ans = 0;
int main()
{
   scanf("%lld%lld", &n, &m);
   for(ll i = 1;i <= n + 1;i++){
       for(ll j = 1;j <= m + 1;j++){
           // 计算 h 和 w
           ll h = min(i - 1LL, n + 1LL - i);
           ll w = min(j - 1LL, m + 1LL - j);
           ll tot = h * ((w << 1LL) + 1LL) + w; // 计算该点线段数量
           ans = ans + tot; // 累加
       }
   }
   printf("%lld", ans); // 输出
   return 0; // 结束 (｡･ω･｡)
}

评论

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

正在加载评论...