形式化题目

在一个 $129\times129$ 的网格路口集合 $\{(x,y)\mid 0\le x,y\le128\}$ 上，给定 $n$ 个带权点：路口 $(x_i,y_i)$ 处有 $k_i$ 个公共场所（同一坐标只出现一次）。选择一个路口 $(cx,cy)$ 作为中心，覆盖所有满足

的带权点（覆盖正方形可以越出网格边界）。求覆盖权值之和最大的中心处，方案数（达到该最大和的中心个数）与最大和各是多少。

样例：$d=1$，点 $(4,4)$ 权 $10$、$(6,6)$ 权 $20$。只有 $(5,5)$ 一个中心能同时覆盖两点，和为 $30$；其余任何中心最多覆盖一点，和为 $10<30$。输出 1 30。

思路

朴素做法与规模评估。 最直接的想法：枚举每个路口 $(cx,cy)$ 作为安装地点，再对每个中心逐点检查 $n$ 个公共场所是否落入覆盖正方形，累加权值并维护最大值。中心有 $129^2=16641$ 个，每次检查 $n\le 20$ 个点，总运算量约 $16641\times20\approx3\times10^5$——在 C++ 里绰绰有余。但数据范围里真正的关键不是 $n$，而是网格是固定的 $129\times129$：这个"小网格 + 大量窗口查询"的结构提示我们换一条更通用的路——把点权铺成网格，用二维前缀和把每次查询降到 $O(1)$。

第一步：把覆盖判定变成矩形求和。 覆盖条件 $|x-cx|\le d$ 且 $|y-cy|\le d$ 恰好是"点落在以 $(cx,cy)$ 为中心、边长 $2d+1$ 的正方形内"（边界也算覆盖）。于是：开一个 $129\times129$ 的权值矩阵 $g$，$g[x][y]=k$（无公共场所则为 $0$），某个中心覆盖的数量之和就是矩阵上一个矩形窗口的元素和。窗口可能越出网格（例如中心 $(0,0)$），但所有带权点都在网格内，所以把窗口与网格 $[0,128]^2$ 求交即可，不会丢权值。

第二步：二维前缀和，$O(1)$ 回答每个窗口。 定义前缀和

外圈补一行一列 $0$ 哨兵，避免下标特判。逐行递推：先在行内做一维前缀，再把上一行的 $P$ 整体加到当前行。对矩阵 $A=[x_1..x_2]\times[y_1..y_2]$ 的查询就是容斥四角：

以下用样例画出任一窗口的四角查询（$d=1$、中心 $(5,5)$ 时窗口为 $[4,6]\times[4,6]$，两个点各被计入一次）：

再以中心 $(0,0)$、$d=2$ 为例看窗口裁剪：数学窗口是 $[-2,2]\times[-2,2]$，与网格求交成 $[0,2]\times[0,2]$，前缀和四角取 $P[3][3]-P[0][3]-P[3][0]+P[0][0]$，哨兵全为 $0$，无需任何分支特判。

第三步：统计最大值与方案数。 扫描全部 $129^2$ 个中心：若当前和 $s$ 大于已知最大值就重置答案；若恰好等于最大值就方案数加一。注意初值取 $0$ 且只在 $s$ 严格更大时重置——$s=0$ 的中心（覆盖不到任何公共场所）不参与计数，与题目"覆盖最多公共场所"的语义一致。

与朴素做法的关系。 这里的枚举中心是题目语义自带的（答案就是所有中心里取最优），不枚举中心就没有"方案数"可言；优化发生在每次评估一个中心的开销上：从"逐点检查 $n$ 个公共场所"降到"一次前缀和四角查询"。整体从 $O(129^2\cdot n)$ 降到 $O(129^2+n)$，同时窗口裁剪与哨兵设计让边界完全免于特判。数据范围下两种写法都能过，但前缀和写法更短、更不易错，也是这类"网格窗口统计"问题的标准姿势。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=129;
int main(){ios::sync_with_stdio(false); cin.tie(nullptr); int d,n; if(!(cin>>d>>n)) return 0; vector<vector<int> > g(N+1, vector<int>(N+1)); for(int i=0;i<n;i++){int x,y,k;cin>>x>>y>>k; g[x][y]=k;} vector<vector<int> > P(N+1, vector<int>(N+1)); for(int i=0;i<N;i++) for(int j=0;j<N;j++) P[i+1][j+1]=g[i][j]+P[i][j+1]+P[i+1][j]-P[i][j]; int best=0,cnt=0; for(int cx=0;cx<N;cx++) for(int cy=0;cy<N;cy++){int x1=max(cx-d,0),x2=min(cx+d,N-1),y1=max(cy-d,0),y2=min(cy+d,N-1); int s=P[x2+1][y2+1]-P[x1][y2+1]-P[x2+1][y1]+P[x1][y1]; if(s>best){best=s;cnt=1;} else if(s==best) cnt++;} cout<<cnt<<' '<<best<<'\n'; return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:54
# update_at: 2026-10-02 10:54

import sys
from itertools import accumulate

N = 129  # 街道编号 0..128


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    d = next(data)
    n = next(data)

    # 权重网格：路口 (x, y) 上的公共场所数量（题目保证同一坐标只出现一次）
    g = [[0] * (N + 1) for _ in range(N + 1)]
    for _ in range(n):
        x, y, k = next(data), next(data), next(data)
        g[x][y] = k

    # 二维前缀和：首行全 0 哨兵，逐行把行内前缀与上一行叠加
    # P[i][j] = sum(g[0..i-1][0..j-1])，比手工双重循环短得多
    P = [[0] * (N + 1)]
    for row in g:
        P.append([a + b for a, b in zip(accumulate(row, initial=0), P[-1])])

    best = cnt = 0
    # 枚举每个路口 (cx, cy) 作为发射器中心，正方形覆盖窗口用前缀和 O(1) 查询
    for cx in range(N):
        for cy in range(N):
            # 覆盖正方形与网格求交（正方形可越出城市，但所有路口都在网格内）
            x1, x2 = max(cx - d, 0), min(cx + d, N - 1)
            y1, y2 = max(cy - d, 0), min(cy + d, N - 1)
            s = P[x2 + 1][y2 + 1] - P[x1][y2 + 1] - P[x2 + 1][y1] + P[x1][y1]
            if s > best:
                best, cnt = s, 1
            elif s == best:
                cnt += 1
    print(cnt, best)


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(129^2+n)$——铺权重网格 $O(n)$，二维前缀和 $O(129^2)$，枚举 $129^2$ 个中心每次 $O(1)$ 查询。
• 空间复杂度：$O(129^2)$，权值矩阵与前缀和矩阵各一个。
• 最大覆盖和不超过 $n\cdot\max k=20\times10^6$，Python 整数无溢出问题；本地实测 10 组数据每组约 $20\,\mathrm{ms}$，远低于 OJ 限时。

总结

• 覆盖条件 $|x-cx|\le d,\ |y-cy|\le d$ 就是"中心为 $(cx,cy)$ 的正方形窗口"，把点权铺成 $129\times129$ 网格后，问题变成"枚举全部中心 + 矩形窗口求和取最大"。
• 二维前缀和（外圈哨兵 + 容斥四角）把每次窗口查询降到 $O(1)$，窗口与网格求交由 max/min 裁剪完成，边界零特判。
• 枚举中心是答案语义的一部分（要输出方案数），优化点在单次查询开销：$O(129^2\cdot n)\to O(129^2+n)$；统计时只在严格更大时重置，避免把 $s=0$ 的空中心计入方案数。