提供广州网站建设,利趣网站开发商,广州做网站优化公司报价,北京网站建设服务器维护分治#xff0c;分而治之#xff0c;其中最经典的便是二分
一、二分
一种经典而且非常好用的思想 将原问题对半转换成两个问题#xff0c;子问题又继续转换成两个问题#xff0c;许多子问题会很显然对答案没有关系#xff0c;所以能讲原本O(n)的东西转化为O(logn) 但一般…分治分而治之其中最经典的便是二分
一、二分
一种经典而且非常好用的思想 将原问题对半转换成两个问题子问题又继续转换成两个问题许多子问题会很显然对答案没有关系所以能讲原本O(n)的东西转化为O(logn) 但一般有个条件单调
之前讲的快速幂其实也用到的是这类思想
经典讲法猜数字
现在有个1-100的数字让你猜每次会回答你猜的大了还是小了尽量用最少次数猜出答案 二分实现每次猜中间的数然后缩小一般的区间重复操作
#includebits/stdc.h
using namespace std;
int x,a;
int main()
{srand(time(0));xrand()%1001;//x为1-100printf(猜1-100的某个数\n);while(scanf(%d,a)){if(ax)printf(猜大了\n);if(ax)printf(猜小了\n);if(ax){printf(**对了**\n);return 0;}}
}P2249 【深基13.例1】查找
这个数列是单调不减所以可以直接用二分来找
#includebits/stdc.h
using namespace std;
int n,m,a[1000005],x;
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);}for(int i1;im;i){scanf(%d,x);/*int anslower_bound(a1,an1,x)-a;//二分搜注意-aif(x!a[ans]) printf(-1 );//没有输出-1虽然可以用这个自带函数但我们这里学的是思想二分思想很重要*/int l1,rn,mid;while(lr){mid(lr)1;if(xa[mid])rmid;else lmid1;//等号可能要多思考一下,1也要思考下}if(a[l]x)printf(%d ,l);else printf(-1 );}
}P1024 [NOIP2001 提高组] 一元三次方程求解
熟悉一下实数版二分有时判断的时候可能需要一个eps1e-3用来辅助判断因为实数精度 判断有时可能不太准确
#includebits/stdc.h
using namespace std;
double a,b,c,d;
double f(double x)
{return a*x*x*xb*x*xc*xd;
}int main()
{scanf(%lf%lf%lf%lf,a,b,c,d);for(int i-100;i100;i){double li,ri1,mid;if(f(l)0){printf(%.2lf ,l);continue;}if(f(l)*f(r)0){while(r-l0.001){mid(lr)/2;if(f(mid)*f(l)0)rmid;else lmid;//printf([%.2lf,%.2lf](%lf)\n,l,r,f(l));}printf(%.2lf ,l);}//l为答案}
}P2678 跳石头
二分答案再学会check对于mid是否成立 需要想到问题对于答案是个单增的如果mid成立则mid也都成立
三分
一般处理单峰函数不常用的板子 可以看到三分板子题解全在叫你用一堆什么随机算法单峰函数也不常见反而随机算法各种题说不定还能对
二、倍增
分治是把问题分开解决而倍增是从成倍整合解决
ST表
预处理 2 0 2^0 20步转移然后 2 1 − 2 20 2^1- 2^{20} 21−220步分别由之前步整合得到
#includebits/stdc.h
using namespace std;
const int N1e510;
int n,m;
int bz[N][20],lg[N];
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,bz[i][0]);for(int j1;j18;j)for(int i1;in;i)if(i(1(j-1))n)bz[i][j]max(bz[i][j-1],bz[i(1(j-1))][j-1]);//重点精髓语句int l,r;while(m--){scanf(%d%d,l,r);int plog2(r-l1);printf(%d\n,max(bz[l][p],bz[r-(1p)1][p]));}
}练习P1816 忠诚
树上倍增-LCA最近公共祖先
等会建图啊树相关啊再回来看(讲有空的可以先看看学学
#includebits/stdc.h
using namespace std;
const int N1000009;
int n,q,x,y,nex[N*2],first[N*2],to[N*2],tot0;
int f[N][21],dep[N];
void Add(int u,int v) //建邻接表
{nex[tot]first[u];first[u]tot;to[tot]v;nex[tot]first[v];first[v]tot;to[tot]u;
}
void Init(int u,int father) //预处理father 是 u 的父节点
{dep[u]dep[father]1;for(int i0;i19;i) //预处理出从某个点跳 2 的 i 次方到达的位置f[u][i1]f[f[u][i]][i];for(int efirst[u];e;enex[e]) //枚举每一条与 u 相连的点{int vto[e];if(vfather) continue; //如果这条连向父节点就 continue f[v][0]u; //v 的父亲是 u Init(v,u); //递归}
}
int Lca(int x,int y) //找 LCA
{if(dep[x]dep[y]) swap(x,y); //保证 x 深度更大for(int i20;i0;i--) //使它们俩跳至深度相同{if(dep[f[x][i]]dep[y]) xf[x][i];if(xy) return x; //属于 x、y 在一条链上y 是 x 和 y 的最近公共祖先}for(int i20;i0;i--) //在 x 和 y 深度相同的情况下if(f[x][i]!f[y][i]) //目标位置不相等x 和 y 就往上爬{xf[x][i]; //x 往上爬yf[y][i]; //y 往上爬}return f[x][0]; //最后肯定一起跳到了 lca 的下面一个
}
int dist(int x,int y){return dep[x]dep[y]-2*dep[Lca(x,y)];} //求距离
int main()
{scanf(%d,n);scanf(%d,q);int st;scanf(%d,st);for(int i1;in;i){scanf(%d%d,x,y);Add(x,y);}Init(st,0); //预处理for(int i1;iq;i){scanf(%d%d,x,y);printf(%d\n,Lca(x,y));}return 0;
}
