首页 > 其他分享 >P7626 [COCI2011-2012#1] MATRIX( 普及/提高− ) 题解

P7626 [COCI2011-2012#1] MATRIX( 普及/提高− ) 题解

时间:2023-11-27 18:33:32浏览次数:45  
标签:P7626 MATRIX int 题解 复杂度 long 前缀

题目传送门

思路:

首先思考暴力,\(O(n^4)\) 的时间复杂度,不行。
那么我们这里就要运用到一点前缀和的知识了。
我们可以用前缀和对两条对角线进行计数。
每个点有两个对角线运算。
差不多是 \(O(n^2)\) 到 \(O(n^3)\)的时间复杂度。
而 \(n\leq400\) 稳过。

Code:

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,a[5][405][405];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[1][i][j];
			a[2][i][j]=a[1][i][j];
			a[1][i][j]=a[1][i][j]+a[1][i-1][j-1];
			a[2][i][j]=a[2][i][j]+a[2][i-1][j+1];//前缀和 
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=k;i<=n;i++)
		{
			for(int j=k;j<=n;j++)
			{
				ans=max(ans,(a[1][i][j]-a[1][i-k][j-k])-(a[2][i][j-k+1]-a[2][i-k][j+1]));//求差的最大值 
			}
		}
	}
	cout<<ans;
	return 0;
}

标签:P7626,MATRIX,int,题解,复杂度,long,前缀
From: https://www.cnblogs.com/BadBadBad/p/P7626.html

相关文章

  • NX二次开发UF_CSYS_edit_matrix_of_object 函数介绍
    文章作者:里海UF_CSYS_edit_matrix_of_objectDefinedin:uf_csys.h intUF_CSYS_edit_matrix_of_object(tag_tobject_id,tag_tmatrix_id)overview概述Updatesthespecifiedcoordinatesystemmatrixwiththeidentifierofthenewcoordinatesystemmatrixthatyouspe......
  • 复旦大学数学学院23级高等代数I期中考试精选大题解答
    四、求解下列线性方程组,其中$a_1,\cdots,a_n,b$为参数且$\sum\limits_{i=1}^na_i\neq0$:$$\begin{cases} (a_1+b)x_1+a_2x_2+a_3x_3+\cdots+a_nx_n=0,\\ a_1x_1+(a_2+b)x_2+a_3x_3+\cdots+a_nx_n=0,\\ a_1x_1+a_2x_2+(a_3+b)x_3+\cdots+a_nx_n=0,\\ \hfill\cdots\cdots......
  • CF1900 B Laura and Operations 题解
    LinkCF1900BLauraandOperationsQuestion给出\(1,2,3\)的个数\(a,b,c\)可以分别减少两个不同的数,增加一个与两个数都不同的数问,是否能经过一些操作使得就剩下\(1\)或\(2\)或\(3\)Solution先考虑\(1,2,3\)其实是等价的,所以我们只需要考虑把\(2,3\)全都变成......
  • CF1900 A Cover in Water 题解
    LinkCF1900ACoverinWaterQuestion给出一个\(n\)个格子,有些格子被堵塞了,有些格子是空的,我需要在进行一些操作,使得所有空的格子里面都有水操作1:给任意一个格子装上水操作2:把一格水从一个地方搬运到另外一个空的格子里如果一个空的格子的相邻的两个格子都有水,那么这......
  • Live Server插件打开浏览器时:该网页无法正常运作,127.0.0.1未发送任何数据的问题解决
    一、问题复现今天使用VsCode写HTML代码时,使用LiveServer打开预览时,发现浏览器显示“该网页无法正常运作,127.0.0.1未发送任何数据”的问题。二、解决办法1.在左侧工具栏找到扩展商店,找到LiveServer,然后点击对应的小齿轮,进入插件设置。2.选择ExtensionSettings3.进入......
  • ABC330 A-E 题解
    ABC330题解AtCoderBeginnerContest330A-CountingPasses思路:枚举一遍,当前数大于\(L\)使\(ans+1\)即可.代码:#include<iostream>#defineintlonglongusingnamespacestd; intn,l,ans;intx; signedmain(){ cin>>n>>l; for(inti=1;i&......
  • Information Graph 题解
    题目链接InformationGraph分析在线并不好做,考虑离线,先将树建出来\(2\)操作时\(x\)节点与当前根节点之间的点都会获得文件当前根节点可以用并查集维护对于查询的节点判断它是否为链上的点即可具体的,若该节点为\(rt\)子树中的点且该节点的子树包含\(x\)节点,它就......
  • P8706 [蓝桥杯 2020 省 AB1] 解码 ( 入门 ) 题解
    题目传送门思路:有一个原串\(t\)。将原串\(t\)转换成简写字符串\(s\)的规则如下:如果有连续的\(2\sim9\)个相同字母,那么可以将它改为字母+数字的格式。如果是单独的字符,也就是与左右两边的字母都不相同,在简写字符串中一模一样。所以,现在告诉我们简写字符串,要我们求出......
  • ICPC2022Xian G Perfect Word 题解
    LinkICPC2022XianGPerfectWordQuestion给出\(n\)个串,我们称\(t\)串是"good"当且仅当\(t\)的所有子串都在\(n\)个串中出现过问最长的"good"的串的长度Solution由于所有串的子串个数为\(L\times(L+1)/2\),\(L\)为串的长度所以”good“串的长度不会大......
  • ICPC2022Xian E Find Maximum 题解
    LinkICPC2022XianEFindMaximumQuestion定义\(f(x)\)求Solution通过打表我们可以发现\(f(x)\)表示三进制表达中有效位数与数码和之和接下来考虑如何获得最大的\(f(x)\)贪心的去考虑,假设答案为\(Ans\),\((Ans)_3\)肯定是前几位和\((R)_3\)的前几位一样,然后某一......