(横向刷题)【算法1-6】二分查找与二分答案【算法2-1】前缀和、差分与离散化(上),总结

news/2024/2/28 17:29:45

【算法1-6】二分查找与二分答案

P1024[NOIP2001 提高组] 一元三次方程求解


思路:题目说明根与根之差的绝对值>=1,且x1<x2&&f(x1)*f(x2)<0则其中存在解,于是联想到枚举,再用二分答案法控制精度
总结:二分对于精度的控制可以记录一下
扩展:盛金公式求解一元三次函数,记住公式模板即可,推导太过麻烦了,

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
double a, b, c, d;
double check(double x) {return a * x * x * x + b * x * x + c * x + d;
}void solve(){cin >> a >> b >> c >> d;double x1, x2,l,r,m;int count = 0;for (double i = -100; i <= 100; i++) {l = i;r = i + 1;x1 = check(l);x2 = check(r);if (x1 == 0) {printf("%.2lf ", l);     //不考虑左端点,防止重复计算count++;}if (x1 * x2 < 0) {                            //区间内有根。while (r - l >= 0.001)  {                   //二分控制精度。m = (l + r) / 2;if (check(m) * check(r) <= 0)l = m;elser = m;  }printf("%.2lf ", r);//输出右端点。count++;}if (count >= 3) {break;}}}
signed main()
{ios::sync_with_stdio(false);int t=1;//cin >> t;while (t--) {solve();}
}


盛金公式:
 

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast) 
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
vector<double>X123;
void ShengJin(double a, double b, double c, double d){double A = b * b - 3 * a * c;double B = b * c - 9 * a * d;double C = c * c - 3 * b * d;double f = B * B - 4 * A * C;double i_value;double Y1, Y2;if (fabs(A) < 1e-6 && fabs(B) < 1e-6)//公式1{X123.push_back(-b / (3 * a));X123.push_back(-b / (3 * a));X123.push_back(-b / (3 * a));}else if (fabs(f) < 1e-6)   //公式3{double K = B / A;X123.push_back(-b / a + K);X123.push_back(-K / 2);X123.push_back(-K / 2);}else if (f > 1e-6)      //公式2{Y1 = A * b + 3 * a * (-B + sqrt(f)) / 2;Y2 = A * b + 3 * a * (-B - sqrt(f)) / 2;double Y1_value = (Y1 / fabs(Y1)) * pow((double)fabs(Y1), 1.0 / 3);double Y2_value = (Y2 / fabs(Y2)) * pow((double)fabs(Y2), 1.0 / 3);X123.push_back((-b - Y1_value - Y2_value) / (3 * a));//虚根我不要//虚根还是看看吧,如果虚根的i小于0.1,则判定为方程的一根吧。。。i_value = sqrt(3.0) / 2 * (Y1_value - Y2_value) / (3 * a);if (fabs(i_value) < 1e-1){X123.push_back((-b + 0.5 * (Y1_value + Y2_value)) / (3 * a));}}else if (f < -1e-6)   //公式4{double T = (2 * A * b - 3 * a * B) / (2 * A * sqrt(A));double S = acos(T);X123.push_back((-b - 2 * sqrt(A) * cos(S / 3)) / (3 * a));X123.push_back((-b + sqrt(A) * (cos(S / 3) + sqrt(3.0) * sin(S / 3))) / (3 * a));X123.push_back((-b + sqrt(A) * (cos(S / 3) - sqrt(3.0) * sin(S / 3))) / (3 * a));}
}void solve(){double a, b, c, d;cin >> a >> b >> c >> d;ShengJin(a, b, c, d);sort(X123.begin(), X123.end());for (auto i : X123) {printf("%.2lf ", i);}}
signed main()
{ios::sync_with_stdio(false);int t=1;//in >> t;while (t--) {solve();}
}

P1182 数列分段 Section II


思路:关键字眼最大值的最小化联想二分,直接二分最大值,l应取数组最大值,r应取数组和,
总结:这道题启发挺大,总结出二分的套路,最大值的最小化,最小值的最大化一般联想到二分,在范围内直接二分(最大值,最小值)
同时二分板子的l,r一定要写清楚,不然要调好久,并且二分的l,r并不是简单的l=0或1,r=无穷,应该考虑极端情况设想就像这题
此类问题check()函数的判定一般根据给定的划分个数

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
#define int long long
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
int n, m;
bool check(int x) {ll sum = 0;int cnt = 0;for (int i = 1; i <= n; i++) {if (sum + a[i] <= x) {sum += a[i];}else {cnt++;sum = a[i];}}return cnt >= m;
}void solve(){cin >> n >> m;int l=0,r=0;for (int i = 1; i <=n; i++) {cin >> a[i];l = max(l, a[i]);r += a[i];}while (l <= r) {                 //二分板子int mid=(l + r) / 2;if (check(mid)) {l = mid+1 ;}else {r = mid - 1;}}cout << l << '\n';}
signed main()
{ios::sync_with_stdio(false);int t=1;//cin >> t;while (t--) {solve();}
}


扩展:最小值的最大化(二分)
POJ2456

题意:英文题写下题意:有n个牛栏,m头牛,然牛住进牛栏,使住牛的相邻牛栏最小间隔最大
思路:根据上题,直接二分(最小值),范围l=0(同住一个栏),r=(数组最大值-最小值)

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
int n, m;
bool check(int x) {int pre = 1;int cnt = 1;for (int i = 2; i <= n; i++) {if ((a[i] - a[pre])>=x) {cnt++;pre = i;if (cnt >= m)return true;}}return false;
}void solve(){int l = 0, r = 0;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + 1 + n);    //使之具有单调性r = a[n] - a[1];while (l < r) {int mid = (l+r+1) >> 1;if (check(mid)) {l = mid;}else {r = mid-1;}}cout << l << '\n';}
signed main()
{ios::sync_with_stdio(false);int t=1;//cin >> t;while (t--) {solve();}
}


扩展:
P3853[TJOI2007]路标设置


思路:关键字相邻路标的最大距离的最小值,直接二分最小值,套板子,check的判定在距离内本就有两个路标,若有余数说明需要y/x向下取整的路标数,但没余数则多出一个

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
int L, n, k;
bool check(int x) {int cnt = 0;for (int i = 2; i <= n; i++) {int y = a[i] - a[i - 1];if (y > x) {cnt += (y)/x;if (y % x == 0) {cnt--;}}}return cnt <= k;
}void solve(){cin >> L >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];}int l = 1, r = L;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) {r = mid-1;}else {l = mid +1;}}cout << l << '\n';}
signed main()
{ios::sync_with_stdio(false);int t=1;//cin >> t;while (t--) {solve();}
}

【算法2-1】前缀和、差分与离散化(上)

AcWing 802. 区间和


思路:对于操作的位置x,和查询的位置l,r值域大,个数较少,于是离散化,
之后二分映射找到离散化后的操作位置+c,前缀和处理,对于询问也同样二分映射找到离散化后的询问位置查询,
对于查询有点像离线操作,这道题在ACW
总结:在数据值域很大,但个数较少的时候,可以使用离散化,如果使用map会爆内存,
 离散化的本质还是映射,将值域间隔大的点映射到间隔数组,无论是对查询,还是操作都会节省时间和空间要求,这道题感觉很典型

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const ll maxn=2e5+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
int Hash[maxn<<1];
int s[maxn];
int sum[maxn];
vector<pair<int, int>>v;   //操作
vector<pair<int, int>>v1;     //询问void solve(){int n,m;cin >> n>>m;int cnt = 0;for (int i = 1; i <= n; i++) {int x, c;cin >> x >> c;v.push_back({ x,c });    //操作离线Hash[++cnt] = x;   //离散}for (int i = 1; i <= m; i++) {int l, r;cin >> l >> r;v1.push_back({ l,r });   //查询离线Hash[++cnt] = l;Hash[++cnt] = r;}sort(Hash + 1, Hash + 1 + cnt);auto k = unique(Hash, Hash + 1 + cnt);for (auto x : v) {    //执行操作int y = lower_bound(Hash + 1, Hash + 1 + cnt, x.first) - Hash;  //找到离散化后的操作位置a[y] += x.second;}for (int i = 1; i <= cnt; i++) {a[i] += a[i - 1];}for (auto x : v1) {int l= lower_bound(Hash + 1, Hash + 1 + cnt, x.first) - Hash;  int r = lower_bound(Hash + 1, Hash + 1 + cnt, x.second) - Hash;cout << a[r] - a[l - 1] << '\n';}}
signed main()
{ios::sync_with_stdio(false);int t=1;//cin >> t;while (t--) {solve();}
}


扩展:P1496 火烧赤壁


思路:同样是数据值域很大,但个数较少,于是离散化,在离散化后的数组操作,同上,一定注意左开右闭,像我没注意到调了好久
总结:离散化的套路很明显,数据值域很大,但个数较少,把原数组操作转化到离散数组的操作,映射即可

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
#define int long long
typedef long long ll;
const ll maxn = 2e5 + 10, inf = 1e18;
const ll mod = 1e9 + 7;
using namespace std;
int Hash[maxn << 1];
vector<pair<int, int>>v;   //操作
int flag[maxn];
void solve() {int n;cin >> n;int cnt = 0;for (int i = 1; i <= n; i++) {int l, r;cin >> l >> r;v.push_back({ l,r });   //操作离线Hash[++cnt] = l;Hash[++cnt] = r;}cnt++;sort(Hash + 1, Hash + 1 + cnt);for (auto x : v) {    //执行操作int l = lower_bound(Hash + 1, Hash + 1 + cnt, x.first) - Hash;  //找到离散化后的操作位置int r = lower_bound(Hash + 1, Hash + 1 + cnt, x.second) - Hash;  for (int i = l; i <= r-1; i++) {     //左闭右开flag[i]++;}}int ans = 0;for (int i = 1; i <= cnt; i++) {if (flag[i]) {ans += Hash[i + 1] - Hash[i];}}cout << ans << '\n';
}
signed main()
{ios::sync_with_stdio(false);int t = 1;//cin >> t;while (t--) {solve();}
}


P1955[NOI2015] 程序自动分析


思路:同样注意到i,j值域很大,但个数较小,离散化,判定满不满足条件,可以并查集判定,这道题还是挺简单的
总结:通过前几个题目可以发现,把原数组操作转化到离散数组的操作,操作是离线的

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define endl cout<<'\n';
typedef long long ll;
const ll maxn=2e6+10,inf = 1e18 ; 
const ll mod = 1e9 + 7;
using namespace std;
int t, n, f[maxn], Hash[maxn];  
struct node {int x, y, e;
}a[maxn];
bool cmp(node a, node b) {return a.e > b.e;
}
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]); 
} //并查集
void solve(){int cnt = 0;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i].x >> a[i].y >> a[i].e;Hash[++cnt] = a[i].x;Hash[++cnt] = a[i].y;}sort(Hash, Hash + cnt);//排序 int len = unique(Hash, Hash + cnt) - Hash-1;  //去重 for (int i = 1; i <= n; ++i) {a[i].x = lower_bound(Hash, Hash + len, a[i].x) - Hash;a[i].y = lower_bound(Hash, Hash + len, a[i].y) - Hash;}for (int i = 1; i <= len; ++i) {f[i] = i;}sort(a + 1, a + n + 1, cmp);  //按e排序 for (int i = 1; i <= n; i++) {int r1 = find(a[i].x);int r2 = find(a[i].y);if (a[i].e) {f[r1] = r2; }else if (r1 == r2) {NO;return;}}YES;
}
int main() {cin >> t;while (t--) {solve();}return 0;
}

这周任务安排

除cf,牛客重现赛补题,坚持对以前的算法,数据结构进行横向刷题,这周为【算法2-1】前缀和、差分与离散化(上),【算法2-3】分治与倍增

总结

通过对以前的算法进行巩固,发现了许多套路,像二分的最大值的最小化,最小值的最大化,离散的数据值域很大,但个数较少,这都是以前没有发现的,还有对题目的总结,扩展也很重要,做题的时候切忌浮躁,一定好好好琢磨背后考察的知识点,另外就是与师傅的沟通不够


http://www.ppmy.cn/news/389595.html

相关文章

Vector-常用CAN工具 - 以太网报文收发方向

目录 Rx 和 Tx 标记 Example&#xff1a;从 CANoe 向 ECU 发送以太网数据包 用例 2&#xff1a;从 ECU 接收以太网数据包 如何仅显示物理或虚拟通信 如何仅显示 Rx 或 Tx 以太网数据包 VN5000以太网包过滤 1、什么是硬件过滤&#xff1f; 2、什么时候使用硬件过滤&…

windows上编译linux程序

文章目录 前言Cygwin、MinGW和MSYS2的区别MSYS2的安装和配置示例 前言 有些项目创建之初&#xff0c;(仅考虑在linux上运行)不考虑在windows原生编译&#xff0c;所以以没有采用跨平台的API进行开发。 后续想要将项目从linux上&#xff0c;移植到windows上运行。要么是重写不…

无线充电小车的实物图

无线充电小车的实物图

图片如何去掉背景色?如何使图片背景变透明?

图片设计工作者常常需要用透明背景图片&#xff0c;如果下载的图片素材不是透明背景的话&#xff0c;就需要先用图片处理工具将图片背景变透明。下面我们就使用压缩图的图片去底色&#xff08;https://www.yasuotu.com/buttonColor&#xff09;功能来给大家演示一下&#xff0c…

上传图片计算机没有桌面,笔记本电脑浏览器不能上传图片怎么处理

随着互联网的进步&#xff0c;浏览器的变化也是层出不穷&#xff0c;很多人用过笔记本电脑&#xff0c;但不免发现有时会遇到笔记本电脑在浏览器无法上传图片的问题&#xff0c;各种绞尽脑汁去解决&#xff0c;有些甚至已然放弃。其实都是没找到真正的方法&#xff0c;只要用心…

AI 去掉图片的背景色

下面介绍在 illustrator 中去掉图片的背景色。 1.打开图片 2.选中图片&#xff0c;再点击上面属性栏中的“图像描摹”下拉按钮&#xff0c;弹出菜单选择“高保真度照片” 3.把图片进行图像描摹后&#xff0c;如图所示&#xff0c;再点击“扩展” 4.鼠标放在图片&#xff0c;再…

电子设计大赛电动车跷跷板设计

文末下载完整资料 摘要   本系统以51系列单片机为控制中心&#xff0c;外加电机驱动集成电路L298、七段码译码显示集成电路74LS247、七段码数码管等外围元件控制电动车前进、后退、停止等运行状态&#xff0c;并显示所需时间、发出声光报警。本次设计前进、后退、停止等状态运…

识别电动汽车车牌并使用自动充电车充电的方案

主要参考&#xff1a;1.用MATLAB实现基于A*算法的路径规划&#xff1b; 2.车牌识别系统&#xff1b;3. 路径规划五种算法简述 下面都是写给自己看的&#xff0c;没地方存储才放上来的。因为大部分都是copy上面两个的&#xff0c;所以放上来不太好。 一、车牌识别 用户在APP上…

css图片填充背景色

background: url(/image/login_icon.png) -104px -47px no-repeat #feefef;

台式计算机的美图,为什么我在台式电脑上看图片,图片色彩很饱和很鲜艳,而笔记本上看的图片有点暗淡呢...

为什么我在台式电脑上看图片&#xff0c;图片色彩很饱和很鲜艳&#xff0c;而笔记本上看的图片有点暗淡呢以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容&#xff0c;让我们赶快一起来看一下吧&#xff01; 为什么我在台式电脑上看图片&#…

上海车展:深蓝汽车首次亮相,全场景电动出行实力圈粉

4月18日&#xff0c;2023上海国际车展如约而至。 作为疫情结束后的首个国际车展&#xff0c;本届上海车展自然吸睛无数&#xff0c;光是首个媒体日进场时的阵仗&#xff0c;就让无数媒体人高呼“人潮汹涌”。 而在本次参展的众多汽车品牌中&#xff0c;刚刚成立一周年的深蓝汽车…

[Java 基于SSO实现单点登录]

目录 前言: 基于 Token 的 SSO 实现单点登录 实现 SSO 的单点登录通常需要以下步骤&#xff1a; 第一步: 创建一个 UserService 类&#xff0c;用于处理用户登录和生成 Token。 创建一个 TokenCache 类&#xff0c;用于存储 Token 和对应的用户信息。 在 Auth Center 中…

海尔消费金融进一步强化经济精神,让用户走向高质量生活消费体验

消费金融在经济结构转型升级中发挥着积极作用。从实际情况来看,消费金融增加对耐用消费品的消费,并开始更多向个人成长、自我提升的领域延伸,有助于消费升级、带动产业机构调整。 2019 年,海尔消费金融宣告将持续打造物联网家庭金融服务渠道,进一步完成“三化一经营”的战略升…

海尔的成功

一、电子商务是海尔的必由之路 网络经济时代的到来&#xff0c;企业如何发展&#xff0c;是一个崭新而迫切的的问题。1999年达沃斯“世界经济论坛”提出了“企业内部组织适应外部变化、全球知名品牌的建立、网上销售体系的建立”三条原则。今年的达沃斯会议又提出了人类在新世纪…

来谈谈海尔采购与供应链管理的智慧!

“海尔在供应链管理上面&#xff0c;并不是像一些企业一样纸上谈兵。正如张瑞敏所说&#xff0c;供应链管理最重要的理念就是企业的核心业务和竞争力。” 近年来&#xff0c;海尔已经有十几个成功的案例进入哈佛大学、洛桑国际管理学院、欧洲工商管理学院、日本神户大学等著名…

计算机专业笔试题,海尔计算机类笔试题

1.计算机在其发展过程中&#xff0c;经历了()等阶段。 A)机械计算机、电子计算机B)电动计算机、电子计算机C)机械计算机、电动计算机、电子模拟计算机、电子数字计算机D)电子模拟计算机、电子数字计算机 2.CPU主频和速度的关系是 A)主频越高&#xff0c;速度越快B)主频越高&…

海尔智家赴港IPO,白电巨头们的资本博弈

配图来自Canva 近日&#xff0c;海尔智家股份有限公司向港交所主板递交上市申请&#xff0c;中金公司及摩根大通为联席保荐人。 在此之前&#xff0c;海尔智家已完成在上海证券交易所及德国法兰克福交易所的上市&#xff0c;其前身为青岛海尔股份有限公司&#xff0c;其大家电…

SWIG介绍和使用

官网&#xff1a;https://www.swig.org/ github&#xff1a;https://github.com/swig SWIG 是一种软件开发工具&#xff0c;可将用 C 和 C 编写的程序与各种高级编程语言连接起来。 SWIG 与不同类型的目标语言一起使用&#xff0c;包括常见的脚本语言&#xff0c;如 Javascri…

色彩空间(CIE色度图,SRGB,AdobeRGB...)

色彩空间基础&#xff1a;https://zhuanlan.zhihu.com/p/24214731 色彩空间的表示和转换&#xff1a;https://zhuanlan.zhihu.com/p/24281841

【色彩管理】色彩管理之黑色分解

00. 目录 文章目录 00. 目录01. 概述02. 控制界面03. 黑色分解检测图04. 预留05. 附录 01. 概述 此功能用于黑色状态不好&#xff0c;黑色有拉丝、断墨、偏色等情况时&#xff0c;使用部分三色灰代替黑色出墨&#xff0c;从而掩盖掉黑色的问题&#xff0c;在点击打印界面高级选…
最新文章