首页 > 其他分享 >洛谷题单指南-前缀和差分与离散化-P2004 领地选择

洛谷题单指南-前缀和差分与离散化-P2004 领地选择

时间:2024-07-29 18:07:54浏览次数:20  
标签:前缀 P2004 int 洛谷题 差分 正方形 maxs x1

原题链接:https://www.luogu.com.cn/problem/P2004

题意解读:在一个n*m的矩阵中,找到边长为c的正方形,使得正方形范围内的数之和最大,输出正方形的左上角坐标。

解题思路:

二维前缀和的简单应用

第一步:计算二维前缀和

第二步:枚举边长为c的正方形左上角,计算正方形区域的数之和,更新答案

第三步:输出答案

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int a[N][N], s[N][N];
int n, m, c;
int ansx, ansy, maxs = -1e9;

int main()
{
    cin >> n >> m >> c;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            //计算二维前缀和
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    //枚举正方形的左上角
    for(int x1 = 1; x1 <= n - c + 1; x1++)
    {
        for(int y1 = 1; y1 <= m - c + 1; y1++)
        {
            int x2 = x1 + c - 1;
            int y2 = y1 + c - 1;
            //计算正方形范围数的和
            int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            if(sum > maxs)
            {
                maxs = sum;
                ansx = x1;
                ansy = y1;
            }
        }
    }

    cout << ansx << " " << ansy;
    return 0;
}

 

标签:前缀,P2004,int,洛谷题,差分,正方形,maxs,x1
From: https://www.cnblogs.com/jcwy/p/18330287

相关文章

  • 洛谷题单指南-前缀和差分与离散化-P1884 [USACO12FEB] Overplanting S
    原题链接:https://www.luogu.com.cn/problem/P1884题意解读:给定n个矩形的平面直角坐标系下左上角、右下角的坐标,计算这n个矩形能覆盖的的格子数。解题思路:直观上来看,此题是一个差分应用,针对二维差分数组,将n个矩形区域内每个格子的值加1,然后统计有多少个不为0的格子即可。但是!坐......
  • 洛谷题单指南-前缀和差分与离散化-P1496 火烧赤壁
    原题链接:https://www.luogu.com.cn/problem/P1496题意解读:给定n个区间[a,b),计算所有区间覆盖的总长度。解题思路:方法1、离散化先思考一种比较直观的思路:既然要计算多个区间覆盖的总长度,可以枚举每一个区间[a,b),通过一个桶数组来标记区间中所有的点f[x]=1,最终统计所有为1的......
  • [NOIP2004 提高组] 虫食算(含代码)
    [NOIP2004提高组]虫食算题目描述所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的数字。来看一个简单的例子:43#9865#045......
  • 前缀和与差分
    前缀和与差分前缀和定义:前缀和可以简单理解为「数列的前n项的和」,是一种重要的预处理方式,能大大降低查询的时间复杂度。一维前缀和模板for(inti=1;i<=n;i++)sum[i]=sum[i-1]+a[i];时间复杂度:O(n)原理数组sum用于储存前i个元素的和,数组a......
  • 差分约束
    差分约束差分约束是一种特殊的n元一次不等式组,m个约束条件,可以组成形如下的格式:\[\begin{cases}x_1-x_1^{'}\ley_1\\x_2-x_2^{'}\ley_2\\\cdots\\x_m-x_m^{'}\ley_m\end{cases}\]我们的任务是需要求出一组解,\(x_1=a_1,x_2=a_2,\cdots,x_n=a_n\)使得不等式......
  • 表面贴装差分输出晶体振荡器 DSO533SK/DSO533SJ 全面解析
    表面贴装差分输出晶体振荡器DSO533SK/DSO533SJ全面解析摘要:本文深入探讨表面贴装差分输出晶体振荡器DSO533SK/DSO533SJ的特性、工作原理、优势、应用领域以及使用中的关键要点。通过详细的阐述和实例分析,为读者提供全面且深入的技术解读。一、引言在当今高度集成和高......
  • 洛谷题单指南-前缀和差分与离散化-P3397 地毯
    原题链接:https://www.luogu.com.cn/problem/P3397题意解读:给定一个n*n的矩阵,每个元素初始值为0,再将m个子矩阵中的元素都增加1,统计每个元素最终的值。解题思路:1、暴力法枚举每一个子矩阵,将对应元素值加1,时间复杂度为1000^3,不可行。2、二维差分对于给定二维数组s[][],给指定区......
  • 洛谷题单指南-前缀和差分与离散化-P2367 语文成绩
    原题链接:https://www.luogu.com.cn/problem/P2367题意解读:对于数组s[],给指定q个区间[x,y]里每个数增加z,计算操作之后最小的数。解题思路:1、暴力做法对于每一个区间[x,y],枚举给每一个数增加z,然后遍历查找最小值,总体时间复杂度为O(N^2),不可行。2、一维差分对于给指定区间[x,......
  • 【模拟电子技术基础】差分放大电路——学生实验报告
        自己(大学生)在校做的实验报告,可借鉴使用,下载资源后可自行增删内容,或按照个人喜好优化排版。内容包括差分放大电路相关的实验目的、实验原理、实验过程及数据记录与处理分析、实验结论等。一、实验目的1.加深对差分放大电路性能及特点的理解2.学习差分放大电路主......
  • 洛谷题单指南-前缀和差分与离散化-P1314 [NOIP2011 提高组] 聪明的质监员
    原题链接:https://www.luogu.com.cn/problem/P1314题意解读:计算m个检验值之和,计算与s差值绝对值的最小值。解题思路:1、首先要搞懂检验值是如何计算的如上图,对于每一个区间的检验值yi,表示为:yi="该区间重量>=W的矿石个数" ✖️"该区间>=W的矿石价值之和"检验值y即所有yi(1<=......