【HDU5749 BestCoder Round 84C】【ST-RMQ？NO！暴力跳法or单调栈法 + 贡献思维】Colmerauer 所有子矩阵size乘鞍点权值和

2024-01-15 22:18
文章标签 round 思维 所有 矩阵 单调 暴力 st rmq bestcoder 贡献 size 权值 鞍点 跳法 hdu5749 84c 栈法 colmerauer

本文主要是介绍【HDU5749 BestCoder Round 84C】【ST-RMQ？NO！暴力跳法or单调栈法 + 贡献思维】Colmerauer 所有子矩阵size乘鞍点权值和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Colmerauer

Accepts: 32
Submissions: 121
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述 
Peter有一个n \times mn×m的矩阵MM. 定义S(a,b)S(a,b)为MM的所有大小为a \times ba×b的子矩阵的权值和. 一个矩阵的权值是这个矩阵所有鞍点的值的和. 在矩阵中, 一个数在所在行中是唯一的最小值, 在所在列中是唯一的最大值, 则被称为鞍点. 帮助Peter找出所有S(a,b)S(a,b)的值.注意: 本题中鞍点的定义可能和你所知的有所不同.
输入描述 
输入包含多组数据, 第一行包含一个整数TT表示测试数据组数. 对于每组数据:第一行包含两个整数nn和mm (1 \le n, m \le 1000)(1≤n,m≤1000)表示矩阵的大小.接下来nn行每行包含mm个非负整数, 表示矩阵MM的每一行 (MM中每个元素都不超过10^610​6​​).
输出描述 
对于每组数据, 输出一个整数W = (\displaystyle\sum_{a=1}^{n}\sum_{b=1}^{m}{a \cdot b \cdot S(a,b)}) \text{ mod } 2^{32}W=(​a=1​∑​n​​​b=1​∑​m​​a⋅b⋅S(a,b)) mod 2​32​​.
输入样例 
3
2 2
1 1
1 1
3 3
1 2 3
4 5 6
7 8 9
3 3
1 2 1
2 3 1
4 5 2
输出样例 
4
600
215

【HDU5749 BestCoder Round 84C】【ST-RMQ？NO！暴力跳法 + 贡献思维】Colmerauer 所有子矩阵size乘鞍点权值和

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1010, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m;
UI a[N][N];
UI c[N + N];
UI d[N][N];
int lft[N][N];
int rgt[N][N];
int top[N][N];
int bot[N][N];
void RMQinit()
{for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){if (j == 1)lft[i][j] = 1;else{int p = j - 1;while (p >= 1 && a[i][p] > a[i][j])p = lft[i][p] - 1;lft[i][j] = p + 1;}if (i == 1)top[i][j] = 1;else{int p = i - 1;while (p >= 1 && a[p][j] < a[i][j])p = top[p][j] - 1;top[i][j] = p + 1;}}}for (int i = n; i >= 1; --i){for (int j = m; j >= 1; --j){if (j == m)rgt[i][j] = m;else{int p = j + 1;while (p <= m && a[i][p] > a[i][j])p = rgt[i][p] + 1;rgt[i][j] = p - 1;}if (i == n)bot[i][j] = n;else{int p = i + 1;while (p <= n && a[p][j] < a[i][j])p = bot[p][j] + 1;bot[i][j] = p - 1;}}}
}int main()
{//fre();for (int i = 1; i <= 2000; ++i)c[i] = c[i - 1] + i;for (int i = 1; i <= 1000; ++i){for (int j = 1; j <= 1000; ++j){d[i][j] = d[i][j - 1] + c[i + j - 1] - c[j - 1];}}scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){scanf("%u", &a[i][j]);}}RMQinit();UI ans = 0;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){int topp = top[i][j];int bott = bot[i][j];int lftt = lft[i][j];int rgtt = rgt[i][j];ans += d[i - topp + 1][bott - i + 1] * d[j - lftt + 1][rgtt - j + 1] * a[i][j];}}printf("%u\n", ans);}return 0;
}
/*
【trick&&吐槽】
复杂度，复杂度，复杂度！
复杂度包括——
思维复杂度
代码复杂度
时空复杂度。这道题上来就想到求出每个点，作为鞍点，向左向右可以延展多少，向上向下可以延展多少。
不过是想用ST-RMQ实现。
而ST-RMQ的复杂度多了一个log(n)妈蛋，zimpha的数据竟然不水了，多个log的算法就tle了。
>.<虽然节省了思维复杂度，却浪费了代码复杂度与时空复杂度，最后没有AC。
还是酌情想出高效的算法比较好。【题意】
给你一个n*m的矩阵。
我们定义S(a,b)为所有大小为a*b的子矩阵的权值和。
一个子矩阵的权值和，定义为——
该矩阵中有所有鞍点的权值和。一个矩阵中的鞍点，定义为——
该点同行的所有点中，该点为唯一最小的点。
该点同列的所有点中，该点为唯一最大的点。让你输出∑(a=1~n)∑(b=1~m)a*b*S(a,b)【类型】
贪心思维 单调思维【分析】
这题用ST-RMQ的算法会导致tle
于是我们要尝试用O(nm)的算法AC这道题。
也就是说，用均摊O(1)的复杂度，求出——
1，每个点向左最多延伸多少个数，都比它大
2，每个点向右最多延伸多少个数，都比它大
3，每个点向上最多延伸多少个数，都比它小
4，每个点向下最多延伸多少个数，都比它小这个的处理方式，可以是本程序的暴力跳。
比如我们处理，"每个点向左最多延伸多少个数，都比它大"时，
int p = j - 1;
while (p >= 1 && a[i][p] > a[i][j])p = lft[i][p] - 1;
lft[i][j] = p + 1;我们对每个点，处理其向左可以延展的最大区间段。
如果发现再向左所延展的区间点，小于等于它，那延展失效。
否则便可以继续向左延展。
这个延展的过程，实际上也是区间合并。
显然我们一共只有n个区间，每次向左延展，也意味着多一次的区间合并。
而每个区间最多被合并一次，所以对于每行的m个数，处理lft[][]的总的复杂度为O(m)
即单点均摊复杂度为O(m)，总复杂度为O(nm)当然，这个过程还可以通过单调栈实现。
以处理lft为例。
我们维护一个严格上升的单调栈。
对于每一个位点，
如果其之前栈顶元素大于它，那么该点的左延展区间范围，就可以覆盖到该栈顶元素，我们同时做出栈处理。
直到——使得其之前栈顶元素小于等于它，那么该点就无法向左延展了，其延展的极限也就知道了。因为每个点最多入栈一次，出栈一次。所以每点的均摊复杂度为O(1)=======================
当我们处理完每个点向左向右向上向下的最大延展范围后。
那这个点有贡献的矩阵，
向上的延展长度，可以是[1,top]
向下的延展长度，可以是[1,bot]
向左的延展长度，可以是[1,lft]
向右的延展长度，可以是[1,rgt]也就是说，包括该点的【时间复杂度&&优化】
O(nm)【数据】
100 
5 5 
3 0 7 9 10 
4 9 9 9 7 
7 1 7 1 10 
3 1 8 6 1 
2 2 6 7 10 */
【HDU5749 BestCoder Round 84C】【ST-RMQ？NO！单调栈法 + 贡献思维】Colmerauer 所有子矩阵size乘鞍点权值和 

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1010, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m;
int a[N][N];
UI c[N + N];
UI d[N][N];
int lft[N][N];
int rgt[N][N];
int top[N][N];
int bot[N][N];int sta[N], tp;
void RMQinit()
{for (int i = 1; i <= n; ++i){sta[tp = 0] = 0; a[i][0] = -1e9;for (int j = 1; j <= m; ++j){while (a[i][sta[tp]] > a[i][j])--tp;lft[i][j] = sta[tp] + 1;//if (a[i][sta[tp]] == a[i][j])--tp;sta[++tp] = j;}}for (int i = 1; i <= n; ++i){sta[tp = 0] = m + 1; a[i][m + 1] = -1e9;for (int j = m; j >= 1; --j){while (a[i][sta[tp]] > a[i][j])--tp;rgt[i][j] = sta[tp] - 1;//if (a[i][sta[tp]] == a[i][j])--tp;sta[++tp] = j;}}for (int j = 1; j <= m; ++j){sta[tp = 0] = 0; a[0][j] = 1e9;for (int i = 1; i <= n; ++i){while (a[sta[tp]][j] < a[i][j])--tp;top[i][j] = sta[tp] + 1;//if (a[sta[tp]][j] == a[i][j])--tp;sta[++tp] = i;}}for (int j = 1; j <= m; ++j){sta[tp = 0] = n + 1; a[n + 1][j] = 1e9;for (int i = n; i >= 1; --i){while (a[sta[tp]][j] < a[i][j])--tp;bot[i][j] = sta[tp] - 1;//if (a[sta[tp]][j] == a[i][j])--tp;sta[++tp] = i;}}
}int main()
{for (int i = 1; i <= 2000; ++i)c[i] = c[i - 1] + i;for (int i = 1; i <= 1000; ++i){for (int j = 1; j <= 1000; ++j){//d[i][j] = d[i][j - 1] + c[i + j - 1] - c[j - 1];	//第一种计算方法d[i][j] = i*c[j] + j*c[i] - i*j;					//第二种计算方法}}scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){scanf("%d", &a[i][j]);}}RMQinit();UI ans = 0;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){int topp = top[i][j];int bott = bot[i][j];int lftt = lft[i][j];int rgtt = rgt[i][j];ans += d[i - topp + 1][bott - i + 1] * d[j - lftt + 1][rgtt - j + 1] * a[i][j];}}printf("%u\n", ans);}return 0;
}
/*
【trick&&吐槽】
复杂度，复杂度，复杂度！
复杂度包括——
思维复杂度
代码复杂度
时空复杂度。这道题上来就想到求出每个点，作为鞍点，向左向右可以延展多少，向上向下可以延展多少。
不过是想用ST-RMQ实现。
而ST-RMQ的复杂度多了一个log(n)妈蛋，zimpha的数据竟然不水了，多个log的算法就tle了。
>.<虽然节省了思维复杂度，却浪费了代码复杂度与时空复杂度，最后没有AC。
还是酌情想出高效的算法比较好。【题意】
给你一个n*m的矩阵。
我们定义S(a,b)为所有大小为a*b的子矩阵的权值和。
一个子矩阵的权值和，定义为——
该矩阵中有所有鞍点的权值和。一个矩阵中的鞍点，定义为——
该点同行的所有点中，该点为唯一最小的点。
该点同列的所有点中，该点为唯一最大的点。让你输出∑(a=1~n)∑(b=1~m)a*b*S(a,b)【类型】
贪心思维 单调思维【分析】
这题用ST-RMQ的算法会导致tle
于是我们要尝试用O(nm)的算法AC这道题。
也就是说，用均摊O(1)的复杂度，求出——
1，每个点向左最多延伸多少个数，都比它大
2，每个点向右最多延伸多少个数，都比它大
3，每个点向上最多延伸多少个数，都比它小
4，每个点向下最多延伸多少个数，都比它小这个的处理方式，可以是本程序的暴力跳。
比如我们处理，"每个点向左最多延伸多少个数，都比它大"时，
int p = j - 1;
while (p >= 1 && a[i][p] > a[i][j])p = lft[i][p] - 1;
lft[i][j] = p + 1;我们对每个点，处理其向左可以延展的最大区间段。
如果发现再向左所延展的区间点，小于等于它，那延展失效。
否则便可以继续向左延展。
这个延展的过程，实际上也是区间合并。
显然我们一共只有n个区间，每次向左延展，也意味着多一次的区间合并。
而每个区间最多被合并一次，所以对于每行的m个数，处理lft[][]的总的复杂度为O(m)
即单点均摊复杂度为O(m)，总复杂度为O(nm)当然，这个过程还可以通过单调栈实现。
以处理lft为例。
我们维护一个严格上升的单调栈。
对于每一个位点，
如果其之前栈顶元素大于它，那么该点的左延展区间范围，就可以覆盖到该栈顶元素，我们同时做出栈处理。
直到——使得其之前栈顶元素小于等于它，那么该点就无法向左延展了，其延展的极限也就知道了。因为每个点最多入栈一次，出栈一次。所以每点的均摊复杂度为O(1)=======================
当我们处理完每个点向左向右向上向下的最大延展范围后，我们要开始算贡献了——对于每个点，这个点作为鞍点，那这个点所得到贡献的矩阵——
向上的延展长度，可以是[1,top]
向下的延展长度，可以是[1,bot]
向左的延展长度，可以是[1,lft]
向右的延展长度，可以是[1,rgt]
其贡献，也就是
int y=0, x=0;
for(int i=1;i<=top;++i)
{for(int j=1;j<=bot;++j){y+=(i+j-1);}
}
for(int i=1;i<=lft;++i)
{for(int j=1;j<=rgt;++j){x+=(i+j-1);}
}
ans+=y*x*a[i][j]我们的做法有以下几种——
1，预处理for(int i=1;i<=a;++i)for(int j=1;j<=b;++j)tmp+=i+j-1;
这个的预处理，d[i][j]是在d[i][j-1]的基础上，获得了c[i+j-1]-c[j-1]的增长
2，独立(i)与(j)算贡献，显然——for(int i=1;i<=a;++i)for(int j=1;j<=b;++j)tmp+=i+j-1;有b个(1~a)，有a个(1~b)，再减去a*b个1【时间复杂度&&优化】
O(nm)【数据】
100
5 5
3 0 7 9 10
4 9 9 9 7
7 1 7 1 10
3 1 8 6 1
2 2 6 7 10*/


这篇关于【HDU5749 BestCoder Round 84C】【ST-RMQ？NO！暴力跳法or单调栈法 + 贡献思维】Colmerauer 所有子矩阵size乘鞍点权值和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/610387。

相关文章

hdu 4565 推倒公式+矩阵快速幂

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值： Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中： 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令： An=(a+b√)n A_n = (a +
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
阅读更多...
POJ1631最长单调递增子序列

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ
阅读更多...
计蒜客 Half-consecutive Numbers 暴力打表找规律

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN
阅读更多...
hdu 6198 dfs枚举找规律+矩阵乘法

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn
阅读更多...
Collection的所有的方法演示

Collection的所有的方法演示

import java.util.ArrayList;import java.util.Collection;import java.util.Iterator;public class TestCollection {/*** @param args* Collection的所有的方法演示* 此程序没有使用泛型，所以可以添加任意类型* 以后如果写到泛型会补充这一方面的内容*/public s
阅读更多...
Temu官方宣导务必将所有的点位材料进行检测-RSL资质检测

Temu官方宣导务必将所有的点位材料进行检测-RSL资质检测

关于饰品类产品合规问题宣导： 产品法规RSL要求 RSL测试是根据REACH法规及附录17的要求进行测试。REACH法规是欧洲一项重要的法规，其中包含许多对化学物质进行限制的规定和高度关注物质。 为了确保珠宝首饰的安全性，欧盟REACH法规规定，珠宝首饰上架各大电商平台前必须进行RSLReport(欧盟禁限用化学物质检测报告)资质认证，以确保产品不含对人体有害的化学物质。 RSL-铅，
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2