洛谷刷题 前缀和与差分-[P2004]领地选择(C++)

2024-04-06 09:12

本文主要是介绍洛谷刷题 前缀和与差分-[P2004]领地选择(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

作为在虚拟世界里统帅千军万马的领袖,小 Z 认为天时、地利、人和三者是缺一不可的,所以,谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 C×C 的正方形。小 Z 希望你寻找到一个合适的位置,使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数 N,M,C,表示地图的宽和长以及首都的边长。

接下来 N 行每行 M 个整数,表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数 X,Y,表示首都左上角的坐标。

输入输出样例

输入 #1

3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

输出 #1

1 2

说明/提示

对于 60%60% 的数据,N,M≤50。

对于 90%90% 的数据,N,M≤300。

对于 100%100% 的数据,1≤N,M≤1e3,1≤C≤min(N,M)。

知识点:前缀和与差分-二维前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll a[N][N],b[N][N];
ll n,m,c,x,y,sum=LLONG_MIN;
int main() {cin>>n>>m>>c;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];}}int value;for(int i=1;i<=n-c+1;i++){for(int j=1;j<=m-c+1;j++){value=b[i+c-1][j+c-1]-b[i-1][j+c-1]-b[i+c-1][j-1]+b[i-1][j-1];if(value>sum){x=i,y=j;sum=value;}}}cout<<x<<" "<<y<<endl;return 0;
}

这篇关于洛谷刷题 前缀和与差分-[P2004]领地选择(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳:精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

《Python中requests与aiohttp在实际项目中的选择策略详解》本文主要介绍了Python爬虫开发中常用的两个库requests和aiohttp的使用方法及其区别,通过实际项目案... 目录一、requests 库二、aiohttp 库三、requests 和 aiohttp 的比较四、requ

el-select下拉选择缓存的实现

《el-select下拉选择缓存的实现》本文主要介绍了在使用el-select实现下拉选择缓存时遇到的问题及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录项目场景:问题描述解决方案:项目场景:从左侧列表中选取字段填入右侧下拉多选框,用户可以对右侧

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中,规

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode(VSCode)中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境:详细教程1. 什么是 VSCode?2. 安装 VSCo

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�