简单单调栈的运用,悬线法---最大子矩阵,整除分块(规律+分块边界)

本文主要是介绍简单单调栈的运用,悬线法---最大子矩阵,整除分块(规律+分块边界),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

简单单调栈的运用

牛客一站到底 最优屏障
题意:有n座山,高度位ai,山上的士兵能相互监督当且仅当max(ai+1...aj-1)<min(ai,aj)
M国的防守能力大小为相互监视的哨兵对数,H国家可以放一块巨大屏障在某山前,以便最大消弱M方式能力
计算最优的屏障放置位置和最大的防守力减少量
 n≤50000
思路:屏障的放置将大区间分为左右两个独立区间,知道大区间的的值
在枚举屏障放置点,关键在与预处理左右两个独立区间
用栈处理左右区间,分为从后往前看,从前往后看两种
处理,添加一个数进来,能产生对数的是前面比之小的单调递减区间
 

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define fr(i,z,n) for(int i = z;i <= n; i++)
#define ufr(i,n,z) for(int i = n;i >= z; i--)
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
int v1[maxn];             //记录从后往前看
int v2[maxn];                     //从前往后看
stack<int>s;signed main()
{int t;scanf("%d", &t);for (int Case = 1; Case <= t; Case++) {memset(v1, 0, sizeof(v1));memset(v2, 0, sizeof(v2));while (!s.empty()) {s.pop();}int n;scanf("%d", &n);fr(i, 1, n) {scanf("%d", &a[i]);}for (int i = 1; i <= n; i++) {                 //从后往前看v1[i] = v1[i - 1];int t = 0;while (!s.empty() && s.top() < a[i]) {s.pop();t++;}if (!s.empty())  v1[i] += t + 1;else   v1[i] += t;s.push(a[i]);}while (!s.empty()) {s.pop();}for (int i = n; i >= 1; i--) {              //从前往后看v2[i] = v2[i + 1];int t = 0;while (!s.empty() && s.top() < a[i]) {s.pop();t++;}if (!s.empty())  v2[i] += t + 1;else   v2[i] += t;s.push(a[i]);}int ans = 0, id = 0;fr(i, 1, n) {int x = v1[n] - (v1[i] + v2[i + 1]);if (x > ans) {ans = x;id = i;}}id += 1;//Case #1: 2 2cout << "Case #" << Case << ": " << id << ' ' << ans << '\n';}
}

悬线法---最大子矩阵


HISTOGRA - Largest Rectangle in a Histogram
在一条水平线上有 n 个宽为1 的矩形,求包含于这些矩形的最大子矩形面积、
时间复杂度O(n)

#include <algorithm>
#include <cstdio>
using std::max;
const int N = 100010;
int n, a[N];
int l[N], r[N];         //l[i]表示a[i]向左能扩展到的位置,r[i]表示向右能扩展到的位置
long long ans;int main() {while (scanf("%d", &n) != EOF && n) {ans = 0;for (int i = 1; i <= n; i++) scanf("%d", &a[i]), l[i] = r[i] = i;for (int i = 1; i <= n; i++)while (l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1];for (int i = n; i >= 1; i--)while (r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1];for (int i = 1; i <= n; i++)ans = max(ans, (long long)(r[i] - l[i] + 1) * a[i]);printf("%lld\n", ans);}return 0;
}


P4147 玉蟾宫
给定n*m的矩阵,每一格为F或R,找到最大的全为F的矩形土地,输出面积*3
n<=m<=1000
思路:同HISTOGRA - Largest Rectangle in a Histogram,将每一行的位置向上扩展作为悬线长度
时间复杂度O(n*m)

#include <algorithm>
#include <cstdio>
#include<iostream>
using namespace std;
int m, n, a[1010], l[1010], r[1010], ans;
int main() {cin >> n >> m;int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {l[j] = r[j] = j;}char s;for (int j = 1; j <= m; j++) {cin >> s;if (s == 'F') {a[j]++;}else {a[j] = 0;}}        for (int j = 1; j <= m; j++) {while (l[j] > 1 && a[j] <= a[l[j] - 1])l[j] = l[l[j] - 1];}for (int j = m; j >=1; j--) {while (r[j] < m && a[j] <= a[r[j] + 1])   r[j] = r[r[j] + 1];}for (int j = 1; j <= m; j++) {ans = max(ans, a[j] * (r[j] - l[j] + 1));}} cout << 3*ans << '\n';
}


洛谷
感觉不错 Feel Good
给出正整数n 和一个长度为n 的数列a,要求找出一个子区间[l, r],
使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点
在答案相等的情况下最小化区间长度,最小化长度的情况下最小化左端点序号。
思路:寻找每一个结点的左右扩展,利用前缀和求出答案

#include <cstdio>
#include <cstring>
const int N = 100010;
int n, a[N], l[N], r[N];
long long sum[N];
long long ans;
int ansl, ansr;
bool fir = 1;int main() {while (scanf("%d", &n) != EOF) {memset(a, -1, sizeof(a));if (!fir)printf("\n");elsefir = 0;ans = 0;ansl = ansr = 1;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);sum[i] = sum[i - 1] + a[i];l[i] = r[i] = i;}for (int i = 1; i <= n; i++)while (a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1];for (int i = n; i >= 1; i--)while (a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1];for (int i = 1; i <= n; i++) {long long x = a[i] * (sum[r[i]] - sum[l[i] - 1]);if (ans < x || (ans == x && ansr - ansl > r[i] - l[i]))ans = x, ansl = l[i], ansr = r[i];}printf("%lld\n%d %d\n", ans, ansl, ansr);}return 0;
}

整除分块(规律+分块边界)


1.f(n)=n/i的和 (1<=i<=n) 
以l为左边界,k=n/l, 右边界r为k的最大下标i,找到最大的i满足i<=n/k
带入k,r=n/(n/l)

#include<iostream>
using namespace std;
int main()
{ int ans = 0;int n;cin >> n;for (int l = 1, r; l <= n; l = r + 1) {r = n / (n / l);cout << l << ' ' << r << '\n';ans += (n / l) * (r - l + 1);}cout << ans << '\n';return 0;
}


P1403 [AHOI2005] 约数研究
f(n)表示n的约数的个数
求f(i)的和  (1<=i<=n)
思路:约数的性质满足每个正约数i在1~n中出现的个为n/i
直接套用整除分块板子

#include<iostream>
using namespace std;
int main()
{int ans = 0;int n;cin >> n;for (int l = 1, r; l <= n; l = r + 1) {r = n / (n / l);//cout << l << ' ' << r << '\n';ans += (n / l) * (r - l + 1);}cout << ans << '\n';return 0;
}


P2424 约数和
f(x)表示x的所有约数和,求f(x)+f(x+1)...+f(y)
思路:约数的性质满足每个正约数i在1~n中出现的个为n/i,于是约数对总和的贡献为i*n/i
在区间[l,r]满足n/i为常数,等差数列求出
 

ans=cal(y)-cla(x-1)
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int a[1000];
int cal(int n) {int res = 0;for (int l = 1, r; l <= n; l = r + 1) {r = n / (n / l);//res += (n / l) * (r - l + 1) / 2;res += (n / l) * (l + r) * (r - l + 1) / 2;}return res;
}
signed main()
{int x, y;cin >> x >> y;cout << cal(y) - cal(x - 1) << '\n';return 0;
}
P2261 [CQOI2007] 余数求和
给定n,k,计算k%i的和,求(1<=i<=n)
n,k<=1e9
思路:对于a%b  -> a-b*(a/b)
k%i ->k-i*(k/i)
ans=k-i*(k/i)的和 (1<=i<=n)
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
signed main()
{int n, k;cin >> n >> k;int ans = n*k;for (int l = 1, r; l <= n; l = r + 1) {if (k / l != 0)                        //防止rer = min(k / (k / l), n);elser = n;ans -= (k / l) * (l + r) * (r - l + 1) / 2;}cout << ans << '\n';return 0;
}

这篇关于简单单调栈的运用,悬线法---最大子矩阵,整除分块(规律+分块边界)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

python中的整除向下取整的操作方法

《python中的整除向下取整的操作方法》Python中的//是整数除法运算符,用于执行向下取整的除法,返回商的整数部分,不会四舍五入,它在分治法、索引计算和整数运算中非常有用,本文给大家介绍pyth... 目录1. // 的基本用法2. // vs /(普通除法)3. // 在 mid = len(lis

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::