Contents
二分
二分查找
二分查找必须在有序（单调）的序列中进行。
每次折半搜索，复杂度为O(\log n)，可以在有序的序列中快速找到需要查找的值（的位置）。
二分答案
假设有函数f(x)表示某个受x影响的状态是否能实现，那么如果x越大或越小时，越难满足条件，则其满足单调性，可以使用二分答案求解
假设此满足单调性的f(x)的函数图像为1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0（1代表能实现，0代表不能实现），那么我们的任务就是找到0前面的那个1（不是在开车），使用二分可以在\log n的时间内实现快速求解。
怎么二分：我们要枚举的就是答案，即题目需要求出的值，然后依据题干定出上下界，然后在这一范围内实现二分，再通过这个答案是否能满足题意来重新划分上下界，然后一步步缩小范围，最后求出答案。
例题：P2678 跳石头
跳石头这道题显然满足单调性和有界性，可以用二分答案求解
枚举题目要求的最短跳跃距离，思考：最短跳跃距离越大，需要挪走的石头越多，这显然满足单调性，又由于能挪走的石头有一个上限M，因此可以使用二分答案进行求解。
求解时从区间[1,L]开始二分，取中点mid，然后开始模拟跳石头，如果下一个石头离上一个石头的距离小于了取的mid，则说明这块石头应该被挪走，计数器cnt加一
如果中途时cnt大于了M，说明需要挪走的石头数量超过了上限，即mid取的过大，方案不可行，接下来就继续二分[1,mid-1]，一步步缩小二分的范围。
同理，如果结束时cnt\leq M，说明该方案可行，但是可能不是最优解，mid还可以取更大，因此继续二分[mid,L]，依次求解。
到最后如果到了区间[l,r]且l=r，说明已经找到了最优解，输出即可。
#include <cstdio>
int L,n,m,d[50005];//见题意
bool judge(int x)
{
int cnt=0;//表示需要挪多少块石头
int now=0,i=0;//now表示当前人在的石头标号，i表示当前处理的石头标号
while(i<n+1)//注意是n+1
{
++i;
if(d[i]-d[now]<x)//如果两块石头中间的距离小于需要查找的mid值
cnt++;
else
now=i;
}
return cnt<=m;//返回判断结果
}
int binary()//二分答案
{
int l=1,r=L;//表示二分边界
int ans;//当前答案
while(l<=r)//当l<=r的时候
{
int mid=l+r>>1;//用位运算更快？？？
if(judge(mid))//如果这个满足条件
ans=mid,l=mid+1;//那么把它存下来，更新二分边界
else//如果不满足条件的话
r=mid-1;//mid取太大了，更新二分边界
}
return ans;//返回答案
}
int main()
{
scanf("%d %d %d",&L,&n,&m);
d[0]=0;
for(int i=1;i<=n;i++) scanf("%d",d+i);
d[n+1]=L;
printf("%d\n",binary());
return 0;
}
实数二分
一般问题：已知函数单调上升，求函数零点。
进行实数二分时记得定义eps（是一个很小的double数）由于浮点误差，使用eps可以避免判断相等时一直等不了的尴尬
例题：P1024
#include <cstdio>
#define EPS 0.001
using namespace std;
double a,b,c,d;
double f(double x)
{
double ans=a*x*x*x+b*x*x+c*x+d;
return ans;
}
void binary(double l,double r)
{
while(r-l>EPS)
{
double mid=(r+l)/2;
if(f(mid)==0)
{
printf("%.2lf ",mid);
return;
}
if(f(r)==0)
{
printf("%.2lf ",r);
return;
}
double ansl=f(l)*f(mid),ansr=f(mid)*f(r);
if(ansl<0)
{
r=mid;
continue;
}
else if(ansr<0)
{
l=mid;
continue;
}
}
printf("%.2lf ",l);
}
int main()
{
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
for(int i=-100;i<=99;i++)//先在[-100,100]中逐个枚举
{
if(f(i+1)==0){printf("%.2lf ",i+1.0);continue;}//如果直接满足岂不美哉
else if(f(i)*f(i+1)<0)//如果f(x1)<f(x2)，且f(x1)*f(x2)<0，则零点必然在(x1,x2)中间
binary(i,i+1.0);//开始二分
}
return 0;
}
三分
三分法可以用来求单峰函数的峰值。
具体做法：先在整个区间中将区间划为三份，就会存在两个划分点a,b，假设待划分的区间为[l,r]，如果a>b，则函数的峰值一定在[l,b]中，继续三分；
反之如果 a
额当a=b的话怎么办呢，说明峰值一定是在[a,b]中。
当然这题也可以求导找导函数的零点然后他就变成二分了
#include <cstdio>
#include <iostream>
#define eps 1e-6//做浮点数的题的时候记得定义eps防止浮点误差
using namespace std;
int n;
double k[15];
double l, r;
double ksm(double base, int p)//快速幂
{
double ans = 1;
for (; p; p >>= 1)
{
if (p & 1)
ans *= base;
base *= base;
}
return ans;
}
double f(double x)//求函数值用的
{
double ans = 0;
for (int i = 0; i <= n; i++)
{
double tmp = k[i] * ksm(x, i);
ans += tmp;
}
return ans;
}
void search()//三分函数
{
while (r - l > eps)//当左右端点不重合时
{
double a, b;
double t = (r - l) / 3;
a = l + t;//构造a和b
b = r - t;
if (f(a) >= f(b))//如果f(a)>f(b)，则峰值一定在[l,b]
{
r = b;
continue;
}
else if (f(a) < f(b))//峰值一定在[a,r]
{
l = a;
continue;
}
}
printf("%.5lf", l);//输出答案
}
int main()
{
cin >> n >> l >> r;
for (int i = n; i >= 0; i--)
cin >> k[i];
search();
return 0;
}
STL
提供upper_bound()和lower_bound()函数
贪心
贪心，就是只从局部考虑，局部优则采用该策略，不考虑总体情况。
贪心不一定能得到最优解，贪心的正确性需要证明虽然窝不会证，考试的时候也不是很必要证。
例题：P1090
这个贪心很好想，只需要每次都将最小的两堆合并即可。类似的问题还有饮水机接水等等
一道例题：给定n，让你钦定一个参数T，有两种操作A:T，B:\displaystyle\frac{n}{T}，使得操作的时间最短。
答案：当T=\sqrt{n}的时候最短，为什么
均值不等式
a^2+b^2\geq2ab\
a+b\geq2\sqrt{ab}\quad(a,b>0)
并且仅当a=b时取得最小值
证明：
\begin{aligned}
(a-b)^2&\geq0\
a^2+b^2-2ab&\geq0\
\therefore a^2+b^2&\geq2ab\
\end{aligned}
令a_1=\sqrt{a},b_1=\sqrt{b}，
\begin{aligned}
\because a_1^2+b_1^2&\geq 2a_1b_1\
\therefore a+b&\geq 2\sqrt{ab}
\end{aligned}
我们需要T+\displaystyle\frac{n}{T}最小，就使T=\sqrt{n}即可。
排序不等式
又一道例题：钦定一个长度为n的排列a，使得
1\cdot a_1+2\cdot a_2+3\cdot a_3+\cdots+n\cdot a_n
最小/最大
答案：当a=1,2,3….时最大，当a=n,n-1…时最小
排序不等式：顺序和\geq乱序和\geq逆序和
求证：a^3+b^3+c^3\geq a^2b+b^2c+c^2a
证明：记序列{x}=a,b,c，{y}=a^2,b^2,c^2，由排序不等式得正序和大于乱序和，证毕。
数据结构2
堆
堆是一棵完全二叉树，每个节点拥有一个key，父亲节点的key一定大于两个儿子节点
堆的查询：堆只能查询堆顶，返回其key即可
堆的插入
核心思想：修复，直接将需要插入的元素摆在堆尾，然后修复堆
如何修复：如果它的key值大于父亲节点的，交换之，递归执行知道它的key值小于父亲节点为止
堆的删除
核心思想：修复，只能删除顶节点
直接将其与末尾节点交换，然后修复之。
如何修复：交换后找一个最大的儿子节点，交换之，递归执行直到修复完毕为止。
细节
堆式存储：直接利用数组来存
根据完全二叉树的性质，一个节点的左儿子的编号是该节点的编号乘2（使用<<1加快运算），右儿子的编号是左儿子的编号+1（使用|1加快速度），父节点的编号就是除以二向下取整（使用>>1加快速度）
#define LE(x) ((x)<<1)
#define RT(x) (((x)<<1)|1)
#define DAD(x) ((x)>>1)
struct heap{
int w[100005];
int tot;
heap()
{
memset(w,0,sizeof(w));
tot=0;
}
int top()
{
return w[1];
}
void modify(int x)
{
if(x==1) return;
if(w[x]>w[DAD(x)])
swap(w[x],w[DAD(x)]),modify(DAD(x));
}
void push(int key)
{
w[++tot]=key;
modify(tot);
}
void repair(int x)
{
int tar=w[LE(x)]>w[RT(x)]?LE(x):RT(x);
if(w[x]<w[tar])
{
swap(w[x],w[tar]);
repair(tar);
}
}
void pop()
{
swap(w[1],w[tot]);
w[tot--]=0;
repair(1);
}
}h;
堆排序
利用堆满足堆顶最大/小的性质，可以利用堆进行排序，由于堆是一棵完全二叉树，每次修改的复杂度为O(\log n)，因此排序的总复杂度为O(n\log n)。
将所有元素压入堆顶，然后依次弹出，弹出的就一定会有序（有些时候这个东西会比快速排序快）
int a[100005];
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
h.push(x);
}
for(int i=n;i>=1;i--)
{
a[i]=h.top();
h.pop();
}
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
STL的优先队列
嗯，我们一般都不手写堆的
优先队列，priority_queue定义在<queue>中，默认是大根堆，可以改成小根堆。
priority_queue<int> q1;//大根堆
priority_queue<int, vector<int>, greater<int> > q2;//小根堆
支持结构体，需要重载结构体的小于号。
支持的常用操作：
q.push(x);//插入x
q.pop();//删除堆顶
q.top();//返回堆顶元素的值
留言