跳转至

二分

二分编号

对于一个有单调性的数组,我们可以二分编号,如果a[mid]<ans,那么mid就往a[]更大的那边走

while(r>l){
    mid=(l+r)/2;
    if(judge(mid))l=mid;
    else r=mid;
}

注意二分代码的写法细节和你的check函数有关！（其实是和你在对于恰好满足要求时check返回值有关）

二分答案

二分答案思路:二分一个猜测的答案mid,进行判定,如果计算出真正的答案q不能达到此mid(a-mid<0)mid就变小(mid=l)

否则mid=r

下面是实数域的二分答案。如果只是整数域，则和上面的无异（参考https://www.luogu.com.cn/problem/P1873）。

double l=?,r=?,mid;
while(r-l>=0.00001){
    mid=(l+r)/2;
    if(sum(mid)>=0)l=mid;
    else r=mid;
}

无论何种二分,请明确二分的上下界(l,r的初始值)

二分模板，可用。

int l=0,r=mxd;
    while(l<=r){
        int mid=l+r>>1;
        if(judge(mid))l=mid+1;
        else r=mid-1;
    }
    cout<<r<<endl;

wqs 二分

WQS二分，全称为Wang Qifan's Binary Search，是一种基于二分搜索的算法技巧，由Wang Qifan（王崎凡）提出。它主要用于解决一类特殊的优化问题，这类问题通常包含两个部分：一个是需要优化的目标函数，另一个是满足某些条件的限制函数。WQS二分的核心思想是将限制函数的参数二分，从而在满足限制条件的前提下，寻找目标函数的最优解。

以下是WQS二分的基本步骤：

  1. 参数二分：将限制函数的参数进行二分，通常是二分一个实数参数。

  2. 评估函数：定义一个评估函数，该函数能够根据当前的参数值，计算出在满足限制条件的情况下，目标函数的某种度量（比如最大值或最小值）。

  3. 二分搜索：使用二分搜索来寻找最优的参数值，使得评估函数的值最优。

  4. 检查和调整：在每次二分搜索的过程中，检查当前参数值是否满足所有的限制条件，如果不满足，则调整参数的范围，继续进行二分搜索。 WQS二分通常用于以下类型的问题：

  5. 带限制的最优化问题：需要在满足一定条件的情况下，找到目标函数的最优解。

  6. 网络流问题：在某些网络流问题中，可以通过WQS二分来寻找最大流或最小割的优化解。

  7. 动态规划问题：在动态规划问题中，有时可以通过WQS二分来优化状态转移方程中的参数。 WQS二分的难点在于如何设计评估函数和如何处理限制条件。以下是一些关键点：

  8. 评估函数的设计：需要根据问题的具体特点设计一个有效的评估函数，该函数能够反映出参数变化对目标函数的影响。

  9. 限制条件的处理：在二分搜索的过程中，需要确保每次评估都是在满足限制条件的前提下进行的。

  10. 精度控制：由于WQS二分涉及到实数参数的二分，因此需要控制二分搜索的精度，以避免浮点数精度问题。 WQS二分是一种高级的算法技巧，它要求算法设计者有较强的数学建模能力和对问题的深刻理解。在实际应用中，WQS二分可以解决一些传统方法难以处理的问题，但它也需要根据具体问题进行适当的调整和优化。

例题 #1 Picnic Planning

题面翻译

给定一张N个点M条边的无向图，求出无向图的一棵最小生成树，满足一号节点的度数不超过给定的整数s。保证 N <= 30

题目描述

PDF

我们考虑先求出最小生成树。如果已经符合要求就直接输出。否则我们要考虑替换掉一些(1,i)边。

那么想必是要优先替换掉边权大的。那么我们是否可以把所有(1,i)边排序后二分一个前缀的边排除呢？不行，因为有一些边虽然权值很大，但是是必须的。

所以我们换一个思路。我们**将这些边的权值加上一个正系数**，这样就可以**降低选这些边的优先级**。用二分直到最小的这正系数使得满足题目要求。输出时因为选择了k条加了系数的边，所以最后答案要减去k倍的系数。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e4 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

struct edge { int x,y,z; };

map<string,int> id;
edge e[1000];
int fa[50];
int n,m,k,t;

int find(int x) { return x==fa[x] ? fa[x] : fa[x]=find(fa[x]); }
bool cmp(const edge& a, const edge& b)
{
    if(a.z+t*(a.x==1)==b.z+t*(b.x==1)) return a.x!=1;
    return a.z+t*(a.x==1)<b.z+t*(b.x==1);
}
pii kruskal()
{
    int ans=0,cnt=0;
    for(int i=1; i<=n; i++) fa[i]=i;
    sort(e+1, e+1+m, cmp);
    for(int i=1; i<=m; i++)
    {
        int fx=find(e[i].x),fy=find(e[i].y);
        if(fx==fy) continue;
        fa[fx]=fy; ans+=e[i].z;
        if(e[i].x==1) ++cnt, ans+=t;
    }
    return mp(ans, cnt);
}
int solve(int l, int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1; t=mid;
        if(kruskal().second>k)
        l=mid+1;
        else
        r=mid;
    }
    return l;
}
void work(int T)
{
    id.clear(); id["Park"]=n=1;

    cin>>m;
    for(int i=1; i<=m; i++)
    {
        string x,y;
        int z;
        cin>>x>>y>>z;
        if(!id[x]) id[x]=++n;
        if(!id[y]) id[y]=++n;
        e[i].x=id[x]; e[i].y=id[y]; e[i].z=z;
        if(e[i].x>e[i].y) swap(e[i].x, e[i].y);
    }
    cin>>k;

    t=0;
    if(kruskal().second>k) t=solve(0, 1000);
    printf("Total miles driven: %lld\n", kruskal().first-k*t);
    if(T) putchar('\n');
}
signed main()
{
    int t;
    cin>>t;
    while(t-->0) work(t);
    return 0;
}

整体二分

例题 #1 [国家集训队] 矩阵乘法

题目描述

给你一个 \(n \times n\) 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 \(k\) 小数。

输入格式

第一行有两个整数，分别表示矩阵大小 \(n\) 和询问组数 \(q\)。

第 \(2\) 到第 \((n + 1)\) 行，每行 \(n\) 个整数，表示这个矩阵。第 \((i + 1)\) 行的第 \(j\) 个数表示矩阵第 \(i\) 行第 \(j\) 列的数 \(a_{i, j}\)。

接下来 \(q\) 行，每行五个整数 \(x_1, y_1, x_2, y_2, k\)，表示一组询问，要求找到以 \((x_1, y_1)\) 为左上角，\((x_2, y_2)\) 为右下角的子矩形中的第 \(k\) 小数。

数据规模与约定

  • 对于 \(20\%\) 的数据，保证 \(n \leq 100\)，\(q \leq 10^3\)。

  • 对于 \(40\%\) 的数据，保证 \(n \leq 300\)，\(q \leq 10^4\)。

  • 对于 \(60\%\) 的数据，保证 \(n \leq 400\)，\(q \leq 3 \times 10^4\)。

  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 500\)，\(1 \leq q \leq 6 \times 10^4\)，\(0 \leq a_{i, j} \leq 10^9\)。

思路

看起来好像是使用主席树实现的，但是二维的我们有怎么实现呢？这里可以使用可持久化二维值域线段树吗？

这里我们引入一个新离线算法，叫做**整体二分**。

整体二分

整体二分是一种算法思想，通常用于解决一些特定的数据结构和算法问题。它主要用于处理序列或树形结构中的问题，通过递归地将数据集划分为两个相对等的部分，然后在每一部分独立地进行处理，最后将结果合并起来。

以下是整体二分的基本步骤：

  1. 划分：将问题规模较大的数据集划分为两个规模较小的子集。

  2. 递归处理：对每个子集递归地应用相同的处理方法。

  3. 合并结果：将子集的处理结果合并起来，形成整个数据集的处理结果。 整体二分在以下几种情况下特别有用：

  4. 离线算法：在无法即时处理查询的问题中，可以先将所有查询离线下来，然后使用整体二分的方法进行处理。

  5. 树状数组或线段树：在处理区间问题时，整体二分可以用来减少问题的规模，将大区间问题转化为小区间问题。

  6. 可并堆：在处理一些需要动态合并和分裂的数据结构问题时，整体二分可以用来优化合并和分裂的效率。 整体二分的一个典型应用是在处理离线区间修改问题时。例如，在一个数组上进行多次区间修改查询操作，整体二分可以用来高效地处理这些操作。 在使用整体二分时，通常需要注意以下几点：

  7. 确保问题可以递归地划分为两个相对等的部分。

  8. 处理子问题时，确保不会影响到其他子问题的解。

  9. 合并结果时，确保能够正确地整合子问题的解。

Code

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
// #define inr int
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

const char el='\n';
const bool enable_dbg = 0;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s << ' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

const int N = 3e3 + 5;
const int INF = 1e18;
const int M = 1e6;
const int MOD = 1e9 + 7;

struct node{
    int x,y,u,v;
    int k,id;
}q[M],q1[M],q2[M];

int tot,ans[M];
int n,m,t[N][N];


namespace ctree{

    inline int lowbit(int x){
        return x&-x;
    }

    void add(int x,int y,int v){
        for(int i=x;i<=n;i+=lowbit(i)){
            for(int j=y;j<=n;j+=lowbit(j)){
                t[i][j]+=v;
            }
        }
    }

    int query(int x,int y){
        int res=0;
        for(int i=x;i;i-=lowbit(i)){
            for(int j=y;j;j-=lowbit(j)){
                res+=t[i][j];
            }
        }
        return res;
    }
}using namespace ctree;

void solve(int l,int r,int x,int y){
    dbg(l,r,x,y,el);
    if(l>r)return ;
    if(x==y){//已经走到了一个数字上，且该数对当前区间内的操作都有贡献，那么贡献答案
        for(int i=l;i<=r;i++){
            if(q[i].id)ans[q[i].id]=x;
        }
        return ;
    }

    int len1=0,len2=0,mid=x+y>>1;
    for(int i=l;i<=r;i++){
        if(!q[i].id){
            if(q[i].k<=mid)add(q[i].x,q[i].y,1),q1[++len1]=q[i];
            else q2[++len2]=q[i];
        }else{
            int t=query(q[i].u,q[i].v)-query(q[i].x-1,q[i].v)-query(q[i].u,q[i].y-1)+query(q[i].x-1,q[i].y-1);//二维树状数组，雷雨二维前缀和，提取子矩阵
            if(t>=q[i].k)q1[++len1]=q[i];
            else q[i].k-=t,q2[++len2]=q[i];//更新后丢到右边
        }
    }

    for(int i=1;i<=len1;i++)q[l+i-1]=q1[i];
    for(int i=1;i<=len2;i++)q[l+len1+i-1]=q2[i];//重新分配所有操作
    for(int i=l;i<=l+len1-1;i++){
        if(!q[i].id&&q[i].k<=mid)add(q[i].x,q[i].y,-1);
    }

    solve(l,l+len1-1,x,mid);//注意区间下标
    solve(l+len1,r,mid+1,y);
}

void solve(){
    n=rd,m=rd;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a=rd;
            q[++tot]=(node){i,j,0,0,a,0};
        }
    }
    dbg("ok");
    for(int i=1;i<=m;i++){
        int x=rd,y=rd,a=rd,b=rd,k=rd;
        q[++tot]=(node){x,y,a,b,k,i};
    }

    dbg("ok");
    solve(1,tot,-INF,INF);
    dbg("ok");
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
}

signed main() {
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

三分

例题 #1

给定 \(n\) 个二次函数 \(f_1(x),f_2(x),\dots,f_n(x)\)（均形如 \(ax^2+bx+c\)），设 \(F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}\)，求 \(F(x)\) 在区间 \([0,1000]\) 上的最小值。

输入格式

输入第一行为正整数 \(T\)，表示有 \(T\) 组数据。

每组数据第一行一个正整数 \(n\)，接着 \(n\) 行，每行 \(3\) 个整数 \(a,b,c\)，用来表示每个二次函数的 \(3\) 个系数，注意二次函数有可能退化成一次。

虽然精度要求不高，但是eps还是要足够小！（在复杂度范围内）

注意加减eps若干倍取m1,m2会TLE

const double eps=1e-12;//精度开高！
int a[N],b[N],n,c[N];

double f(double x,int i){
    return x*x*a[i]+x*b[i]+c[i];
}
double check(double x){
    double res=f(x,1);
    for(int i=2;i<=n;i++)res=max(res,f(x,i));
    return res;
}#

signed main(){
    int T=rd;
    // cerr<<eps<<endl;
    while(T--){
        n=rd;
        for(int i=1;i<=n;i++)a[i]=rd,b[i]=rd,c[i]=rd;
        double l=0,r=INF;
        while(r-l>eps){
            double m1=l+(r-l)/3.0;
            double m2=r-(r-l)/3.0;
            if(check(m1)>check(m2))l=m1;
            else r=m2;
            // cerr<<m1<<' '<<m2<<' '<<l<<' '<<r<<endl;
        }
        // cerr<<"l="<<l<<endl;
        printf("%.4lf\n",check(l));

    }
}

二分的多种写法的边界与适用范围

itn l=1,r=n;
int res=0;
while(l<=r){
    int mid=l+r>>1;
    if(a[mid]<=k)res=mid,l=mid+1;
    else r=mid-1;
} 
return res;

上述二分代码适用于整数域，边界无误。可以求出最大的符合条件的值。

分析方法：看到if(a[mid]<=k)res=mid,l=mid+1;我们可以得出：

  • 最后的答案一定是某一个合法值

  • 如果遇到一段连续的合法值，指针会一直向右走，直到不合法。因此取的是最大的合法值。

本写法也可以适用于负数域，和上述一样。

那么会不会死循环呢？我们分析l+r>>1。在正数域上，它是向下取整。在负数域上也是向下取整。因为每次改变l,r时都比mid多偏移了1，所以不会进入死循环。

itn l=1,r=n;
int res=0;
while(l<=r){
    int mid=l+r>>1;
    if(a[mid]>=k)res=mid,r=mid-1;
    else l=mid+1;
}

这样写这是找到最小的符合要求的数。其它点没有区别。

有可能的**超时**代码二分是这样的：

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

这份代码可以被卡爆，例如某时候l=−5,r=−4,计算得到mid=(−9)/2=−4,如果check也是成立的，那么会发现l和r的值不会变化，于是就会无法跳出二分从而超时。

一种解决办法是改/2成>>1

改了之后就过了，因为/2和>>操作有差别。 右移是商向负无穷取，除是商向0取。