【T】分治与倍增

分治，分而治之，其中最经典的便是二分

一、二分

一种经典而且非常好用的思想
将原问题对半转换成两个问题，子问题又继续转换成两个问题，许多子问题会很显然对答案没有关系，所以能讲原本O(n)的东西转化为O(logn)
但一般有个条件：单调

（之前讲的快速幂其实也用到的是这类思想）

经典讲法：猜数字

现在有个1-100的数字让你猜，每次会回答你猜的大了还是小了，尽量用最少次数猜出答案
二分实现：每次猜中间的数，然后缩小一般的区间重复操作

#include<bits/stdc++.h>
using namespace std;
int x,a;
int main()
{srand(time(0));x=rand()%100+1;//x为1-100printf("猜1-100的某个数\n");while(scanf("%d",&a)){if(a>x)printf("猜大了\n");if(a<x)printf("猜小了\n");if(a==x){printf("**对了**\n");return 0;}}
}

P2249 【深基13.例1】查找

这个数列是单调不减，所以可以直接用二分来找

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],x;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){scanf("%d",&x);/*int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意-aif(x!=a[ans]) printf("-1 ");//没有，输出-1虽然可以用这个自带函数，但我们这里学的是思想，二分思想很重要*/int l=1,r=n,mid;while(l<r){mid=(l+r)>>1;if(x<=a[mid])r=mid;else	     l=mid+1;//等号可能要多思考一下,+1也要思考下}if(a[l]==x)printf("%d ",l);else	   printf("-1 ");}
}

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

熟悉一下实数版二分，有时判断的时候可能需要一个eps=1e-3用来辅助判断，因为实数精度 判断有时可能不太准确

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double f(double x)
{return a*x*x*x+b*x*x+c*x+d;
}int main()
{scanf("%lf%lf%lf%lf",&a,&b,&c,&d);for(int i=-100;i<100;i++){double l=i,r=i+1,mid;if(f(l)==0){printf("%.2lf ",l);continue;}if(f(l)*f(r)<0){while(r-l>=0.001){mid=(l+r)/2;if(f(mid)*f(l)<=0)r=mid;else			  l=mid;//printf("[%.2lf,%.2lf](%lf)\n",l,r,f(l));}printf("%.2lf ",l);}//l为答案}
}

P2678 跳石头

二分答案，再学会check对于mid是否成立
需要想到问题对于答案是个单增的，如果mid成立，则>mid也都成立

三分

一般处理单峰函数，不常用的板子
可以看到三分板子题解全在叫你用一堆什么随机算法，单峰函数也不常见，反而随机算法各种题说不定还能对

二、倍增

分治是把问题分开解决，而倍增是从成倍整合解决

ST表

预处理$2^0$步转移，然后$2^1-2^{20}$步分别由之前步整合得到

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int bz[N][20],lg[N];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&bz[i][0]);for(int j=1;j<=18;j++)for(int i=1;i<=n;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 p=log2(r-l+1);printf("%d\n",max(bz[l][p],bz[r-(1<<p)+1][p]));}
}

练习：P1816 忠诚

树上倍增->LCA最近公共祖先

等会建图啊，树相关啊，再回来看(讲），有空的可以先看看学学

#include<bits/stdc++.h>
using namespace std;
const int N=1000009;
int n,q,x,y,nex[N*2],first[N*2],to[N*2],tot=0;
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 i=0;i<=19;i++) //预处理出从某个点跳 2 的 i 次方到达的位置f[u][i+1]=f[f[u][i]][i];for(int e=first[u];e;e=nex[e]) //枚举每一条与 u 相连的点{int v=to[e];if(v==father) 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 i=20;i>=0;i--) //使它们俩跳至深度相同{if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x; //属于 x、y 在一条链上，y 是 x 和 y 的最近公共祖先}for(int i=20;i>=0;i--) //在 x 和 y 深度相同的情况下if(f[x][i]!=f[y][i]) //目标位置不相等，x 和 y 就往上爬{x=f[x][i]; //x 往上爬y=f[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 i=1;i<n;i++){scanf("%d%d",&x,&y);Add(x,y);}Init(st,0); //预处理for(int i=1;i<=q;i++){scanf("%d%d",&x,&y);printf("%d\n",Lca(x,y));}return 0;
}