「NOIP2014」 无线网络发射器选址 - 前缀和

2024-01-02 07:58

本文主要是介绍「NOIP2014」 无线网络发射器选址 - 前缀和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

随着智能手机的日益普及,人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状,并且相邻的平行街道之间的距离都是恒定值1。东西向街道从北到南依次编号为0,1,2…128 , 南北向街道从西到东依次编号为0,1,2…128。

东西向街道和南北向街道相交形成路口,规定编号为x的南北向街道和编号为y的东西向街道形成的路口的坐标是(x,y)。 在某些路口存在一定数量的公共场所。

由于政府财政问题,只能安装一个大型无线网络发射器。该无线网络发射器的传播范围
一个以该点为中心,边长为2*d的正方形。传播范围包括正方形边界。

例如下图是一个d=1的无线网络发射器的覆盖范围示意图。

noip2014

现在政府有关部门准备安装一个传播参数为d的无线网络发射器,希望你帮助他们在城市内找出合适的安装地点,使得覆盖的公共场所最多。

输入格式

第一行包含一个整数d,表示无线网络发射器的传播距离。

第二行包含一个整数n,表示有公共场所的路口数目。

接下来n行,每行给出三个整数x,y,k,中间用一个空格隔开,分别代表路口的坐标(x,y)以及该路口公共场所的数量。同一坐标只会给出一次。

输出格式

输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点 方案数,以及能覆盖的最多公共场所的数量。

样例输入

1
2
4 4 10
6 6 20

样例输出

1 30

数据规模与范围

对于100%的数据, 1d20,1n20,0x,y128,0k1000000 1 ≤ d ≤ 20 , 1 ≤ n ≤ 20 , 0 ≤ x , y ≤ 128 , 0 ≤ k ≤ 1000000

分析

由于本题数据范围较小,可以用暴力过,但我还是讲讲二维前缀和的做法。

定义, sum[i][j] s u m [ i ] [ j ] 为前 i i 行前j列在 a[][] a [ ] [ ] 中的和。所以, sum[i][j] s u m [ i ] [ j ] 就是下图中棕色区域的和。

这里写图片描述

通过这张图,也可以知道,棕色区域就等于蓝色框起来的区域和+绿色框起来的区域和-它们重叠的黄色区域和+右下角没有没覆盖到的棕色值。

这里写图片描述

sum[i][j]=sum[i1][j]+sum[i][j1]sum[i1][j1]+a[i][j] s u m [ i ] [ j ] = s u m [ i − 1 ] [ j ] + s u m [ i ] [ j − 1 ] − s u m [ i − 1 ] [ j − 1 ] + a [ i ] [ j ]

这样我们就可以把前缀和算出来了。可要怎么快速查询 a[i][j]a[k][m] a [ i ] [ j ] − a [ k ] [ m ] 的和?也很简单,如下图:

这里写图片描述

我们可以看到, a[i][j]a[k][m] a [ i ] [ j ] − a [ k ] [ m ] 的和可以表示为棕色区域的和,而棕色区域的和就等于 sum[j][m]sum[i][m]sum[k][j] s u m [ j ] [ m ] − s u m [ i ] [ m ] − s u m [ k ] [ j ] 再加上多减的 sum[i][j] s u m [ i ] [ j ] ,即为

sum[k][m]sum[i][m]sum[j][m]+sum[i][j] s u m [ k ] [ m ] − s u m [ i ] [ m ] − s u m [ j ] [ m ] + s u m [ i ] [ j ]

这样就可以在 O(1) O ( 1 ) 时间内求解。

对于这道题,也是差不多的。

代码

#include <iostream>
#include <cstdio>
using namespace std;
int d,n;
long long sum[131][131],ans,cnt;
int g[130][130];
int main() {scanf("%d%d",&d,&n);for (int i = 1;i <= n;i++) {int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a+1][b+1]=c;}for (int i = 1;i <= 129;i++)for (int j = 1;j <= 129;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j];//制造前缀和for (int i = 1;i <= 129;i++) {for (int j = 1;j <= 129;j++) {long long t=sum[min(i+d,129)][min(j+d,129)]-sum[max(i-d,1)-1][min(j+d,129)]-sum[min(i+d,129)][max(j-d,1)-1]+sum[max(i-d,1)-1][max(j-d,1)-1];//注意是从i+d,j+d到i-d,j-d的和if (t>ans) {ans=t;cnt=1;}else if (t==ans) {cnt++;}}}printf("%lld %lld",cnt,ans);return 0;
}

这篇关于「NOIP2014」 无线网络发射器选址 - 前缀和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/561825

相关文章

机试算法模拟题 服务中心选址

题目描述 一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置,并希望能够以此为依据为新的服务中心选址:使服务中心到所有区域的距离的总和最小。 给你一个数组positions,其中positions[i] = [left, right] 表示第 i 个区域在街道上的位置,其中left代表区域的左侧的起点,right代表区域的右侧终点,假设服务中心的位置为loca

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

前缀和 — 利用前缀信息解决子数组问题

【前缀和的核心思想是预先处理数组来快速计算任意子数组的和,基本上用于数组和序列问题。】 前缀和算法具体步骤 构造前缀和数组: 给定一个数组nums,其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。构建前缀和公式: p r e x [ i ] = n u m s [ i ] ( i = = 0 ) p r e x [ i ] = p r e x

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

【数据结构-二维前缀和】力扣1504. 统计全 1 子矩形

给你一个 m x n 的二进制矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。 示例 1: 输入:mat = [[1,0,1],[1,1,0],[1,1,0]] 输出:13 解释: 有 6 个 1x1 的矩形。 有 2 个 1x2 的矩形。 有 3 个 2x1 的矩形。 有 1 个 2x2 的矩形。 有 1 个 3x1 的矩形。 矩形数目总共 = 6 + 2 + 3 + 1 +

Python高效实现Trie(前缀树)及其插入和查找操作

Python高效实现Trie(前缀树)及其插入和查找操作 在Python面试中,考官通常会关注候选人的编程能力、问题解决能力以及对Python语言特性的理解。Trie(前缀树)是一种高效的数据结构,广泛应用于字符串处理、自动补全、拼写检查等场景。本文将详细介绍如何实现一个Trie,并提供插入和查找操作,确保代码实用性强,条理清晰,操作性强。 1. 引言 Trie(前缀树)是一种树形数据结构,

Jaxb - 生成带命名空间和节点前缀的Xml的方式

一、生成带命名空间的Xml     Xml效果 <Order xmlns="http://www.xl.com.cn/msg">     Java代码 /*** Entity*/@XmlRootElement(name="Order", namespace="http://www.xl.com.cn/msg")public class Order{} 二、声明带前缀的命名空间

信息学奥赛初赛天天练-83-NOIP2014普及组-基础题2-输入设备、输出设备、操作系统、二进制、整数除法、while、do while循环

1 NOIP 2014 普及组 基础题2 4 以下哪一种设备属于输出设备( ) A 扫描仪 B 键盘 C 鼠标 D 打印机 5 下列对操作系统功能的描述最为完整的是( ) A 负责外设与主机之间的信息交换 B 负责诊断机器的故障 C 控制和管理计算机系统的各种硬件和软件资源的使用 D 将没有程序编译成目标程序 11 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( ) A 296

【UVa】10755 Garbage Heap 三维前缀和

题目分析:将前缀和应用到三维,求最大子矩阵。为S[x][y][z]数组中每个坐标保存从(0,0,0)到(x,y,z)范围内的子矩阵的元素和,最后用多次区间加减法可以得到需要的子矩阵的元素和,再用类似一维求最大连续和的方法求三维最大连续和。 代码如下: #include <cstdio>#include <cstring>#include <algorithm>using

【codeforces】gym 101138 K. The World of Trains【前缀和优化dp】

题目链接:K. The World of Trains 记录一个横着的前缀dp和以及斜着的前缀dp,复杂度 O(n2) O(n^2) #include <bits/stdc++.h>using namespace std ;typedef pair < int , int > pii ;typedef long long LL ;#define clr( a , x ) memset (