ZR#712 朱雀 2024-04-20 10:24 88阅读 0赞 ## ## 消灭砖块 ### 题意: ### > 很多块砖分布在一个 $ m \\times m $ 的矩阵中,他可以消掉以他为左上角顶点的一个 $ n \\times n $ 的矩阵里的所有砖块。计算可以消掉最多的砖块数(只能消一次)。 ### 解法: ### > 和最大子矩阵类似,不过要稍微改变一下条件和状态。 > 求前缀和,固定的子矩阵边长,然后把循环和计算那里容斥一下。 ### CODE: ### #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define N 1010 int m,n,k,f[N][N],pre[N][N]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i = 1 ; i <= k ; i++) { int x,y; scanf("%d%d",&x,&y); f[x][y]++; } for(int i = 1 ; i <= m ; i++) { for(int j = 1 ; j <= m ; j++) { pre[i][j] = f[i][j] + pre[i - 1][j]; } } int ans = 0; for(int i = 1 ; i <= m - n + 1 ; i++) { for(int j = 1 ; j <= m - n + 1 ; j++) { int sum = 0; for(int k = j ; k <= j + n - 1 ; k++) { sum += pre[i + n - 1][k] - pre[i - 1][k]; ans = max(ans,sum); } } } printf("%d \n",ans); //system("pause"); return 0; } 转载于:https://www.cnblogs.com/Repulser/p/11391059.html
相关 ZR#997 ZR\997 解法: > 找找规律就出来了,全场最简单的一道题。 CODE: include<iostream> include<cstdi... 怼烎@/ 2024年04月20日 10:34/ 0 赞/ 99 阅读
相关 ZR#999 ZR\999 解法: > 一道计数题,看到要求必须 $ m $ 个标号,所有标号至少出现一次的方案。 > 很容易想到可以容斥,但容斥这个东西是一种很神奇... 清疚/ 2024年04月20日 10:34/ 0 赞/ 98 阅读
相关 ZR#957 ZR\957 解法: > 首先 $ T $ 必须得要是 $ S $ 的子序列,不然不存在好的下标序列,因此一定无解。 > 考虑判断一个串 $ T $ 是... 痛定思痛。/ 2024年04月20日 10:34/ 0 赞/ 97 阅读
相关 ZR#959 ZR\959 解法: > 对于一个询问,设路径 $ (u, v) $ 经过的所有边的 $ gcd $ 为 $ g $,这可以倍增求出。 > 考虑 $ g... Bertha 。/ 2024年04月20日 10:34/ 0 赞/ 103 阅读
相关 ZR#998 ZR\998 解法: > 先把所有物品按照拿走的时间从小到大排序,拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。 ... 柔光的暖阳◎/ 2024年04月20日 10:33/ 0 赞/ 114 阅读
相关 ZR#956 集合 ZR\956 集合 解法: > 维护一个异或操作的懒标记,并对应的处理插入、删除和异或操作。接下来考虑如何整体加一。 > 考虑一个数字 $ x $ 变为... 待我称王封你为后i/ 2024年04月20日 10:31/ 0 赞/ 89 阅读
相关 ZR#712 消灭砖块 题意: > 很多块砖分布在一个 $ m \\times m $ 的矩阵中,他可以消掉以他为左上角顶点的一个 $ n \\times n $ 的矩阵... 朱雀/ 2024年04月20日 10:24/ 0 赞/ 89 阅读
相关 ZR#710 雷劈数 题意: > 现在给出两个整数,求出位于两个整数之间的所有的“雷劈数。 解法: > 因为雷劈数特殊的性质,所以在数据范围中的雷劈数实际很少,直... ゝ一纸荒年。/ 2024年04月20日 10:24/ 0 赞/ 111 阅读
相关 ZR#996 ZR\996 解法: > 若删除长度为 $ x $ 的子串后序列中没有相同元素,那么一定有至少一个长度为 $ x+1 $ 的子串,删除它后序列中也没有相同元... 怼烎@/ 2024年04月20日 10:23/ 0 赞/ 96 阅读
相关 leetcode 712 这道题的思路:我是根据最长公共子序列的思路得来的。 最长公共子序列是: d\[i\]\[j\]表示字符串s1前i个(0~i-1)字符,和字符串s2前j个(0~j-1)字符的最 野性酷女/ 2021年09月29日 04:46/ 0 赞/ 267 阅读
还没有评论,来说两句吧...