1.二分查找的原则
- 当要查找的值target>mid 就在mid和right中查找
- 当要查找的值target<mid就在left和mid中查找
对于边界条件的处理：
while(l<r)
mid的取值是[l,r)
重点是下面部分，直接决定使用哪个二分模板。
1.3 中间值归属问题
这个问题其实比较灵活，这里我只讨论3种情况，其余情况类似。假设有序数组为int[] nums，求解的是索引，根据题目要求分为3种情况：
情况一
假设我们要搜索的是大于6的最小值索引，如果num[mid] <= 6，那么这个mid一定不是目标索引，此时left = mid + 1（因为mid位置的值比目标值还小，而我们找的元素肯定大于目标值），如果如果num[mid] > 6，此时的mid是有可能是目标索引的，所以令right = mid；
情况二
假设我们要搜索的是小于6的最大值索引，如果num[mid] >= 6，那么这个mid一定不是目标索引，此时right = mid - 1（因为mid位置的值比目标值还大，而我们找的元素肯定小于目标值），如果如果num[mid] < 6，此时的mid是有可能是目标索引的，所以令left = mid；
情况三（最简单）
假设我们要搜索的是等于6的索引，如果num[mid] > 6，那么这个mid一定不是目标索引，此时right = mid - 1；如果如果num[mid] < 6，此时的mid也肯定不是目标索引，所以令left = mid + 1；如果num[mid] == 6，那就找到啦；
情况一：
while(l<r){
int mid = l+r >>1;
if(check(mid)) r= mid; //往小收缩
else l= mid+1;
}
cout<<l;
情况二、三：
while(l<r){
int mid = l+r+1 >>1;
if(check(mid)) l = mid;//往大扩张
else r= mid-1;
}
cout<<l;
2.DAG图的拓扑排序
DAG图：有向无环图
简单的拓扑排序就是：找到任意一个入度为0的点，将它删除，和它相连的边也删除。这样反复做，如果最后的图能删光，不留点和边，则可以生成一个拓扑序列，否则不能生成。
具体实现是用queue存储入度为0的点，当处理一个queue中的点时，将它链接的点的入度分别-1，如果有相连的点的入度变成0了，就将这个点放入queue。最后queue为空时进行最终的判断。
扩展：DAG中找路径条数，长度不限制 场景：食物链计数
方法：伪dp
//拓扑排序板子
//邻接表方法：
int n,m;
int h[5000005],ru[5000005],chu[5000005],f[5000005];
int tot;
int ans;
struct node{
int v,nxt;
}d[5000005];
queue<int>q;
void add(int u,int v){
d[++tot].v = v;
d[tot].nxt = h[u];
h[u] = tot;
}
void tpsort(){
for(int i=1;i<=n;i++){
if(ru[i]==0){
q.push(i);
f[i]++;//入度为0即为最弱的一个点，所以f[i]=1;
}
}
while(!q.empty()){
int p = q.front();
q.pop();
for(int i=h[p];i;i=d[i].nxt){
int to = d[i].v;
f[to] = (f[to]+f[p])%mod;
ru[to]--;
if(ru[to]==0){
q.push(to);//将入度为0的点作为起始点。
}
}
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
ru[b]++;
chu[a]++;
}
tpsort();
for(int i=1;i<=n;i++){
// debug(ans);
if(chu[i]==0) ans = (ans+f[i])%mod;
}
cout<<ans<<endl;
}
3.链式向前星
设置三个数组:
head[u] 表示以u作为起点的第一条边的编号
nxt[cnt] 表示以cnt为边的下一条边。这条边和cnt同起点。
to[cnt] 表示编号为cnt的边的终点。
初始时令head[u] = cnt =0;表示尚未有边，每个点都是孤立点。
当加入一条新边e[u,v]时，
- cnt++
- nxt[cnt] = head[u] ;将原来以u作为起点的第一条边，作为该边的后续边。
- to[cnt] = v; 当前边的终点位置
//不带权
void add(int u,int v)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
//带权
void add(int u,int v,int w)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
val[cnt]=w;
}
//遍历
for(int i=head[u];!i;i=nxt[i]) //广度遍历
{
int v=to[i];
//其他操作
}
//删边 删去一条边【u,vv】
int last=0;
for(int i=head[u];!i;i=nxt[i])
{
int v=to[i];
if(v==vv)
{
if(i==head[u]) head[u]=nxt[i];
else nxt[last]=nxt[i];
break;
}
last=i;
}