luogu2038 [NOIp2014]无线网络发射器选址 (前缀和)

时间:2022-09-14 21:56:07

貌似不用做前缀和也能过?

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int d,N;
ll sum[maxn][maxn]; int main(){
int i,j,k;
d=rd(),N=rd();
for(i=;i<=N;i++){
int a=rd(),b=rd(),c=rd();
sum[a][b]=c;
}
for(i=;i<=;i++){
for(j=;j<=;j++){
sum[i][j]+=(i?sum[i-][j]:)+(j?sum[i][j-]:)-(i&&j?sum[i-][j-]:);
}
}
ll mm=;int cnt=;
for(i=;i<=;i++){
for(j=;j<=;j++){
int i0=max(,i-d),j0=max(,j-d),ii=min(,i+d),jj=min(,j+d);
ll x=sum[ii][jj]-(j0?sum[ii][j0-]:)-(i0?sum[i0-][jj]:)+(i0&&j0?sum[i0-][j0-]:);
if(x>mm) mm=x,cnt=;
else if(x==mm) cnt++;
}
}
printf("%d %lld\n",cnt,mm);
return ;
}

luogu2038 [NOIp2014]无线网络发射器选址 (前缀和)的更多相关文章

  1. NOIP2014 无线网络发射器选址

    1.无线网络发射器选址 (wireless.cpp/c/pas) [问题描述] 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平 ...

  2. 关于NOIP2014&OpenCurlyDoubleQuote;无线网络发射器选址”一题的衍生题目的思考及思维方向

    无线网络发射器选址 题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形 ...

  3. NOIP2014无线网络发射器选址改编1

    问题描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状,并且相邻的平 ...

  4. noip2014无线网络发射器选址

    题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的 129 条东西向街道和 129 条南北向街道所形成的网格状,并且 ...

  5. &lbrack;NOIP2014&rsqb; 提高组 洛谷P2038 无线网络发射器选址

    题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形成的网格状,并且相邻 ...

  6. NOIP2014&lowbar;day2&colon;无线网络发射器选址

    #include<stdio.h>//NOIP2014 day2 :无线网络发射器选址 ,max=; ][]; void wifi(int a,int b,int c) { int i,j ...

  7. Codevs 3578 无线网络发射器选址&equals;&equals; NOIP 2014 Day2 T1

    3578 无线网络发射器选址 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 随着智能手机的日益普及,人们对无线网的需求日益增大. ...

  8. luogu2038&lbrack;NOIP2014 T4&rsqb;无线网络发射器选址

    题目描述 随着智能手机的日益普及,人们对无线网的需求日益增大.某城市决定对城市内的公共场所覆盖无线网. 假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形成的网格状,并且相邻 ...

  9. Noip2014 提高组 Day1 T1 生活大爆炸版石头剪刀布 &plus; Day2 T1 无线网络发射器选址

    Day1 T1 题目描述 石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头.如果两个人出拳一样,则不分胜负.在<生活大爆炸>第二季第8 集中出现了一种石头剪刀布的升级版游戏. 升 ...

随机推荐

  1. 自动打补丁Bat指令

    自动打补丁 补丁放于hotfix文件夹下 for %%i in (hotfix\*.exe) do start /wait %%i /z /u

  2. c&plus;&plus;中string类型可以直接进行比较

    以下代码在Ubuntu14.10下实现 /*------------------------- filename is demo.cpp --------------------------*/ #i ...

  3. linux yum安装mongodb

    1.yum -y install mongodb-server  mongodb 2.service mongod start                     #启动mongodb 服务 3. ...

  4. git 解决每次更新代码都要输入用户名密码的解决方案

    使用git pull或者git push每次都需要输入用户名和密码很繁琐,耽误时间,现在教大家一条命令实现保存用户名和密码不用再输入 git config --global credential.he ...

  5. docker与虚拟机有何不同

    docker与虚拟机有何不同 Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化. 容器技术有 ...

  6. UVA1646-Edge Case(递推&plus;斐波那契数列)

    Problem UVA1646-Edge Case Time Limit: 3000 mSec Problem Description Input For each test case, you ge ...

  7. Lodop导出图片和打印机无关,测试是否有关

    Lodop导出的图片,既可以在预览界面另存为,也可以用语句导出.语句导出,可查看本博客的相关博文:Lodop导出图片,导出单页内容的图片 预览的时候,由于选择的打印机不同,而真实的打印机可能有不同的可 ...

  8. DateTables的服务器分页

    function InitTable() { var table = $('#tbl_users').DataTable(); if ($.fn.dataTable.isDataTable('#tbl ...

  9. 《剑指offer&lpar;第二版&rpar;》面试题55——判断是否为平衡二叉树

    一.题目大意 输入一颗二叉树,判断该二叉树是否为平衡二叉树(AVL树). 二.题解 <剑指offer>上给出了两种解决方式: 1.第一种是从根节点开始,从上往下遍历每个子节点并计算以子节点 ...

  10. python学习之老男孩python全栈第九期&lowbar;day003知识点总结

    1. int: i.bit_length(): 把i这个数转换成二进制所需最少的位数 2. bool: (1) 1比True的效率更高 (2) 空字符串(什么都没有)为False:非空字符串为True ...