二分基础模型

二分端点

• 二分左端点

int l=1,r=n;
  while(l<r)
  {
  int mid=l+r>>1; //中间位置
  if(a[mid]>=x) r=mid; //符合判断条件答案一定在mid或者mid左边
  else l=mid+1; //答案一定在mid右边
  }

• 二分右端点

int l=1,r=n;
while(l<r)
{
    int mid=l+r+1>>1; //当l=mid的时候需要加1 
    if(a[mid]<=x) l=mid; //判断符合条件答案一定在mid或mid右边 
    else r=mid-1; //答案一定在mid左边 
    }

以上两种写法循环结束时l==r,

需要记住当判断结束以后l=mid,那么我们在二分的时候一定要+1防止死循环

实数二分

double l=-1000,r=1000;
while(r-l>1e-9){
	double mid=(l+r)/2.0;
	if(mid*mid*mid<x) //满足条件
	{
		l=mid;
	}
	else r=mid;
}

实数二分不存在死循环或者是上取整的问题，一般来说，如果题目要求n位小数，那么我们保留精度到n+2即可。

二分答案基础模型

//越大越好
bool check(int x)
{
    //使用x进行判断
    //返回是否符合要求

}
while(l<r)
{
    int mid=(l+r)/2;
    if(check(mid))
    {
        r=mid;
    }
    else
   {
        l=mid+1;
    }
}

//越小越好
bool check(int x)
{
    //使用x进行判断
    //返回是否符合要求

}
while(l<r)
{
    int mid=(l+r+1)/2;
    if(check(mid))
    {
        l=mid;
    }
    else
   {
        r=mid-1;
    }
}

标准模板库二分

int k=lower_bound(a,a+n,x)-a;
在a[0]到a[n-1]中找到大于等于x的最小位置
int k=upper_bound(a,a+n,x)-a;
在a[0]到a[n-1]中找到大于x的最小位置

高精度算法

使用数组模拟竖式运算

高精度加法

//逆序储存
for(int i=0,j=s1.size()-1;j>=0;i++,j--) //翻转第一个数 
{
    a[i]=s1[j]-'0'; 
}   
for(int i=0,j=s2.size()-1;j>=0;i++,j--) //翻转第二个数 
{
    b[i]=s2[j]-'0';
}
int t=0; //表示进位 
for(int i=0;i<=lenc;i++)
{
    t=t+a[i]+b[i];
    c[i]=t%10;
    t/=10;
}
while(lenc>0&&c[lenc]==0) lenc--; //去掉前导0

高精度减法

//逆序 
for(int i=0,j=lena-1;j>=0;i++,j--)
{
    a[i]=s1[j]-'0';
}
for(int i=0,j=lenb-1;j>=0;i++,j--)
{
    b[i]=s2[j]-'0';
}
int t=0; //借位 
for(int i=0;i<lenc;i++) //从低位到高位处理每位 
{
    c[i]=a[i]-b[i]+t;
    if(c[i]<0) //需要借位 
    {
        c[i]+=10;
        t=-1;
    }
    else //清除之前的借位 
    {
        t=0;
    }
}
while(lenc>0&&c[lenc]==0) //去除前导0 
{
    lenc--;
}

大整数乘以整数

//逆序储存第一个数 
for(int i=0,j=lena-1;j>=0;i++,j--)
{
	a[i]=s1[j]-'0';
}
for(int i=0;i<lena;i++) //计算 
{
	c[i]=a[i]*b;
}
for(int i=0;i<lenc;i++) //处理进位 
{
	c[i+1]+=c[i]/10;//处理当前位进位
	c[i]=c[i]%10; 
}
while(lenc&&c[lenc]==0) lenc--; //去除前导0

大整数乘以大整数

//逆序储存 
for(int i=0,j=lena-1;j>=0;i++,j--)
{
    a[i]=s1[j]-'0';
}
for(int i=0,j=lenb-1;j>=0;i++,j--)
{
    b[i]=s2[j]-'0';
}
//模拟竖式乘法 
for(int i=0;i<lena;i++)
{
    for(int j=0;j<lenb;j++)
    {
        c[i+j]=c[i+j]+a[i]*b[j];
    }
}
//处理进位 
for(int i=0;i<lenc;i++) 
{
    c[i+1]=c[i+1]+c[i]/10;
    c[i]=c[i]%10;
}
//去除前导0 
while(lenc>0&&c[lenc]==0)
{
    lenc--;
}

大整数除以整数

//正序储存 
for(int i=0;i<s.size();i++) 
{
	a[i]=s[i]-'0';
}
int t=0; //余数 
for(int i;i<s.size();i++) //模拟竖式除法 
{
	t=t*10+a[i];
	c[i]=t/b;
	t%=b;
}
reverse(c,c+lenc); //翻转商数组 
while(lenc>0&&c[lenc]==0) //去除前导0 
{
	lenc--;
}

stl常用结构

动态数组

vector<int> v;             //声明一个动态数组
vector<int> v(n,3)         //初始化一个长度为n的动态数组,每个数值是3
v.size()                   //返回动态数组大小
v.empty()                  //返回动态数组是否为空
v.clear()                  //清空数组 
v.front()                  //动态数组第一个元素 等价于v[0]
v.back()                   //动态数组最后一个元素 等价于v[v.size()-1] 
v.push_back(x)             //在动态数组最后插入一个元素x
v.pop_back()               //删除动态数组的最后一个元素
v.begin()                  //动态数组的开始位置
v.end()                    //动态数组的结束位置的下个位置 
v.resize(n,m)              //重新调整数组大小为n.如果n比原来大，则新增的部分都初始化为m。
  
vector<int> g[100]         //声明100个动态数组 
遍历形式

for(int i=0;i<v.size();i++) //下标访问 
{
	cout<<v[i]<<" ";	
} 
for(vector<int>::iterator it=v.begin();it!=v.end();it++) //迭代器访问 
{
	cout<<(*it) 
}
for(auto x:v)                  //泛型遍历 
{
	cout<<x<<" ";
}
sort(v.begin(),v.end())        //对动态数组进行排序
reverse(v.begin(),v.end())     //对动态数组整个翻转
reverse(v.begin(),v.begin()+2) //对动态数组的v[0]到v[1]进行翻转 

v.erase(unique(v.begin(),v.end()),v.end());
//对有序数组进行去重

struct Stu{
	string name;
	int sc;
}; 
vector<Stu> v;                   //声明结构体类型的动态数组

键值对(哈希表)

map 字典(键值对,键只能出现一次) 
map<string,int>          //声明一个键为字符串，值为整数的数据类型
h[x]=t                   //在h中插入一个键为x，值为t的元素 
h.size()                 //返回map中的元素个数
h.count(x)               //统计x在h中出现的次数
h.erase(x)               //删除h中的x
h.find(x)                //找到x在h中出现的地址
h.empty()                //判断h是否为空
h.begin()                //map的起点位置
h.end()                  //map最后一个位置的下个位置

遍历
for(auto x:h)
{
	cout<<x.first<<" "<<x.second;
	      //键           值 
} 

set 集合(每个元素只会出现一次) 
set<int> s;             //声明一个int类型的集合
s.insert(x)             //在集合中插入元素x 
s.size()                //返回集合的元素个数
s.count(x)              //判断x是否在集合之中出现过
s.erase(x)              //在集合s中删除元素x
s.find(x)               //得到x出现在s中的地址
s.empty()               //判断s是否为空 
s.begin()               //起点地址
s.end()                 //终点地址

遍历 
for(auto x:s)
{
	cout<<x;	
} 
map和set插入元素以后按照从小到大排序，大部分超过logn
multimap,multiset 支持元素重复
unordered_map,unordered_set,unordered_multimap,unordered_multiset和上面类似，插入后不会排序

链表

list<int> l       //声明一个链表l
l.push_back(x)    //在链表尾插入一个元素x
l.pop_back()      //删除链表最后一个元素
l.push_front(x)   //在链表头插入元素x
l.pop_front()     //在链表头删除一个元素

                  //某个元素的位置pos可以通过l.begin()+k得到

l.insert(pos,x)   //在pos位置前插入元素x,返回新数据的位置
l.insert(pos,n,x) //在pos位置前插入n个元素x,无返回值
l.clear()         //清空链表
l.erase(beg,end)  //删除[beg,end)的数据，返回删除数据后的下个位置
l.erase(pos)      //删除pos位置的数据，返回下个数据的位置  
l.erase(x)        //删除容器中所有和x匹配的元素

l.front()         //第一个元素
l.back()          //最后一个元素
l.reverse()       //翻转链表 
list.sort()       //从小到大排序

队列

队列是一种先进先出的结构
queue<int> q; //声明一个整数类型的队列
q.push(x) ;   //将元素插入队尾
q.pop();      //删除队头
q.size();     //获取队列元素个数
q.front();    //获取队头元素


数据模拟队列
int hh=0,tt=-1;//队头和队尾
q[++tt]=x;     //加入队列
hh++;          //删除队头
tt-hh+1        // 队列之中元素个数 


优先队列
priority_queue<int> q;//大根堆
priority_queue<int,vector<int>,greater<int> > q;  //小根堆

要使用结构体的小根堆，如果是涉及到排序，需要重载小于符号

struct Stu{
	int id;
	string name;
	bool ooperator<(const Stu &s)const
	{
		return id>s.id;
	}
}; 


deque<int> q;    //声明一个双端队列 
q.pop_back()     //从队尾删除
q.pop_front()    //从队头删除
q.push_front(x)  //从队头添加
q.push_back(x)   //从队尾添加

栈

栈是一种先进后出的数据结构
stack<int> stk;          //声明一个整数类型的栈 
stk.push(x);             //栈顶加入元素x
stk.pop();              //删除栈顶元素
stk.size();             //获取栈中的元素个数
stk.top();              //获取栈顶元素

数组模拟栈
int tt=0;               //栈顶 
q[++tt]=x;              //将元素x加入栈中
tt--;                   //删除栈顶元素

//初始化括号匹配 
map<char,int> h={{'{',1},{'[',2},{'(',3},{'<',4},{'>',5},{')',6},{']',7},{'}',8}};