1.位運算

1.1.基礎(chǔ)知識

一般只考慮自然數(shù)。

在k位二進制數(shù)中，通常稱最低位為第0位，最高位為第k-1位。

1.1.1.算術(shù)位運算

與and，&：\((1010)_2 \operatorname{and} (0110)_2=(0010)_2\)。

或or，|：\((1010)_2 \operatorname{or} (0110)_2=(1110)_2\)。

非not，~，!：\(\operatorname{not}(1010)_2=(0101)_2\)。

• 在k位二進制數(shù)下，\(\operatorname{not}(x)=(2^k-1)-x\)。

  not(x)可以視作在模\(2^k-1\)意義下的-x。

• 在C++語法里，not、!的對象是布爾變量；對于有符號整數(shù)x，~x=-1-x。

異或xor，^：\((1010)_2 \operatorname{xor} (0110)_2=(1100)_2\)。

• 異或可以看作不進位加法或模2意義下加法。a^b≤a+b。

  與可以看作模2意義下乘法。

• \(x\operatorname{xor}y=z\Leftrightarrow y\operatorname{xor}z=x\Leftrightarrow x\operatorname{xor}y\operatorname{xor}z=0\)。

• 異或的加和：拆位。

• 異或適合用線性基維護。

• 要求復(fù)雜的二進制下計數(shù)問題：數(shù)位dp。復(fù)雜度=O(狀態(tài)數(shù))=O(log n)。

  \(x\operatorname{xor}y=z\Leftrightarrow x\operatorname{xor}y\operatorname{xor}z=0\)：f_{pos,l_x,l_y,l_z}：第pos位，x,y,z最高位是否有限定，的方案數(shù)。

• count(x xor y)=count(x)+count(y)-2*count(x and y)。

  當(dāng)且僅當(dāng)二進制下含奇數(shù)個1的數(shù)xor二進制下含偶數(shù)個1的數(shù)=二進制下含奇數(shù)個1的數(shù)。

• 重要性質(zhì)：位運算按位獨立。

  • 證明位運算的運算性質(zhì)只要證明對于一個數(shù)位成立，那么對于整個數(shù)都成立。
  • 拆位。

• x+y=(x&y)+(x|y)。

• x xor y=(x|y)-(x&y)。

  定義\(\bigoplus\limits_i a_i=\sum\limits_{k}[\exist i,a_i\&2^k\not=0][\exist i,a_i\&2^k=0]2^k\)，則\(\bigoplus\limits_{i}a_i=\operatorname{or}\limits_ia_i-\operatorname{and}\limits_ia_i\)。

• \(x-y\equiv x+(2^k-y)\pmod{2^k}\)。

• x是y的子集（\(x\sube y\)）\(\Leftrightarrow\)x|yy\(\Leftrightarrow\)y-x是y的子集\(\Leftrightarrow\)x&(y-x)0\(\Leftrightarrow\)y是x的超集\(\Leftrightarrow\)not(y)是not(x)的子集。

  • 推論：x是x+y的子集\(\Leftrightarrow\)y是not(x)的子集。

    證明：x是x+y的子集\(\Leftrightarrow\)not(x+y)是not(x)的子集\(\Leftrightarrow\)not(x)-not(x+y)=((2^k-1)-x)-((2k-1)-(x+y))=y是not(x)的子集。

1.1.2.移位運算

左移<<：\((10)_2<<k=(10\underbrace{\dots}_{\text{k個0}})_2\)。

右移>>：\((10\underbrace{\dots}_{\text{k個0和1}})_2>>k=(10)_2\)。

• \(1\operatorname{<<}n=2^n\)，\(n<<1=2*n\)，\(n>>1=\lfloor \dfrac{n}{2.0} \rfloor\)。

• 注意左/右移在變量類型下的位數(shù)限制。

  e.g.在int類型下，左/右移32位及以上是未定義行為。

  e.g.正確寫法：1ll<<60ll！！！錯誤寫法：1<<60。

1.1.3.機器數(shù)

對于有符號整數(shù)x，~x=-1-x。

正數(shù)原碼$(0|1010)_2 \(的反碼是其本身\)(0|1010)_2 $。

負(fù)數(shù)原碼$(1|1010)_2 \(的反碼是在其原碼的基礎(chǔ)上，符號位不變，其余位取反\)(1|0101)_2 $。

正數(shù)原碼$(0|1010)_2 \(的補碼是其本身\)(0|1010)_2 $。

負(fù)數(shù)原碼($1|1010)_2 \(的補碼是其反碼+1\)(1|0110)_2 $。

• 對負(fù)數(shù)x取反碼可類比\(x+(2^k-1)\)。

  對負(fù)數(shù)x取補碼可類比\(x+2^k\)。

任何兩個數(shù)值做加減法運算\(\Leftrightarrow\)減法看作加負(fù)數(shù)，先對兩數(shù)取補碼，再做最高位不進位的二進制加法，最后對結(jié)果取補碼。

• 可類比\(x-y=((x+2^k)\%2^k+(-y+2^k)\%2^k+2^k)\%2^k\)。

1.1.4.常用技巧

• unsigned long long（或unsigned int）發(fā)生算術(shù)溢出時相當(dāng)于自動對\(2^{64}\)（或\(2^{32}\)）取模。

• 初始化最大值const int INF=0x3f3f3f3f;和memset(a,0x3f,sizeof a);。

• 成對變換

  \(n \operatorname{xor} 1 = \begin{cases} n+1，（n為偶數(shù)）\\n-1，（n為奇數(shù)） \end{cases}\)，“0與1”、“2與3”、“4與5”……關(guān)于\(\operatorname{xor}1\)運算“成對變換”。用于鄰接表判斷反向邊。

• 滾動數(shù)組（不是求max和min時）：f[i&1]。

• 二進制拆分?jǐn)?shù)或者集合。

• 異或的加和：拆位。

1.2.lowbit\(O(1)\)

返回x二進制下“最低位的1和后邊所有0”構(gòu)成的數(shù)值

inline int lowbit(int x){
    return x&-x;  //或return x&(~x+1);
}//返回x的最后一位1

1.3.統(tǒng)計數(shù)中 1 的個數(shù)

在線求解：\(O(\log N)\)

int a,ans;

inline int lowbit(int x){
    return x&-x;  //或return x&(~x+1);
}//返回x的最后一位1

int main(){
  cin>>a;
  while(a){
    a-=lowbit(a);
    ans++;
  }
  cout<<ans<<' ';
  return 0;
}

離線預(yù)處理：\(O(N)\)

int siz[1<<N];
for(int i=0;i<=(1<<n);i++) siz[i]=siz[i>>1]+(i&1);

1.4.快速冪

1.4.1.整數(shù)域的快速冪\(O(\log N)\)

typedef long long ll; 

ll qpow(ll x,int y,int mod){  //x^y
  if(y<0) return qpow(qpow(x,MOD-2),-y);
  ll ans=1;
  while(y){
    if(y&1) ans=(ans*x)%mod;
    x=x*x%mod;
    y>>=1;
  }
  return ans;
}

1.4.2.有理數(shù)域的快速冪

\(x^{-y}=(x^{-1})^{y}\)，即先求x的逆元再求快速冪。

1.4.3.光速冪

\(O(\sqrt {指數(shù)})\)預(yù)處理，\(O(1)\)查詢。

適用條件：調(diào)用光速冪時底數(shù)相同，\(O(\sqrt{指數(shù)})\)不大。

令\(B=\sqrt{指數(shù)}\)，預(yù)處理p1[B]和p2[B]：\(p1[i]=x^i,p2[i]=(x^B)^i=x^{i*B}\)。調(diào)用光速冪時直接\(O(1)\)拼接。

1.5.龜速乘（用于先乘再取模會爆long long的情況）

\(O(1)\)

\(a*b\% p=a*b-\lfloor a*b/p\rfloor*p\)。

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

typedef long long ll;
typedef unsigned long long ull;

ll mul_64(ll a,ll b,ll p){
    a%=p,b%=p;
    ull c=(long double)a*b/p;
    ull x=a*b,y=c*p;
    ll ans=(ll)(x%p)-(ll)(y%p);
    if(ans<0) ans+=p;
    return ans;
}

int main(){
    ll a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld",mul_64(a,b,p));
    return 0;
}

\(O(\log b)\)

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

typedef long long ll;

ll mul_64(ll a,ll b,ll p){
    ll res=0;
    while(b){
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}

int main(){
    ll a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld\n",mul_64(a,b,p));
    return 0;
}

1.6.狀態(tài)壓縮

1. 取出n 在二進制下的第k位（ k 從 0 開始計數(shù) ) ：(n>>k)&1；
2. 取出n 在二進制下的第0～k-1位：n&((1<<k)-1)；
3. 對n 在二進制下的第k位取反：n xor (1<<k)；
4. 對n在二進制下的第0～k-1位取反：n xor (1<<k)-1；
5. 對n 在二進制下的第k位賦值1：n|(1<<k)；
6. 對n 在二進制下的第k位賦值0：n&(!(1<<k))。

1.7.模擬集合操作

一個數(shù)的二進制表示可以看作是一個集合（0表示不在集合中，1表示在集合中）。\(e.g.\)集合{1,3,4,8} ，可以表示成\((100011010)_2\) 。

而對應(yīng)的位運算也就可以看作是對集合進行的操作：交集a&b、并集a|b、全集(1<<n)-1、補集~a、差集a&(~b)、對稱差a^b。

1.7.1.枚舉集合\(O(2^N)\)

一般常用來代替遞歸型枚舉或者狀態(tài)壓縮。

for(int state=1;state<(1<<k);state++)

1.7.2.枚舉子集

對于上面枚舉的一個集合state，遍歷state的子集。

//枚舉非空（真）子集
for(int s=state/*如果遍歷非空真子集就是(state-1)&state*/;s;s=(s-1)&state/*注意這里是state而不是s*/)//s是state的一個非空子集

//枚舉子集
for(int s=state;;s=(s-1)&state)
{
    //abaabaaba
    if(!s) break;
}

s-1：把 s的0~lowbit(s)位全部取反；(s-1)&state：依次消除s的lowbit(s)位上的1。

如果枚舉集合的循環(huán)嵌套枚舉子集的循環(huán)，復(fù)雜度是\(O(3^N)\)（一個元素有3種選擇方式：不在集合內(nèi)部、在集合內(nèi)部但不在子集內(nèi)部、在子集內(nèi)部）。

應(yīng)用

1. 二進制下不存在某一位n為0而m為1\(\Leftrightarrow\)二進制下m是n的子集，n轉(zhuǎn)移到m用子集轉(zhuǎn)移。

2. 枚舉\(s1,s2\in (1<<n)-1\)，且s1&s2==0即無交集：枚舉集合s1，枚舉(s1^((1<<n)-1))的子集s2，復(fù)雜度從\(O((2^n)^2)\)優(yōu)化到\(O(3^n)\)。

   如果還滿足s1|s2==(1<<n)-1，可考慮子集卷積優(yōu)化，復(fù)雜度從\(O(3^n)\)優(yōu)化到\(O(n^2*2^n)\)。

1.8.位集合優(yōu)化\(O(\frac{?}{w})\)

適用條件：布爾數(shù)組的操作。

常用于很難繼續(xù)優(yōu)化復(fù)雜度的\(O(N^2)\)做法。

STL

《C++語言.4.2.位集合bitset》。

手寫

可以預(yù)處理所有長度為b的2^b個01串的復(fù)雜信息。復(fù)雜度是\(O(2^b+\frac{?}{b})\)。

2.遞推·遞歸·分治

遞推在狀態(tài)轉(zhuǎn)移領(lǐng)域有很多涉獵，遞歸在搜索、樹（包括圖和數(shù)據(jù)結(jié)構(gòu)）領(lǐng)域有很多涉獵。

2.1.遞歸實現(xiàn)指數(shù)型枚舉

int n;
int chosen[N],idx;

void calc(int x){
    //問題邊界，輸出
    if(x==n+1){
        for(int i=1;i<=idx;i++) printf("%d ",chosen[i]);
        puts("");
        return ;
    }

    //選x
    chosen[++idx]=x;
    calc(x+1);
    idx--;  //還原現(xiàn)場

    //不選x
    calc(x+1);

    return ;
}

scanf("%d",&n);
calc(1);

2.2.遞歸實現(xiàn)組合型枚舉

int n,m;
int chosen[N],idx;

void calc(int x){
    //剪枝
    if(idx>m || idx+(n-x+1)<m) return ;

    //問題邊界，輸出
    if(x==n+1){
        for(int i=1;i<=idx;i++) printf("%d ",chosen[i]);
        puts("");
        return ;
    }

    //選x
    chosen[++idx]=x;
    calc(x+1);
    idx--;  //還原現(xiàn)場

    //不選x
    calc(x+1);

    return ;
}

scanf("%d%d",&n,&m);
calc(1);

• 2.3.遞推實現(xiàn)組合型枚舉

const int N=1<<21,inf=0x3f3f3f3f;
int n,m;
map<int ,int > m1;

struct point{
    vector<int > v1;
}p1[N];

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

bool cmp(point x,point y){
    int ptail=0;
    while(x.v1[ptail]==y.v1[ptail])ptail++;
    return x.v1[ptail]<y.v1[ptail];
}

int main(){
    cin>>n>>m;
    bitset<26> b1;
    m1[1]=0;
    int q=2,tail=0;

    for(int i=1;i<=32;i++){
        m1[q]=i;
        q*=2;
    }

    for(int a=0;a<(1<<n);a++){
        b1|=a;
        if(b1.count()==m){
            int pa=a;
            while(pa){
            p1[tail].v1.push_back(m1[lowbit(pa)]+1);
            pa^=lowbit(pa);
            }
            tail++;
        }
        b1&=0;
    }
    sort(p1,p1+tail,cmp);
    for(int a=0;a<tail;a++){
        for(int b=0;b<m;b++)printf("%d ",p1[a].v1[b]);
        printf("\n");
    }
}

2.4.遞歸實現(xiàn)排列型枚舉

int n;
int order[N];
bool vis[N];

void calc(int idx){
    //問題邊界，輸出
    if(idx==n+1){
        for(int i=1;i<=n;i++) printf("%d ",order[i]);
        puts("");
        return ;
    }

    //排列枚舉
    for(int x=1;x<=n;x++){
        if(vis[x]) continue;
        order[idx]=x;
        vis[x]=true;
        calc(idx+1);
        vis[x]=false;
        //此處省略了：order[idx]=0;
        //不可以寫：idx--;
    }

    return ;
}

scanf("%d",&n);
calc(1);

2.5.遞歸實現(xiàn)分治

void merge(int l,int r){
    if(l>=r) return ;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    
    //abaabaaba
    
    return ;
}

4種分治模型：

1. 每次可以把集合劃分為兩半，分別往下遞歸處理。\(e.g.\)利用分治轉(zhuǎn)移dp、一維四邊形不等式優(yōu)化dp的離線分治寫法。
2. 有關(guān)元素與元素之間的配對的問題：2個元素都在左/右區(qū)間的情況遞歸處理，2個元素分別在左右兩個區(qū)間的情況當(dāng)前層處理。e.g.CDQ分治、點分治（1條經(jīng)過根節(jié)點路徑由2條從根節(jié)點出發(fā)的路徑組成）。
3. 計算每個點都需要一些信息，直接計算會超時：可以考慮借助分治結(jié)構(gòu)充分利用信息、子區(qū)間利用父親區(qū)間的信息，信息最多被分到\(O(\log N)\)個區(qū)間。e.g.線段樹分治。
4. 整體二分型分治（移動指針MID，指針移動距離是\(O(N\log N)\)，且操作最多往下遞歸\(O(log N)\)層）。

2.5.1.分治求解平面最近點對\(O(N \log N)\)

1. 將點按橫坐標(biāo)x排序。以便分治求解。
2. 分治，把點分成左右兩半部分遞歸處理。在當(dāng)前層記錄base=point[mid].x；d：當(dāng)前的最近點對的距離。
3. 最近點對的距離的可能值：左半部分最近點對、右半部分最近點對以及左半部分與右半部分構(gòu)成的最近點對。

   • 左半部分最近點對以及右半部分最近點對

     遞歸時求解。

   • 左半部分與右半部分構(gòu)成的最近點對

     暴力匹配左右兩半部分的點對。復(fù)雜度是\(O(N^2)\)。

     剪枝：

     1. 橫坐標(biāo)x的信息已經(jīng)利用完。歸并把點按縱坐標(biāo)y排序，以便下面利用縱坐標(biāo)y的信息。
     2. 排除不可能答案：點i的橫坐標(biāo)與base的絕對值都大于當(dāng)前的最近點對的距離d，與另一半部分構(gòu)成的點對的距離更不可能成為答案。
     3. 排除不可能答案：由于點按縱坐標(biāo)排序，所以暴力匹配當(dāng)點i與點j的距離大于當(dāng)前的最近點對的距離d時，點j后面的點與點i構(gòu)成的點對的距離更不可能成為答案。

     加上這3個剪枝后，數(shù)學(xué)幾何可以證明該暴力匹配的復(fù)雜度是\(O(5*N)\)。

typedef long double LD;
typedef pair<LD,LD> PLDLD;
int n;
PLDLD p[N],seq[N];

bool cmpx(PLDLD q,PLDLD w)  //按橫坐標(biāo)x排序
{
    return cmp(q.x,w.x)<0;
}

LD divide(int l,int r)
{
    //分治
    //最近點對的距離的可能值：左半部分最近點對、右半部分最近點對以及左半部分與右半部分構(gòu)成的最近點對
    if(l==r) return INF;//邊界
    int mid=(l+r)>>1;
    LD base=p[mid].x;   //一定在上面就記錄，因為下面遞歸會把p[i]按照縱坐標(biāo)y排序
    
    //左半部分最近點對以及右半部分最近點對：遞歸時求解
    LD d=min(divide(l,mid),divide(mid+1,r));    //d：當(dāng)前的最近點對的距離
    
    //左半部分與右半部分構(gòu)成的最近點對：暴力匹配左右兩半部分的點對
    //剪枝1：歸并按縱坐標(biāo)y排序
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        if(cmp(p[i].y,p[j].y)<0)
        {
            seq[k]=p[i];
            k++;
            i++;
        }
        else
        {
            seq[k]=p[j];
            k++;
            j++;
        }
    }
    while(i<=mid)
    {
        seq[k]=p[i];
        k++;
        i++;
    }
    while(j<=r)
    {
        seq[k]=p[j];
        k++;
        j++;
    }
    for(i=l;i<=r;i++) p[i]=seq[i];
    
    int sidx=0;
    for(i=l;i<=r;i++) if(cmp(fabs(p[i].x-base),d)<=0) seq[++sidx]=p[i]; //剪枝2：排除不可能答案：點i的橫坐標(biāo)與base的絕對值都大于當(dāng)前的最近點對的距離d，與另一半部分構(gòu)成的點對的距離更不可能成為答案
    for(i=1;i<=sidx;i++)    //暴力匹配左右兩半部分的點對。加上3個剪枝后，數(shù)學(xué)幾何可以證明復(fù)雜度是O(5*N)
        for(j=i+1;j<=sidx;j++)
        {
            if(cmp(fabs(seq[i].y-seq[j].y),d)>=0) break;    //剪枝3：排除不可能答案：由于點按縱坐標(biāo)排序，所以當(dāng)點i與點j的距離大于當(dāng)前的最近點對的距離d時，點j后面的點與點i構(gòu)成的點對的距離更不可能成為答案
            d=min(d,get_dis(seq[i],seq[j]));
        }
    
    return d;
}

for(int i=1;i<=n;i++) scanf("%Lf%Lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmpx);   //將點按橫坐標(biāo)x排序。以便分治求解
printf("%.4Lf\n",divide(1,n));

2.6.分形

1. 新建字符數(shù)組a為畫布。
2. 思考如何在畫布a的矩形(x1,y1),(x2,y2)范圍內(nèi)畫第k階圖形u。
3. 用空格初始化畫布a。
4. 分治畫圖，注意n,i,x是縱，m,j,y是橫。輸出。

//注意n,i,x是縱，m,j,y是橫
void divide(int u,int k,int x1,int y1,int x2,int y2)//在畫布a的矩形(x1,y1),(x2,y2)范圍內(nèi)畫第k階圖形u

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        a[i][j]=' ';//注意初始化
divide(1,k,1,1,n,m);
for(int i=1;i<=n;i++,puts(""))
    for(int j=1;j<=m;j++)
        putchar(a[i][j]);

3.排序

3.1.快速排序

3.1.1.快速排序\(O(\log N*N*Compare)\)

STLsort

《C++語言.1.標(biāo)準(zhǔn)模板庫（STL）函數(shù)和算法模板 排序sort》

手寫

void quick_sort(type a[],int l,int r)   //將數(shù)組a的下標(biāo)在[l,r]內(nèi)的元素升序排序
{
    if(l>=r) return ;
    int i=l-1,j=r+1;
    type x=a[(l+r)>>1];
    while(i<j)
    {
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);
    return ;
}

3.1.2.快速排序求第k小元素\(O(N*Compare)\)

STLnth_element

《C++語言.1.標(biāo)準(zhǔn)模板庫（STL）函數(shù)和算法模板 第n小元素nth_element》

手寫

type quick_sort(type a[],int l,int r,int k)   //將數(shù)組a的下標(biāo)在[l,r]內(nèi)的元素重新分配順序，第k小的元素分配在l+k-1，小于（等于）第k小的元素的元素分配在[l,l+k-1)，大于（等于）第k小的元素的元素分配在(l+k-1,r]，并返回第k小元素
{
    if(l>=r) return a[l];
    int i=l-1,j=r+1;
    type x=a[(l+r)>>1];
    while(i<j)
    {
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    if(j-l+1>=k) return quick_sort(a,l,j,k);
    else return quick_sort(a,j+1,r,k-(j-l+1));
}

cout<<quick_sort(a,1,n,k)<<'\n';
/*或者
quick_sort(a,1,n,k);
cout<<a[k]<<'\n';
*/

3.2.歸并排序

3.2.1.歸并排序\(O(\log N*N*Compare)\)

STLstable_sort

《C++語言.1.標(biāo)準(zhǔn)模板庫（STL）函數(shù)和算法模板 穩(wěn)定排序stable_sort》

手寫

type b[N];

void merge_sort(type a[],int l,int r)    //將數(shù)組a的下標(biāo)在[l,r]內(nèi)的元素升序排序
{
    if(l==r) return ;
    
    int mid=(l+r)>>1;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j])
        {
            b[k]=a[i];
            i++,k++;
        }
        else
        {
            b[k]=a[j];
            j++,k++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++,k++;
    }
    while(j<=r)
    {
        b[k]=a[j];
        j++,k++;
    }
    for(i=l;i<=r;i++) a[i]=b[i];
    
    return ;
}

3.2.2.1.逆序?qū)?/h4>

本質(zhì)是二維偏序：滿足的i<j且\(a_i>a_j\)元素對\((\{i,a_i\},\{j,a_j\})\)個數(shù)。

應(yīng)用

• 現(xiàn)實意義：給定1個數(shù)列，只能使用交換相鄰兩項的操作（冒泡排序），至少需要逆序?qū)€數(shù)次操作次數(shù)。

• 逆序?qū)Φ钠媾夹裕?/p>

  • 交換序列中的兩個元素，逆序?qū)Φ钠媾夹砸欢〞淖儭?/li>
  • 將序列中下標(biāo)在[l,r]內(nèi)的元素循環(huán)左移k位，當(dāng)且僅當(dāng)長度r-l+1為偶數(shù)并且k為奇數(shù)時，逆序?qū)Φ钠媾夹愿淖儭?/li>

• 給定1個pair數(shù)列，按照第一關(guān)鍵字排序得到的數(shù)列的以第二關(guān)鍵字為依據(jù)的逆序?qū)€數(shù)res1=按照第二關(guān)鍵字排序得到的數(shù)列的以第一關(guān)鍵字為依據(jù)的逆序?qū)€數(shù)res2。

  證明：由逆序?qū)Φ默F(xiàn)實意義，按照第一關(guān)鍵字排序得到的數(shù)列至少使用res1次交換相鄰兩項的操作才能得到按照第二關(guān)鍵字排序得到的數(shù)列，按照第二關(guān)鍵字排序得到的數(shù)列至少使用res2次交換相鄰兩項的操作才能得到按照第一關(guān)鍵字排序得到的數(shù)列。而這兩個變換本質(zhì)上是互逆的。

• 奇數(shù)碼游戲兩個局面可達(dá)，當(dāng)且僅當(dāng)兩個局面轉(zhuǎn)化為序列（不考慮空格）后，逆序?qū)Φ钠媾夹韵嗤?/p>

\(O(N\log N)\)

注意開long long！

只能最后一起求逆序?qū)Α?/p>

type b[N];

ll merge_sort(type a[],int l,int r)    //求出數(shù)組a的下標(biāo)在[l,r]內(nèi)的元素構(gòu)成的逆序?qū)?{
    if(l==r) return 0;
    
    ll res=0;
    int mid=(l+r)>>1;
    res+=merge_sort(a,l,mid);
    res+=merge_sort(a,mid+1,r);
    
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j])
        {
            b[k]=a[i];
            i++,k++;
        }
        else
        {
            b[k]=a[j];
            res+=mid-i+1;   //a[j]與a[i~mid]構(gòu)成逆序?qū)?            j++,k++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++,k++;
    }
    while(j<=r)
    {
        b[k]=a[j];
        j++,k++;
    }
    for(i=l;i<=r;i++) a[i]=b[i];
    
    return res;
}

樹狀數(shù)組求逆序?qū)Γ?a target="_blank" rel="noopener nofollow">《數(shù)據(jù)結(jié)構(gòu)7.1.樹狀數(shù)組求逆序?qū)Α?/a>

優(yōu)點：可以一邊插入一邊隨時求逆序?qū)Α?/p>

3.2.3.歸并排序?qū)?個有序的序列合并為1個有序的序列\(O((N_1+N_2)*Compare)\)

3.3.基數(shù)排序

3.3.1.計數(shù)排序\(O(N+W)\)

void counting_sort(int a[],int n)
{
    int c[W];
    int b[N];
    memset(c,0,sizeof c);
    for(int i=1;i<=n;i++) c[a[i]]++;
    for(int x=1;x<W/*注意這里是<W*/;x++) c[x]+=c[x-1];
    for(int i=n;i>=1;i--) b[c[a[i]]--]=a[i];    //從n到1倒序以保證排序穩(wěn)定性
    for(int i=1;i<=n;i++) a[i]=b[i];
    return ;
}

3.3.2.k-關(guān)鍵字元素

\(a<b\Leftrightarrow \exist i\in[1,k],(\forall j\in[1,i-1],a_j=b_j)\land a_i<b_i\)。

\(a=b\Leftrightarrow \forall i\in[1,k],a_i=b_i\)。

3.3.3.基數(shù)排序\(O(K(N+W^{\frac1K}))\)

下面采用LSD（Least Significant Digit first）寫法。

1. 將元素轉(zhuǎn)化為k-關(guān)鍵字元素，滿足大小關(guān)系不變。
2. 從k到1遍歷i，依次以第i關(guān)鍵字為依據(jù)對所有元素執(zhí)行計數(shù)排序。

代碼以元素為10^9內(nèi)的正整數(shù)為例。

struct K_keyword
{
    int key[K];
};

void counting_sort(K_keyword ak[],int n,int ik)
{
    int c[WK];
    K_keyword b[N];
    memset(c,0,sizeof c);
    for(int i=1;i<=n;i++) c[ak[i].key[ik]]++;
    for(int x=1;x<WK;x++) c[x]+=c[x-1];
    for(int i=n;i>=1;i--) b[c[ak[i].key[ik]]--]=ak[i];
    for(int i=1;i<=n;i++) ak[i]=b[i];
    return ;
}

void radix_sort(int a[],int n)
{
    int k=2,wk=sqrt(W);
    K_keyword ak[N];
    for(int i=1;i<=n;i++) ak[i].key[1]=a[i]/wk,ak[i].key[2]=a[i]%wk;
    for(int i=k;i>=1;i--) counting_sort(ak,n,i);
    for(int i=1;i<=n;i++) a[i]=ak[i].key[1]*wk+ak[i].key[2];
    return ;
}

3.4.嚴(yán)格弱序

比較必須滿足嚴(yán)格弱序。以重載為例，必須滿足以下嚴(yán)格弱序的四個條件：

\(\not<\)：cmp函數(shù)判斷是否x<y返回false。

• 非自反性：“嚴(yán)格”：\(x\not< x\)。

  因此小于號不能重載為小于等于。

• 等價（不可比性）傳遞性：“弱”：若\(x\not<y,y\not<x\)，則x=y。\(\Leftrightarrow\)若\(x\not<y,y\not<x,y\not<z,z\not<y\)，則\(x\not<z,z\not<x\)。

• 反對稱性：“有序”：若x<y，則\(y\not<x\)。

• 傳遞性：“有序”：若x<y,y<z，則x<z。

若重載小于號時不能滿足上面的嚴(yán)格弱序的條件，則必須構(gòu)造一種既滿足原比較關(guān)系，又滿足嚴(yán)格弱序的比較關(guān)系。

方法一：一般最容易不滿足嚴(yán)格弱序的條件是“弱”。如果原比較關(guān)系只不滿足“弱”，則特判當(dāng)兩組元素在原比較關(guān)系相等時如何比較它們之間的大小。\(e.g.\)min(a[i],b[i+1])<min(a[i+1],b[i])不滿足“弱”。只需要在min(a[i],b[i+1])==min(a[i+1],b[i])時判斷a[i]<a[i+1]即可。

方法二：如果比較的元素是多元組，則先按照組內(nèi)元素大小關(guān)系分類，討論類與類之間的大小關(guān)系以及類內(nèi)部組與組之間的大小關(guān)系。

方法三：某些比較關(guān)系可以等價變形。\(e.g.\)max(a[i],a[i+1]+b[i])<max(a[i+1],a[i]+b[i+1])：顯然a[i]<a[i]+b[i+1]，a[i+1]+b[i]>a[i+1]，因此等價變形為a[i+1]+b[i]<a[i]+b[i+1]。

補充

1. 若\((a_{i+1}-a_i)(b_{i+1}-b_i)>0\)，則不交換\((b_i,b_{i+1})\)更優(yōu)\(\Leftrightarrow\)在保證a不變的情況下，移動b使在同一個位置的a,b的兩根火柴在a,b中的排名對應(yīng)相等。

3.5.排序思想

3.5.1.冒泡排序

鄰項交換、逆序?qū)Α?/p>

3.5.2.插入排序

數(shù)學(xué)歸納法（假設(shè)前i-1個數(shù)有序，考慮第i個數(shù)。）

4.二分

適用條件：具有單調(diào)性的問題。

4.1.STLlower_bound、upper_bound

《C++語言.1.標(biāo)準(zhǔn)模板庫（STL）函數(shù)和算法模板 二分lower_bound和upper_bound》

4.2.整數(shù)集合上的二分

4.2.1.整數(shù)集合上的二分

• l=mid？r=mid？

  令長度為2的區(qū)間l=1，r=2。看是l=mid還是r=mid會縮小為長度為1區(qū)間。

• 保左？保右？

  代碼

  令長度為2的區(qū)間l=1，r=2。如果mid是偏向l（r），則該二分是保左（右）。

  如果mid是恰好可行的（==）且保左（右），就令r=mid（l=mid）。（因為mid本身就是偏左（右））

  問題

  保左（右）：邊界mid在答案位置ans的左（右）邊。此時l（r）會向mid的右（左）邊一單位跳到答案位置。

  4種情況（0代表check(mid)=false，1代表true）：01找最后一個0、01找第一個1、10找最后一個1、10找第一個0。

  根據(jù)問題選擇保左的二分還是保右的二分。

• 無解？

  對于保左寫法（mid=(l+r)>>1），mid不會取到r這個值，因此可以把最初的二分區(qū)間[1,n]擴大為[1,n+1]，若最終l==n+1，無解。

  對于保右寫法（mid=(l+r+1)>>1），mid不會取到l這個值，因此可以把最初的二分區(qū)間[1,n]擴大為[0,n]，若最終l==0，無解。

在單調(diào)序列a中查找≥x最小的一個（x或x的后繼、01找第一個1、10找第一個0），保左：

while(l<r)
{
    int mid=(l+r)>>1;
    if(a[mid]>=x) r=mid;
    else l=mid+1;
}
return a[l];//思維：此時l==r

在單調(diào)序列a中查找≤x最大的一個（x或x的前軀、01找最后一個0、10找最后一個1），保右：

while(l<r)
{
    int mid=(l+r+1)>>1;
    if(a[mid]<=x) l=mid;
    else r=mid-1;
}
return a[r];//思維：此時l==r

• 萬能二分

  01：

int ans;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(check(mid)) r=mid-1,ans=mid;
    else l=mid+1;
}
return ans;//思維：此時l==r

10：

int ans;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(check(mid)) l=mid+1,ans=mid;
    else r=mid-1;
}
return ans;//思維：此時l==r

4.2.2.二分答案轉(zhuǎn)為判定

這個思想在很多算法中都有涉獵。

適用條件：具有“單調(diào)性”值域的問題：
設(shè)定義域為該問題下可行方案，則值域為該方案的評分，最優(yōu)解就是評估分最高S的方案。\(\forall x>S\)，都不存在一個合法的方案達(dá)到x分；\(\forall x≤S\)，一定存在一個合法的方案達(dá)到或超過x分。
又或者說方案一段全部合法另一段全部不合法。

把最優(yōu)性問題轉(zhuǎn)化為可行性問題，簡化題目。

注意保左保右的問題。詳見《基礎(chǔ)算法4.1.整數(shù)集合上的二分》

技巧

• 求絕對值|c-x|最小值：可拆成小于c的最大x和大于c的最小x兩個子問題。
• 求check()方案時，要在while(l<r)循環(huán)后****check(l)，不可以在while(l<r)循環(huán)內(nèi)的if(check(mid))后記錄方案，因為有可能mid一直非法到最后l=r=1就沒有記錄方案了。

4.3.實數(shù)域上的二分

while(r-l>EPS)
{
    double mid=(l+r)/2;
    if(check(mid)) l=mid;//mid還需要再大一點
    else r=mid;//mid還需要再小一點
}
return l;//思維：此時l==r。偶爾取l（或r）會有精度問題，需要換著取r（或l）試試

4.4.斜率上的二分

凸單調(diào)問題。求一個點集中的點，使其與給定的點的斜率最值→求一個凸包上的點，使其與給定的點的斜率最值。

下面以下凸包（斜率最大）為例：下凸包存在棧s中：

int l=1,r=top,res;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(sign(slope(s[mid-1],poi)/*slope(a,b)：a、b兩點連線的斜率*/,slope(s[mid],poi))<0) l=mid+1,res=mid;
    else r=mid-1;
}
return res;

4.5.三分

《搜索.三分》

搜索

4.6.制造可二分性

• “找到第一個關(guān)鍵點”：前綴處理，使得滿足可二分性。

5.倍增

適用條件：遞推問題的狀態(tài)空間關(guān)于2的次冪具有可劃分性，或具有可二分性。

5.1.序列上的倍增——二分的兄弟

01找最后一個0、10找最后一個1。

若要“01找第一個1、10找第一個0”，則在倍增求得“01找最后一個0、10找最后一個1”后令答案加一。

5.1.1.二進制拆分寫法

int r=l-1;
for(int k=19;k>=0;k--)
    if(r+(1<<k)<=n && check(l,r+(1<<k)))
        r+=1<<k;

//找最后一個0
if(r==l-1) puts("-1");    //不存在0，無解
printf("%d\n",r);

//找第一個1
r++;
if(r==n+1) puts("-1");    //不存在1，無解
printf("%d\n",r);

5.1.2.最遠(yuǎn)擴展寫法

記len=r-l+1，check(l,r)的復(fù)雜度是\(O(f(len))\)。則此寫法的復(fù)雜度是\(O(f(len)\log len)\)。

int r=l-1,p=1;
while(r+p<=n && check(l,r+p))
{
    r+=p;
    p<<=1;
}
while(p)
{
    if(r+p<=n && check(l,r+p)) r+=p;
    p>>=1;
}

//找最后一個0
if(r==l-1) puts("-1");    //不存在0，無解
printf("%d\n",r);

//找第一個1
r++;
if(r==n+1) puts("-1");    //不存在1，無解
printf("%d\n",r);

5.1.3.倍增優(yōu)于二分的情況

5.1.3.1.樹狀數(shù)組上從1向右/從n向左倍增

樹狀數(shù)組上二分是\(O(\log^2N)\)，樹狀數(shù)組上二進制拆分寫法的倍增是\(O(\log N)\)。

5.1.3.2.最小劃分問題

問題：求出將序列最小劃分成幾段，才能使每一段都滿足條件。

根據(jù)貪心，為了讓序列分成的段數(shù)最少，每一段都應(yīng)該在滿足條件的前提下，盡量包含更多的數(shù)。

于是現(xiàn)在需要高效解決的問題為：當(dāng)確定一個左端點l之后，右端點r在[l,r]滿足條件的前提下，最遠(yuǎn)能擴展到多少。

二分的復(fù)雜度是\(O(\sum f(N)\log N=f^2(N)\log N)\)，最遠(yuǎn)擴展寫法的倍增的復(fù)雜度是\(O(\sum f(len)\log len)=O(f(N)\log N)\)。

5.2.ST表

適用條件：可重疊：RMQ問題：區(qū)間最值問題、區(qū)間GCD。

思維：計數(shù)問題：不重不漏；最值問題：不漏即可。

以靜態(tài)詢問區(qū)間最大值為例：

\(f[l,k]\)：序列下標(biāo)在\([l,l+2^k-1]\)里的數(shù)的最大值，即從\(l\)開始\(2^k\)個數(shù)的最大值。

遞推邊界：\(f[l,0]=a[l]\)。

遞推公式：\(f[l,k]=\max(f[l,k-1],f[l+2^{k-1},k-1])\)。

const int N=2e5+10;
int n,q;
int a[N];
int f[N][20],log_2[N];

void ST_pre()
{
    for(int i=2;i<=n;i++) log_2[i]=log_2[i>>1]+1;
    for(int l=1;l<=n;l++) f[l][0]=a[l];
    for(int k=1;1+(1<<k)-1<=n;k++)
        for(int l=1;/*r=*/l+(1<<k)-1<=n;l++)
            f[l][k]=/*或min*/max(f[l][k-1],f[l+(1<<(k-1))/*注意這里不要-1！！！*/][k-1]);
    return ;
}

int ST_query(int l,int r)
{
    int k=log_2[r-l+1];
    return /*或min*/max(f[l][k],f[r-(1<<k)+1][k]);
}

如果還要求出最大值在哪個位置：

void st_pre()
{
    for(int i=2;i<=n;i++) log_2[i]=log_2[i>>1]+1;
    for(int i=1;i<=n;i++) f[i][0]=i;
    for(int k=1;1+(1<<k)-1<=n;k++)
        for(int l=1;l+(1<<k)-1<=n;l++)
        {
            int a=f[l][k-1],b=f[l+(1<<(k-1))][k-1];
            f[l][k]=sum[a]>sum[b] ? a : b;
        }
    return ;
}

int st_query(int l,int r)
{
    int k=log_2[r-l+1];
    int a=f[l][k],b=f[r-(1<<k)+1][k];
    return sum[a]>sum[b] ? a : b;
}

卡空間技巧

若st表要在struct上建立，開\(O(N\log N)\)的struct可能會爆空間。其實只要開\(O(N)\)的struct存原序列，st表開\(O(N\log N)\)的int存最值對應(yīng)的下標(biāo)，比較大小時用映射后的值比較。

5.3.倍增數(shù)組

\(f[i][k]\)：區(qū)間\([i,i+2^k-1]\)或\([i-2^k+1,i]\)的某信息。

5.4.倍增的其他運用

1. 樹上倍增求LCA。

   《圖論》

6.散列表（Hash）

6.1.數(shù)Hash

6.1.1.離散化\(O(N\log N)\)

有關(guān)區(qū)間覆蓋[l,r]問題中的離散化的注意事項：

如果只把l、r加入到離散化，或錯把l、l+1、r-1、r加入到離散化（即向內(nèi)擴張），那么對于依次[1,5]、[1,2]、[4,6]區(qū)間覆蓋，由于有關(guān)[1,5]的離散化的點都被覆蓋，導(dǎo)致程序誤判[1,5]被完全覆蓋。

正確的做法是把l、r、r+1（或l-1）加入到離散化，即要向外擴張。如果求穩(wěn)可以把l、l-1、l+1、r、r-1、r+1都加入到離散化。

6.1.1.1.基于相對大小

優(yōu)點：仍能比較大小。

缺點：必須一起離線處理。

vector<int> nums;

//最小的元素->0
//注意，如果要令最小的元素->1，則查詢離散化之前的值應(yīng)該是nums[x-1]！！！
int Hash(int x)
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

int main()
{
    scanf("%d",&x);
    nums.push_back(x);
    //繼續(xù)輸入abaabaaba...

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    //O(1)查詢使用離散化之后的值，先預(yù)處理：a->b
        x=Hash(x);
        //然后x就是離散化之后的值

    //查詢離散化之前的值：a<-b
    int y=nums[x];

    return 0;
}

6.1.1.2.基于記憶化

優(yōu)點：可以在線處理。

缺點：不能比較大小。

int hidx;
map<int,int> h;

int Hash(int x)
{
    if(h.count(x)) return h[x];
    return h[x]=++hidx;
}

int main()
{
    int x;
    scanf("%d",&x);
    int y=Hash(x);
    //abaabaaba...
}

6.1.2.Xor Shift\(O(1)\)

const ull MASK=mt19937_64(srd())();

ull xor_shift(ull x)
{
    x^=MASK;
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    x^=MASK;
    return x;
}

6.2.字符串Hash

通過下面的內(nèi)容可以實現(xiàn)一個簡單的\(O(N\log^2N)\)的后綴數(shù)組求法。

6.2.1.判斷兩個子串是否相同

\(O(N)\)預(yù)處理母串，\(O(1)\)判斷兩個子串是否相同。

//模數(shù)=131
int m,len,l1,l2,r1,r2;
unsigned long long f[N],q[N];//f：字符串hash；q：預(yù)處理模數(shù)的次方
char s[N];

int main(){
    scanf("%s",s+1);
    scanf("%d",&m);
    
    len=strlen(s+1);
    q[0]=1;
    for(int i=1;i<=len;i++){
        f[i]=f[i-1]*131+(s[i]-'a'+1);//在字符串后面添加一個字符,+1不可省略！！！
        
        q[i]=q[i-1]*131;
    }
    
    while(m--){
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(f[r1]-f[l1-1]*q[r1-l1+1]/*求子字符串的hash'*/ == f[r2]-f[l2-1]*q[r2-l2+1]) puts("Yes");
        else puts("No");
    }
    return 0;
}

6.2.2.比較兩個子串的大小與查詢兩個子串的最長公共前綴

\(O(N)\)預(yù)處理母串。

二分找到第一處兩個子串不相同的位置。二分判斷條件是《基礎(chǔ)算法6.2.1.判斷兩個子串是否相同》中的哈希判斷相同。然后比較第一處不相同的位置的字符的大小。若沒有不相同的位置，則比較兩個子串的長度。\(O(\log N)\)。

bool cmp(int l1,int r1,int l2,int r2)
{
    int len=min(r1-l1+1,r2-l2+1);   //防止越界
    
    //二分找到第一處兩個子串不相同的位置：str[l1+l]!=str[l2+l]
    int l=0,r=len;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(f[l1+mid]-f[l1-1]*p[(l1+mid)-(l1-1)]!=f[l2+mid]-f[l2-1]*p[(l2+mid)-(l2-1)]/*哈希判斷相同*/) r=mid;
        else l=mid+1;
    }
    if(l==len) return r1-l1+1<r2-l2+1;  //若沒有不相同的位置，則比較兩個子串的長度
    else return str[l1+l]<str[l2+l];    //若有不相同的位置，比較第一處不相同的位置的字符的大小
}

同理可以查詢兩個子串的最長公共前綴。\(O(\log N)\)。

6.3.樹同構(gòu)

樹同構(gòu)一般是判斷無標(biāo)號同構(gòu)，所以不可用prufer有標(biāo)號判斷。

無根樹同構(gòu)轉(zhuǎn)化為有根樹同構(gòu)

選定關(guān)鍵點為無根樹的根，而一棵樹的重心最多只有2個。

int n;
int head[2][N],e[2][M],ne[2][M],idx[2];

pii wc[2][2];

void add(int id,int u,int v)
{
    e[id][++idx[id]]=v,ne[id][idx[id]]=head[id][u],head[id][u]=idx[id];
    return ;
}

int dfs1(int id,int u,int father)
{
    int siz=1,ma=0;
    for(int i=head[id][u];i;i=ne[id][i])
    {
        int v=e[id][i];
        if(v==father) continue;
        int res=dfs1(id,v,u);
        siz+=res;
        ma=max(ma,res);
    }
    ma=max(ma,n-siz);
    if(ma<wc[id][0].y) wc[id][0]={u,ma},wc[id][1]={-1,n};
    else if(ma==wc[id][0].y) wc[id][1]={u,ma};
    return siz;
}

cin>>n;
for(int id=0;id<=1;id++)
{
    idx[id]=0,wc[id][0]=wc[id][1]={-1,n};
    for(int u=1;u<=n;u++) head[id][u]=0;
}
for(int id=0;id<=1;id++)
{
    for(int i=1,u,v;i<n;i++)
    {
        cin>>u>>v;
        add(id,u,v),add(id,v,u);
    }
    dfs1(id,1,0);
}

技巧

1. 還需判斷點權(quán)是否相同：把點權(quán)設(shè)計到點的初值。

對比

			復(fù)雜度	是否絕對正確	是否好寫/能否高效換根	能否在線處理	能否比較大小	能否逆向求出樹的結(jié)構(gòu)
AHU算法	基于樹的最小括號序列表示		\(O(N^2)\)	√	×	√	√（能比較任何點的以其為根的子樹的最小括號序列的大小）	√
	基于點的兒子數(shù)組遞推的數(shù)值表示	基于同一深度的點的以其為根的子樹的“結(jié)構(gòu)字典序”的相對大小	\(O(N)/O(N\log N)\)			×	√（能比較同一深度的點的以其為根的子樹的“結(jié)構(gòu)字典序”的大小）	×
		基于記憶化	\(O(N\log N)\)			√	×	×
樹哈希			\(O(N)\)	×（但幾乎正確，期望沖突率為\(O(\frac{N^2}{W_{Hash}})\)）	√	√	×	×

6.3.1.AHU算法

6.3.1.1.基于樹的最小括號序列表示（樹的最小表示）\(O(N^2)\)

(或者0代表進入一點，)或者1代表出去一點。

復(fù)雜度參考樹形dp和合并子樹信息模型。

string ahu(int id,int u,int fa)  //求出以點u為根的子樹的最小括號序列
{
    vector<string> son_seqs;
    for(int i=head[id][u];i;i=ne[id][i])
    {
        int v=e[id][i];
        if(v==fa) continue;
        son_seqs.push_back(ahu(id,v,u));
    }
    sort(son_seqs.begin(),son_seqs.end());

    string res="("; //進入該點，回溯時該res會自動釋放內(nèi)存
    for(auto s : son_seqs) res+=s;
    res+=')';   //出去該點
    return res;
}

if(ahu(0,wc[0][0].x,0)==ahu(1,wc[1][0].x,0)) cout<<"YES\n";
else
{
    if(wc[0][1].x!=-1 && ahu(0,wc[0][1].x,0)==ahu(1,wc[1][0].x,0)) cout<<"YES\n";
    else cout<<"NO\n";
}

6.3.1.2.基于點的兒子數(shù)組遞推的數(shù)值表示

6.3.1.2.1.基于同一深度的點的以其為根的子樹的“結(jié)構(gòu)字典序”的相對大小\(O(N)/O(N\log N)\)

有根樹的“結(jié)構(gòu)字典序”的大小：對于不同構(gòu)的有根樹\(T_1\)和有根樹\(T_2\)，\(T1,T2\)的根節(jié)點的兒子\(son_1,son_2\)都分別按照以其為根的子樹的‘結(jié)構(gòu)字典序’排序，滿足“任何小于等于其的序號\(j\)都有以\(son_{1,j}\)為根的子樹的‘結(jié)構(gòu)字典序’等于以\(son_{2,j}\)為根的子樹的‘結(jié)構(gòu)字典序’（同構(gòu)）”的最大序號為\(i\)，\(T_1\)的“結(jié)構(gòu)字典序”小于\(T_2\)的“結(jié)構(gòu)字典序”當(dāng)且僅當(dāng)：\(i\)等于\(son_1\)的數(shù)量或者以\(son_{1,i+1}\)為根的子樹的“結(jié)構(gòu)字典序”小于以\(son_{2,i+1}\)為根的子樹的“結(jié)構(gòu)字典序”。

注意必須一起處理所有樹的同一深度的點。

在下面的代碼的cmp中，若采用暴力比較，則總體復(fù)雜度是\(O(N\log N)\)（參考樹上啟發(fā)式合并）；若采用基數(shù)排序，則總體復(fù)雜度是\(O(N)\)。

vector<pii> layer[N];
int fa[2][N];
vector<int> f[2][N];
int tag[2][N];

void dfs2(int id,int u,int d)
{
    layer[d].push_back({id,u});
    for(int i=head[id][u];i;i=ne[id][i])
    {
        int v=e[id][i];
        if(v==fa[id][u]) continue;
        fa[id][v]=u;
        dfs2(id,v,d+1);
    }
    return ;
}

bool cmp(pii x,pii y)
{
    return f[x.x][x.y]<f[y.x][y.y];
}

bool ahu(int rt[])
{
    for(int d=1;d<=n+1/*注意初始化到n+1！！！*/;d++) layer[d].clear();
    for(int id=0;id<=1;id++)
    {
        fa[id][rt[id]]=0;
        for(int u=1;u<=n;u++) f[id][u].clear();
    }
    for(int id=0;id<=1;id++) dfs2(id,rt[id],1);
    for(int d=n;d>=1;d--)
    {
        for(auto it : layer[d+1]) f[it.x][fa[it.x][it.y]].push_back(tag[it.x][it.y]);
        sort(layer[d].begin(),layer[d].end(),cmp);
        int tidx=0;
        for(int i=0;i<layer[d].size();i++)
        {
            if(i && f[layer[d][i].x][layer[d][i].y]!=f[layer[d][i-1].x][layer[d][i-1].y]) tidx++;
            tag[layer[d][i].x][layer[d][i].y]=tidx;
        }
    }
    return tag[0][rt[0]]==tag[1][rt[1]];
}

int rt[2]={wc[0][0].x,wc[1][0].x};
if(ahu(rt)) cout<<"YES\n";
else
{
    rt[0]=wc[0][1].x,rt[1]=wc[1][0].x;
    if(rt[0]!=-1 && ahu(rt)) cout<<"YES\n";
    else cout<<"NO\n";
}

6.3.1.2.2.基于記憶化\(O(N\log N)\)

int tidx;
map<vector<int>,int> h;
int tag[2][N];

void ahu(int id,int u,int fa)
{
    vector<int> son_tags;
    for(int i=head[id][u];i;i=ne[id][i])
    {
        int v=e[id][i];
        if(v==fa) continue;
        ahu(id,v,u);
        son_tags.push_back(tag[id][v]);
    }
    sort(son_tags.begin(),son_tags.end());
    if(!h.count(son_tags)) tag[id][u]=h[son_tags]=++tidx;
    else tag[id][u]=h[son_tags];
    return ;
}

ahu(0,wc[0][0].x,0),ahu(1,wc[1][0].x,0);
if(tag[0][wc[0][0].x]==tag[1][wc[1][0].x]) cout<<"YES\n";
else
{
    if(wc[0][1].x==-1) cout<<"NO\n";
    else
    {
        ahu(0,wc[0][1].x,0);
        if(tag[0][wc[0][1].x]==tag[1][wc[1][0].x]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

6.3.2.樹哈希\(O(N)\)

定義以點u為根的子樹的Hash值\(h(u)=1+\sum\limits_{v\in son_u}f(h(v))\)，其中f是一個隨機函數(shù)。

若f滿足是一個隨機函數(shù)，則幾乎正確，期望沖突率為\(O(\frac{N^2}{W_{Hash}})\)（只需考慮最深的一對沖突點即可）。

還可以對最終的哈希值^=prime[siz[u]]來繼續(xù)提高正確率。

能高效換根，第二次 dp 時只需把子樹Hash減掉即可。

random_device srd;
const ull MASK=mt19937_64(srd())();
ull h[2][N];

//第一種隨機函數(shù)f：xor shift
ull f(ull x)
{
    x^=MASK;
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    x^=MASK;
    return x;
}
/*第二種隨機函數(shù)f：一個隨便找的無特殊性質(zhì)的函數(shù)+擾動
ull shake(ull x)  //擾動，這里可以隨便寫無特殊性質(zhì)的擾動。數(shù)字必須是質(zhì)數(shù)，否則會因保持2^k的同余關(guān)系而增加沖突
{
    return x*x*x*3333331+19260817;
}

ull f(ull x)
{
    return shake(x&((1ull<<31ull)-1))+shake(x>>31ull); //注意不加ull會溢出
}
*/

void dfs2(int id,int u,int father)
{
    h[id][u]=1;
    for(int i=head[id][u];i;i=ne[id][i])
    {
        int v=e[id][i];
        if(v==father) continue;
        dfs2(id,v,u);
        h[id][u]+=f(h[id][v]);
    }
    return ;
}

dfs2(0,wc[0][0].x,0),dfs2(1,wc[1][0].x,0);
if(h[0][wc[0][0].x]==h[1][wc[1][0].x]) cout<<"YES\n";
else
{
    if(wc[0][1].x==-1) cout<<"NO\n";
    else
    {
        dfs2(0,wc[0][1].x,0);
        if(h[0][wc[0][1].x]==h[1][wc[1][0].x]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

6.4.異或Hash

適用條件：只關(guān)心每個元素出現(xiàn)次數(shù)的奇偶性+判斷2個哈希值是否相等。

當(dāng)元素種數(shù)較小時，用一個二進制數(shù)表示每個元素出現(xiàn)次數(shù)的奇偶性，該數(shù)二進制下第k位表示第k種元素出現(xiàn)次數(shù)的奇偶性。遇到一個第k種元素就令x^=(1<<k)。

當(dāng)元素種數(shù)較多時，考慮上面的方法相當(dāng)于p[k]=1<<k;x^=p[k];，其實可以令每個p[k]隨機一個long long范圍的數(shù)for(int k=1;k<=n;k++) p[k]=r64(1e9,1e18)，出現(xiàn)沖突的概率極小。遇到一個第k種元素就令x^=p[k]，然后就像普通異或那樣使用。

進一步提高正確率可以采用雙哈希（兩個隨機數(shù)p[2][k]）。

6.5.Hash

適用條件：一般將實際問題通過某種運算得到它的“特征數(shù)”，但是“特征數(shù)”過大或“特征數(shù)”會有小沖突。

模數(shù)N應(yīng)該是一個遠(yuǎn)離2的次冪的質(zhì)數(shù)。

6.5.1.Hash設(shè)計思路

1. 先在不考慮取模和哈希值較大的情況下，保證哈希值正確率100%。

   把判定相同的條件全部設(shè)計到哈希值。

   技巧：哈希值=狀態(tài)1（\(≤10^x\)）+狀態(tài)2*一個質(zhì)數(shù)（\(>10^x\)）。

2. 取模。

   技巧：多模數(shù)：

const int MOD[2]={651293939,492998489};//隨機多個質(zhì)數(shù)
LL h[2][N]; //h[i][x]：在模數(shù)是MOD[i]情況下x的哈希值
for(int midx=0;midx<2;midx++) h[midx][x]=calc(x)%MOD[midx];
if((h[0][x]==h[0][y]) && (h[1][x]==h[1][y])) puts("same");  //只有當(dāng)多模數(shù)的所有哈希值都相同時，才判定x與y相同

6.5.1.1.pair Hash

pair.first*P+pair.second。其中P是一個大質(zhì)數(shù)，最好大小超過pair.second的值域。

6.5.2.開放尋址法

注意模數(shù)N應(yīng)該是大于題目數(shù)據(jù)范圍的2～3倍的質(zhì)數(shù)。

const int N=200003,INF=0x3f3f3f3f;
int n;
int h[N];

int find(int x)
{
    int res=(x%N+N)%N;
    while(h[res]!=INF && h[res]!=x)
    {
        res++;
        if(res==N) res=0;
    }
    return res;
}

int main()
{
    memset(h,0x3f,sizeof h);
    scanf("%d",&n);
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I') h[find(x)]=x;
        else
        {
            if(h[find(x)]==INF) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

6.5.3.鏈表法

const int N=100003;
int n;
int h[N],e[N],ne[N],idx;

void add(int u,int v)
{
    e[++idx]=v;
    ne[idx]=h[u];
    h[u]=idx;
    return ;
}

bool query(int u,int v)
{
    for(int i=h[u];i!=-1;i=ne[i]) if(e[i]==v) return true;
    return false;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I') add((x%N+N)%N,x);
        else
        {
            if(query((x%N+N)%N,x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

7.雙指針

r++區(qū)間內(nèi)加入一個元素，l++區(qū)間內(nèi)刪除一個元素。

7.1.雙指針

常見問題分類：

1. 答案隨著編號有單調(diào)性。\(O(N)\)。
2. 對于一個序列，用兩個指針維護一段區(qū)間
3. 對于兩個序列，維護某種次序，比如歸并排序中合并兩個有序序列的操作

for (int i = 0, j = 0; i < n; i ++ ){
    while (j < i && check(i, j)) j ++ ;
    // 具體問題的邏輯
}

7.2.回滾雙指針（baka's trick）\(O(N)\)

前提條件：求解的信息具有結(jié)合律。

適用條件：r++區(qū)間內(nèi)加入一個元素的復(fù)雜度較小，l++區(qū)間內(nèi)刪除一個元素的復(fù)雜度較大。

加入一個新指針mid，l≤mid≤r。

lres[i]：[i,mid)的信息。（mid是實時的mid。）

算法的核心。如何不贅余地維護lres[i]見下面的代碼。

rres：[mid,r]的信息。（mid是實時的mid。）

當(dāng)l<mid 時，[l,r]的信息=calc(lres[l],rres)；當(dāng)l==mid 時，[l,r]的信息=rres。

int lres[N],rres;

for(int l=1,r=1,mid=1;l<=n;l++)
{
    if(l>=mid)//>：特判上一輪l=mid=r的情況；=：lres[l]：[l,mid)。
    {
        if(l>r) r=l;//特判上一輪l=mid=r的情況。
        mid=r;
        
        rres=a[r];
        
        lres[mid-1]=a[mid-1];
        for(int i=mid-2;i>=l;i--) lres[i]=calc(a[i],lres[i+1]);
    }
    while(r+1<=n && ((l<mid && check(lres[l],rres,a[r+1])) || (l==mid && check(rres,a[r+1]))))
    {
        r++;
        rres=calc(rres,a[r]);
    }
   if((l<mid && check(lres[l],rres)) || (l==mid && check(rres))) ans[l]=r;
}

8.區(qū)間處理

8.1.區(qū)間合并

步驟：

1. 將所有區(qū)間按左端點排序；
2. 對于每個區(qū)間，它的后面的區(qū)間只有一下三種情況：a. 包含關(guān)系；b. 有交集，但是不包含；c. 毫無關(guān)系。解決方案：對于 a : 直接跳過；對于 b : 延長 ed；對于 c : 輸出區(qū)間，新建一個新區(qū)間。

struct node{
    int x,y;
}a[100005];

bool cmp(node q,node w){
    return q.x<w.x;
}

int main(){
    int n,l=-1e9,r=-1e9,tot=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    
    sort(a+1,a+n+1,cmp);
    
    for(int i=1;i<=n;i++){
        if(a[i].x>r){
            tot++;
            l=a[i].x;
            r=a[i].y;
        }
        else if(a[i].y>r) r=a[i].y;
    }
    
    cout<<tot<<endl;
    return 0;
}

8.2.排除包含區(qū)間

若兩個區(qū)間i\([l_i,r_i]\)和j\([l_j,r_j]\)滿足\(l_j≤l_i≤r_i≤r_j\)，則刪除區(qū)間i。

1. 按左端點遞增，右端點遞減排序區(qū)間。
2. 記錄右端點最大值r。依次遍歷排序后的區(qū)間，若\(r_i≤r\)，則排除區(qū)間i。

9.貪心

遇事不決先排序。

貪心的證明

1. 微擾（鄰項交換）；
2. 范圍縮放：證明對任何局部最優(yōu)策略作用范圍的擴展都不會造成整體結(jié)果變差；
3. 決策包容性；
4. 反證法；
5. 數(shù)學(xué)歸納法。

9.1.區(qū)間問題

9.1.1. 區(qū)間選點問題

9.1.1.1. 一個區(qū)間至少要包含一個點，求點的最少數(shù)量？

1. 將每個區(qū)間按照右端點從小到大進行排序
2. 從前往后枚舉區(qū)間，last值初始化為無窮小

   • 如果本次區(qū)間不能覆蓋掉上次區(qū)間的右端點last<a[i].l

     說明需要選擇一個新的點ans++,last=a[i].r;

   • 如果本次區(qū)間可以覆蓋掉上次區(qū)間的右端點，則直接continue進行下一輪循環(huán)

證明

int n,ans,last=-INF;
struct node{
    int l,r;
    
    bool operator < (const node &t) const{
        return r<t.r;
    }
}a[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    
    sort(a+1,a+n+1);
    
    for(int i=1;i<=n;i++){
        if(a[i].l<=last) continue;
        ans++;
        last=a[i].r;
    }
    
    printf("%d\n",ans);
    
    return 0;
}

9.1.1.2. 曬衣服問題

任意區(qū)間不會重疊包含（但可能會有公共端點），一個區(qū)間至少包含兩個夾子，求夾子的最少數(shù)量？

1. 按右端點排序；
2. 先把公共端點加夾子；
3. 從左往右掃描，在未滿足條件的區(qū)間上加夾子。

9.1.2. 區(qū)間不相交問題（選課、開會問題）

9.1.2.1.求最大不相交（包括端點）區(qū)間數(shù)量？

1. 將每個區(qū)間按照右端點從小到大進行排序
2. 從前往后枚舉區(qū)間，last值初始化為無窮小

   • 如果本次區(qū)間不能覆蓋掉上次區(qū)間的右端點last<a[i].l

     說明需要選擇一個新的點ans++,last=a[i].r;

   • 如果本次區(qū)間可以覆蓋掉上次區(qū)間的右端點，則直接continue進行下一輪循環(huán)

• 證明正解\(ANS<=\)ans

  反證法。
  假設(shè)\(ANS>\)ans，則區(qū)間至少要用\(ANS\)（\(>\)ans）個點才能被完全覆蓋，這與《區(qū)間選點》矛盾。

int n,ans,last=-INF;
struct node{
    int l,r;
    
    bool operator < (const node &t) const{
        return r<t.r;
    }
}a[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    
    sort(a+1,a+n+1);
    
    for(int i=1;i<=n;i++){
        if(a[i].l<=last) continue;
        ans++;
        last=a[i].r;
    }
    
    printf("%d\n",ans);
    
    return 0;
}

9.1.2.2.拓展：選出的區(qū)間不能相交（包括端點），求選出的區(qū)間總長最大值

《錯題本?動態(tài)規(guī)劃2022.9.7.【線性dp】饑餓的奶牛》

9.1.3. 區(qū)間分組問題（開會房間問題）

每組區(qū)間不能相互重疊包含，求最小組數(shù)？

例1：有若干個活動，第\(i\)個活動開始時間和結(jié)束時間是\([si,ei]\)，同一個教室安排的活動之間不能重疊包含（包括公共端點），求要安排所有活動，至少需要幾個教室？
例2： 畜欄預(yù)定

1. 把所有區(qū)間按照左端點從小到大排序；
2. 從前往后枚舉每個區(qū)間，判斷此區(qū)間能否將其放到現(xiàn)有的組中；
   • 如果一個區(qū)間的左端點比最小組的右端點要小，a[i].l<=heap.top()， 就開一個新組heap.push(a[i].r);。
   • 如果一個區(qū)間的左端點比最小組的右端點要大，則放在該組：去除右端點最小的區(qū)間，只保留一個右端點較大的區(qū)間，這樣heap有多少區(qū)間，就有多少組heap.pop(), heap.push(a[i].r);。
3. heap有多少區(qū)間，就有多少組；

• 證明正解\(ANS>=\)ans

  當(dāng)a[i].l<=max_r，要給一個新的區(qū)間開一個新的第ans組時，由于按左端點排序l<=a[i].l且a[i].l<=max_r，所以當(dāng)前ans個區(qū)間相互重疊包含，故至少要ans個分組。

int n;
struct node{
    int l,r;
    bool operator < (const node &t) const{
        return l<t.l;
    }
}a[N];
priority_queue<int,vector<int>,greater<int> > heap;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    
    sort(a+1,a+n+1);
    
    for(int i=1;i<=n;i++){
        if(heap.empty() || heap.top()>=a[i].l) heap.push(a[i].r);
        else{
            heap.pop();
            heap.push(a[i].r);
        }
    }
    
    printf("%d\n",heap.size());
    
    return 0;
}

9.1.4. 區(qū)間覆蓋問題

至少要用多少個區(qū)間才能覆蓋給定的線段（或給定的區(qū)間上的所有點（注意不是邊））？

1. 將所有區(qū)間按照左端點從小到大進行排序；
2. 從前往后枚舉每個區(qū)間，在所有能覆蓋st的區(qū)間中，選擇右端點的最大區(qū)間，然后將st更新成右端點的最大值（如果要求覆蓋的是點，則st更新成右端點的最大值+1）。

• 證明

  正解\(ANS\)可以按照上述操作等價變換成ans。

int n,st,ed,ans;
bool success;
struct node{
    int l,r;
    bool operator < (const node &t) const{
        return l<t.l;
    }
}a[N];

int main(){
    scanf("%d%d%d",&st,&ed,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    
    sort(a+1,a+n+1);
    
    for(int i=1;i<=n;i++){
        int j=i,r=-INF;
        
        //在所有能覆蓋st的區(qū)間中，選擇右端點的最大區(qū)間
        while(j<=n && a[j].l<=st){
            r=max(r,a[j].r);
            j++;
        }
        ans++;
        
        //失敗
        if(r<st) break;
        
        //成功
        if(r>=ed){
            success=true;
            break;
        }
        
        //更新
        st=r;//如果要求覆蓋的是點，則st=r+1;！！！
        i=j-1;  //注意不是j，因為j++之后就跳到新的區(qū)間了
    }
    
    if(!success) puts("-1");
    else printf("%d\n",ans);
    
    return 0;
}

9.2.不等式

9.2.1. 排序不等式

讓花費時間少的人先打水。

• 證明

  設(shè)\(n\)個人打水時間從小到大為\(t_1、t_2、t_3...t_{n-1}、t_n\)。

  則他們按花費時間從小到大排序打水總的等待時間\(T = t_1 * (n-1) + t_2 * (n-2) + t_3 * (n-3) + ... + t_{n-1} * 1\)

  用 微擾（鄰項交換） 的方法發(fā)現(xiàn)微擾后總的等待時間\(T\)增大，證畢。

int n;
LL ans;
int t[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);

    sort(t+1,t+n+1);
    
    for(int i=1;i<=n;i++) ans+=(LL)t[i]*(n-i);
    
    printf("%lld\n",ans);
    
    return 0;
}

9.2.2. 絕對值不等式

利用中位數(shù)的性質(zhì)。

• 證明

  設(shè)\(n\)個倉庫坐標(biāo)從小到大為\(x_1、x_2...x_{n-1}、x_n\)，貨倉坐標(biāo)為\(x\)。

  則貨倉到每家商店的距離之和$dis = |x_1-x| + |x_2-x| + ... + |x_{n-1}-x| + |x_n-x| = (|x_1-x| + |x_n-x|) + (|x_2-x| + |x_{n-1}-x|) + ... $

  利用 數(shù)學(xué)上絕對值的幾何意義 ，$dis \geqslant (x_n-x_1) + (x_{n-1}-x_2) + ... \(，當(dāng)\)x \in [x_1,x_n]、[x_2,x_{n-1}]、...\(時取到等號，即\)x$為中位數(shù)，證畢。

寫法1：中位數(shù)

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

const int N=1e5+5;
int n,ans;
int x[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    
    sort(x+1,x+n+1);
    
    for(int i=1;i<=n;i++) ans+=abs(x[i]-x[n/2+1]);  //注意這里的n/2+1才是中位數(shù)
    
    printf("%d\n",ans);
    
    return 0;
}

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,ans; int x[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x[i]); sort(x+1,x+n+1); int i=1,j=n; while(i<=j){ ans+=(x[j]-x[i]); i++,j--; } printf("%d\n",ans); return 0; }

9.2.3. 推公式

• 例題1. 耍雜技的牛

  按\(w[i]+s[i]\)從小到大排序。

  題解：證明：微擾（鄰項交換）

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

typedef pair<int,int> PII;
const int N=5e4+5,INF=2e9;
int n,sum,ans=-INF;
PII cow[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int w,s;
        scanf("%d%d",&w,&s);
        cow[i]={w+s,w};
    }
    
    sort(cow+1,cow+n+1);
    
    for(int i=1;i<=n;i++){
        int w=cow[i].second,s=cow[i].first-cow[i].second;
        ans=max(ans,sum-s);
        sum+=w;
    }
    
    printf("%d\n",ans);
    
    return 0;
}

• 例題2. 防曬

  1. 將所有奶牛按照 minSPF 從大到小 的順序排序，然后依次考慮每頭奶牛；
  2. 對于每頭奶牛，掃描當(dāng)前所有能用的防曬霜，選擇 SPF 值最大的防曬霜來用；

  • 證明

    用 決策包容性 的方法：

    由于所有奶牛按照minSPF從大到小的順序排序，所以每一個不低于當(dāng)前奶牛\(minSPF\)值的防曬霜，都不會低于后面其他奶牛的\(minSPF\)值。

    換言之，對于當(dāng)前奶牛可用任意兩瓶防曬霜\(x\)和\(y\)（設(shè)\(spf[x]<spf[y]\)），后面的奶牛只可能出現(xiàn)“\(x\)、\(y\)都能用”、“\(x\)、\(y\)都不能用”和“\(x\)能用，\(y\)****不能用”。因此當(dāng)前奶牛選擇\(spf\)比較大的\(y\)對整體的影響比\(x\)好。

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

const int N=2505;
int n,m,ans;

struct Cow{
    int mi,ma;
    bool operator < (const Cow W) const{
        return mi>W.mi;
    }
}cow[N];

struct SPF{
    int s,c;
    bool operator < (const SPF W) const{
        return s>W.s;
    }
}spf[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&cow[i].mi,&cow[i].ma);
    for(int i=1;i<=m;i++) scanf("%d%d",&spf[i].s,&spf[i].c);

    sort(cow+1,cow+n+1);
    sort(spf+1,spf+m+1);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(cow[i].mi<=spf[j].s && spf[j].s<=cow[i].ma && spf[j].c!=0){
                spf[j].c--;
                ans++;
                break;
            }

    printf("%d\n",ans);

    return 0;
}

9.3.數(shù)據(jù)特征值

9.3.1.平均數(shù)

適用條件：平均分。

定義：\(E(X)=\frac{\sum\limits_{i=1}^{n}x[i]}{n}\)。

9.3.1.1.均分紙牌

算平均數(shù)ave。求每堆紙牌與平均數(shù)的關(guān)系（多1記為1，少1記為-1。即牌數(shù)-平均數(shù)）。當(dāng)a[i]（第i堆紙牌與平均數(shù)的關(guān)系）不等于0時，令a[i+1]=a[i+1]+a[i]（當(dāng)a[i]<0時從第i+1個牌堆向第i個牌堆移|a[i]|張紙牌，當(dāng)a[i]>0時從第i個牌堆向第i+1個牌堆移|a[i]|張紙牌），牌堆的移動次數(shù)加1，牌的移動數(shù)量加|a[i]|。

int n,ave,ans1,ans2;    //ave：平均數(shù)；ans1：牌堆的最少移動次數(shù)；ans2：牌的最少移動數(shù)量
int a[N];

scanf("%d",&n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    ave+=a[i];
}
ave/=n;
for(int i=1;i<=n;i++) a[i]-=ave;
for(int i=1;i<=n;i++)
{
    if(a[i]==0) continue;
    a[i+1]+=a[i];
    ans1++;
    ans2+=abs(a[i]);
}
printf("%d %d\n",ans1,ans2);

9.3.2.中位數(shù)

適用條件：絕對值不等式。

定義：序列X排序后，\(\begin{cases} x_{\frac{n+1}{2}}&n\text{ is odd} \\\frac{x_{\frac{n}{2}}+x_{\frac{n}{2}+1}}{2}&n\text{ is even} \end{cases}\)。

9.3.2.1.貨倉選址

9.3.2.1.1.貨倉選址

見《基礎(chǔ)算法9.2.2. 絕對值不等式 》。

9.3.2.1.2.帶權(quán)貨倉選址

求\(f(x)=\sum\limits_i b_i|a_i-x|\)。

利用《思維題技巧12.絕對值的處理2.》的技巧：\(f(x)=(\sum\limits_{a_i\ge x} b_ia_i-\sum\limits_{a_i<x} b_ia_i)+x(\sum\limits_{a_i\ge x} b_i-\sum\limits_{a_i<x} b_i)\)。

對于一個確定的x求\(f(x)\)：利用建立在值域上、支持查詢前綴和的數(shù)據(jù)結(jié)構(gòu)，f(x)=總和-2*<x的前綴和。

性質(zhì)

求\(\min f(x)\)：若\(b_i≥0\)，f(x)是下凸函數(shù)且只有最值處有平臺，所以可以使用三分求\(\min f(x)\)。

例題。

9.3.2.2.環(huán)形均分紙牌

求牌的最少移動數(shù)量。

平均數(shù)與中位數(shù)的綜合應(yīng)用。

核心：將式子化為只有一個未知數(shù)。

設(shè)a[i]：第i個牌堆原有的牌數(shù)。ave：所有牌堆的牌數(shù)的平均數(shù)。

可將向左傳和向右傳合并：設(shè)x[i]：第i個牌堆向左傳的牌數(shù)-第i-1（當(dāng)i=1時為n）堆向右傳的牌數(shù)。

有：a[i]+x[i+1]-x[i]=ave(1≤i<n)。（方程a[n]+x[1]-x[n]=ave無用，因為可被前面的方程線性表示。）

設(shè)\(c[i]=(\sum\limits_{j=1}^{i} a[j])-i*ave\)。則對上面的式子變形有：x[i]=x[1]-c[i-1]（特別地，c[0]=0）。

牌的移動數(shù)量ans=|x[1]|+|x[2]|+...+|x[n]|=|x[1]-c[0]|+|x[1]-c[1]|+...+|x[1]-c[n-1]|。由《基礎(chǔ)算法9.3.2.1.貨倉選址》得當(dāng)x[1]取序列c[0~n-1]的中位數(shù)時，ans有最小值。

n=read();
for(int i=1;i<=n;i++)
{
    a[i]=read();
    ave+=a[i];
}
ave/=n;
c[0]=0;
for(int i=1;i<n;i++) c[i]=c[i-1]+a[i]-ave;
sort(c,c+n);
mid=c[n/2];
for(int i=0;i<n;i++) ans+=abs(mid-c[i]);
printf("%lld\n",ans);

9.3.3.眾數(shù)

一般定義的眾數(shù)不滿足區(qū)間可加性和結(jié)合律。

9.3.3.1.摩爾投票法求絕對眾數(shù)

前提條件：絕對眾數(shù)：保證眾數(shù)的個數(shù)嚴(yán)格大于總數(shù)的一半。

絕對眾數(shù)滿足區(qū)間可加性。

9.3.3.1.1.靜態(tài)求全局絕對眾數(shù)

時間復(fù)雜度：\(O(N)\)。空間復(fù)雜度：\(O(1)\)。

記錄2個變量：major,cnt：當(dāng)前摩爾投票的結(jié)果和計數(shù)器。初始cnt=0。當(dāng)cnt==0時，當(dāng)前摩爾投票沒有結(jié)果。

依次讀入x和y，表示給定了y個x。若當(dāng)前major==x，令cnt+=y；若當(dāng)前major≠x，比較cnt和y的大小，若cnt≥y，令major不變，cnt-=y，否則更新當(dāng)前摩爾投票的結(jié)果，令major=x,cnt=y-cnt。掃描完后major就是答案。

理解：現(xiàn)在有2伙人（是絕對眾數(shù)的一伙，不是眾數(shù)的另一伙）打架，每個人的戰(zhàn)斗力都是1換1，由于保證前提條件“絕對眾數(shù)的個數(shù)嚴(yán)格大于總數(shù)的一半”，所以摩爾投票法最后剩下的數(shù)一定是絕對眾數(shù)。

int major,cnt;
for(int i=1;i<=m;i++)
{
    int x,y;
    scanf("%d%d",&x,&y);
    if(major==x) cnt+=y;
    else
    {
        if(cnt>=y) cnt-=y;
        else major=x,cnt=y-cnt;
    }
}
printf("%d\n",major);

9.3.3.1.2.靜態(tài)求區(qū)間絕對眾數(shù)

主席樹的節(jié)點維護其對應(yīng)的值域上的數(shù)的出現(xiàn)次數(shù)sum，版本維護區(qū)間。

• 對于一個詢問[l,r]，若當(dāng)前區(qū)間的左兒子的版本r減版本l的sum的2倍大于r-l+1，說明可能的答案只可能在左兒子。
• 否則若當(dāng)前區(qū)間的右兒子的版本r減版本l的sum的2倍大于r-l+1，說明可能的答案只可能在右兒子。
• 否則[l,r]不存在絕對眾數(shù)。

代碼鏈接。

9.3.3.1.3.動態(tài)求全局絕對眾數(shù)

摩爾投票法使得眾數(shù)滿足區(qū)間可加性。因此建立一棵權(quán)值線段樹，線段樹節(jié)點記錄siz,major,cnt表示區(qū)間所有數(shù)的個數(shù)、當(dāng)前區(qū)間摩爾投票的結(jié)果和計數(shù)器，根據(jù)摩爾投票的思想很容易寫出pushup：

void pushup(int u)
{
    if(!u) return;
    tr[u].siz=tr[tr[u].lson].siz+tr[tr[u].rson].siz;
    if(tr[tr[u].lson].major==tr[tr[u].rson].major) tr[u].major=tr[tr[u].lson].major,tr[u].cnt=tr[tr[u].lson].cnt+tr[tr[u].rson].cnt;
    else if(tr[tr[u].lson].cnt>=tr[tr[u].rson].cnt) tr[u].major=tr[tr[u].lson].major,tr[u].cnt=tr[tr[u].lson].cnt-tr[tr[u].rson].cnt;
    else tr[u].major=tr[tr[u].rson].major,tr[u].cnt=tr[tr[u].rson].cnt-tr[tr[u].lson].cnt;
    return ;
}

如果有多棵權(quán)值線段樹，則繼續(xù)把它們根節(jié)點的摩爾投票結(jié)果再進行摩爾投票得到最后1個結(jié)果。

最后還要檢驗最終的那1個結(jié)果是否是絕對眾數(shù)：每棵權(quán)值線段樹都統(tǒng)計出最終的那1個結(jié)果的出現(xiàn)個數(shù)和所有數(shù)的個數(shù)，判斷是否最終的那1個結(jié)果的個數(shù)嚴(yán)格大于所有數(shù)的一半。

9.3.3.1.4.動態(tài)求區(qū)間絕對眾數(shù)

把《基礎(chǔ)算法9.3.3.1.2.動態(tài)求全局絕對眾數(shù)》中的權(quán)值線段樹（葉子節(jié)點i儲存數(shù)值i的出現(xiàn)次數(shù)）替換成普通線段樹（葉子節(jié)點i儲存位置i上的數(shù)值）。對于動態(tài)查詢區(qū)間內(nèi)數(shù)值maj的出現(xiàn)次數(shù)，對于每一個數(shù)值maj開一個平衡樹儲存數(shù)值是maj的位置，在數(shù)值maj的平衡樹查詢位置小于等于r和小于等于l-1的大小，相減就可以了。

代碼鏈接。

9.3.4.方差

• \(D(X)=\frac{\sum\limits_{i=1}^n(x_i-\bar{x})^2}{n}=\frac{\sum\limits_{i=1}^nx_i^2}{n}-\bar{x}^2=E(X^2)-E^2(X)\)。
• 直觀理解：數(shù)據(jù)的離散程度。數(shù)據(jù)越分散（集中），方差越大（小）。
• 設(shè)S,T是兩個（可重）集合，D(S)≤D(T)，則D(S∪T)≥D(S)。

9.4.鄰項交換

前提條件：交換前的答案與交換后的答案列出的不等式化簡后不含除i、i+1其他的項。

適用條件：題目需要一個最優(yōu)的序列順序，因此需要排序的關(guān)鍵字。

假設(shè)得到了最優(yōu)的排序方式\(a_1,a_2,...,a_n\)，交換相鄰的兩項i和i+1，將交換前的答案與交換后的答案列一個不等式\(calc(a_i,a_{i+1})<calc(a_{i+1},a_i)\)，化簡整理后會得到\(f(a_i)<f(a_{i+1})\)。于是我們就得到了排序的關(guān)鍵字。

• 正確性

  根據(jù)冒泡排序的知識，任何一個序列都能通過鄰項交換的方式變成有序序列。

注意

• sort中的cmp函數(shù)的含義是：當(dāng)cmp(i,j)返回true時，i排在j前面。
• 《基礎(chǔ)算法3.5.嚴(yán)格弱序化》。

9.5.反悔貪心思想

前提條件：1.反悔涉及的決策不能過多，保證復(fù)雜度；2.花費只與當(dāng)前決策有關(guān)。

適用條件：有時候在滿足題目約束條件（\(e.g.\)物品有使用期限，或是需要選擇k個物品）和達(dá)成最優(yōu)解的時候會產(chǎn)生矛盾，但是不管題目條件，一味地追求達(dá)成最優(yōu)解是很容易做到的。

圖論上的反悔貪心：網(wǎng)絡(luò)流。

1. 思考選擇一個決策會導(dǎo)致哪些決策不能被選擇，如何在遍歷到那些不能被選擇的決策時用堆判斷是否反悔之前的決策，如何反悔之前的決策。
2. 用堆維護當(dāng)前最優(yōu)決策和反悔決策。（可能合并到一個就夠了。也可能對于\(b_j-a_i\)的式子需要將式子拆開成\(b_j\)和\(-a_i\)用兩個堆維護，這樣就可以把多個反悔決策縮小到一個反悔決策）
3. 分題型：

   • 若題目對選擇物品的總數(shù)無限制，且是一元條件：

     依次遍歷排序后的決策。無論當(dāng)前的最優(yōu)決策是否全局最優(yōu)都接受。如果不能接受當(dāng)前的最優(yōu)決策，將該決策與之前選過的決策（用堆維護）進行比較。

     例題：Luogu P2949 [USACO09OPEN]Work Scheduling G。

   • 若題目要求選k個物品：

     1. for(int i=1;i≤k;i++)：以當(dāng)前選了i個物品為階段。

     2. 比較當(dāng)前是直接選擇還是反悔。有時兩者可以合并到一起。

        反悔時，因為當(dāng)前是以選了i個物品為階段，所以要保證i=選擇物品總數(shù)。也就是相對i-1要有增量。\(e.g.\)反悔選之前的1個物品則還要同時再選2個物品（注意反悔之后決策的范圍有變動），相當(dāng)于之前和現(xiàn)在的決策分別選擇這2個物品。

     3. 加入貢獻(xiàn)。

     4. 選擇了一個決策，會導(dǎo)致其他決策不能被選擇，這時要把相關(guān)決策全部移出，把反悔費用累加加入到堆中。

        移動相關(guān)決策狀態(tài)時，若物品的決策狀態(tài)多（\(e.g.\)不選/選1個/選2個當(dāng)前的物品），則可以考慮寫一個函數(shù)insert_x(id)：將第id個物品的決策狀態(tài)納入狀態(tài)x；erase_x(id)：將第id個物品的決策狀態(tài)移出狀態(tài)x。

     例題1：Luogu P3620 [APIO/CTSC2007] 數(shù)據(jù)備份。

     例題2：CF436E Cardboard Box。

9.6.\(Huffman\)樹

《數(shù)據(jù)結(jié)構(gòu)4.2.\(Huffman\)樹》

數(shù)據(jù)結(jié)構(gòu)·序列

10.高精度

高精度封裝。

一般用a表示低精度或字符串，A表示高精度。

算法流程模擬筆算。

兩個高精度運算要比較大小避免特判。

10.1.可以不用高精度的情況

10.1.1.有模數(shù)的情況

適用條件：模數(shù)在long long范圍內(nèi)。對輸入的數(shù)據(jù)取模答案沒有影響。

秦九韶算法。

int n,len;
char s[N];

scanf("%s",s+1);
len=strlen(s+1);
for(int i=1;i<=len;i++) n=(n*10+s[i]-'0')%MOD;

10.1.2.__int128

適用條件：數(shù)值的絕對值小于\(2^{128}-1\)。

注意

• __int128不可以使用cin、cout、scanf、printf等輸入輸出。

  讀入和輸出：使用把int改成__int128的快讀和快寫的模板。

  《生活小妙招 快讀和快寫》

• __int128 res=(__int128)12345678901234567890123456789;仍然會溢出。（因為該代碼的執(zhí)行步驟是將long long類型的12345678901234567890123456789（此時已經(jīng)溢出）轉(zhuǎn)化為__int128）

• __int128 res=1234567890123456789*1234567890132456789;會溢出。

  應(yīng)改為__int128 res=(__int128)1234567890123456789*1234567890132456789;

10.2.高精度的讀入和輸出

//讀入
char a[N];
int lena;
vector<int> A;
scanf("%s",a+1);
lena=strlen(a+1);
for(int i=lena;i>=1;i--) A.push_back(a[i]-'0');

//輸出
for(int i=A.size()-1;i>=0;i--) printf("%d",A[i]);

10.3.高精度的比較

//判斷A是否大于B
bool cmp(vector<int> &A,vector<int> &B)
{
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--) if(A[i]!=B[i]) return A[i]>B[i];
    return false;    //注意這里要返回false，嚴(yán)格弱序化
}

10.4.高精度加法

10.4.1.高精度加法（不壓位）

vector<int> add(vector<int> &A,vector<int> &B)//加引用效率會高一些
{
    if(A.size()<B.size()) return add(B,A);//要比較大小
    int t=0;//進位
    vector<int> C;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t!=0) C.push_back(t);
    return C;
}

vector<int> A,B,C;
C=add(A,B);

10.5.高精度減法

vector<int> sub(vector<int> &A,vector<int> &B)
{
    if(cmp(B,A))//注意cmp是<。如果改為!cmp(A,B)則當(dāng)A=B會輸出-0
    {
        putchar('-');
        return sub(B,A);
    }
    int t=0;    //借位
    vector<int> C;
    for(int i=0;i<A.size();i++)
    {
        t=A[i]-t;
        if(i<B.size()) t-=B[i];
        C.push_back((t%10+10)%10);
        if(t<0) t=1;
        else t=0;
    }
    while(C.size()>1 && C.back()==0) C.pop_back();  //刪除前導(dǎo)零，注意答案為0時要保留一個0
    return C;
}

vector<int> A,B,C;
C=sub(A,B);

10.5.高精度乘法

10.5.1.高精乘低精（不壓位）

vector<int> mul(vector<int> &A,LL b)//不要忘記開long long
{
    LL t=0;    //進位
    vector<int> C;
    for(int i=0;i<A.size() || t!=0;i++)
    {
        if(i<A.size()) t+=A[i]*b;//不開long long這里會爆！！！
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1 && C.back()==0) C.pop_back();  //刪除前導(dǎo)零，例如A*0，注意答案為0時要保留一個0
    return C;
}

vector<int> A,C;
LL b;
C=mul(A,b);

10.5.2.高精乘高精：FFT\(O(N\log N)\)

《數(shù)學(xué)..1.1.FFT求高精度乘法\(O(N\log N)\)》

10.6.高精度除法

10.6.1.高精除低精

輸出商和余數(shù)。

vector<int> divi(vector<int> &A,LL b,LL &r)//不要忘記開long long
{
    r=0;    //余數(shù)
    vector<int> C;
    for(int i=A.size()-1;i>=0;i--)  //，注意為了少用reverse節(jié)省時間，從高位到低位
    {
        r=r*10+A[i];//不開long long這里會爆！！！
        C.push_back(r/b);
        r%=b;
    }
    reverse(C.begin(),C.end()); //注意記得翻轉(zhuǎn)
    while(C.size()>1 && C.back()==0) C.pop_back();  //刪除前導(dǎo)零，例如A*0，注意答案為0時要保留一個0
    return C;
}

vector<int> A,C;
LL b,r;

10.7.高精度短除法

《基礎(chǔ)算法11.1.3.\(()_x→()_y\)》

11.進位制

11.1.進制轉(zhuǎn)化

11.1.1.\(()_x→()_{10}\)

秦九韶算法：\(e.g.\)\((615023)_7→()_{10}\)：((((67+1)7+5)7+0)7+2)*7+3

11.1.2.\(()_{10}→()_x\)

短除法：\(a_i\%x\)，\(\lfloor \dfrac{a_i}{x} \rfloor\)

11.1.3.\(()_x→()_y\)

方法一（更常用）

短除法：\(a_i\%y\)，\(\lfloor \dfrac{a_i}{y} \rfloor\)。注意：除法借位時應(yīng)該加x而不是10！！！

由于除法借位的問題，我們用高精度短除法實現(xiàn)。

vector<int> divi(vector<int> &C,int a,int b)
{
    vector<int> Res;
    while(C.size())
    {
        int r=0;    //余數(shù)
        for(int i=C.size()-1;i>=0;i--)
        {
            C[i]+=a*r;
            r=C[i]%b;
            C[i]/=b;
        }
        Res.push_back(r);
        while(!C.empty()/*注意這里不是size>1*/ && C.back()==0) C.pop_back();//可以在稿紙上模擬一下，此處不需要翻轉(zhuǎn)
    }
    return Res; //可以在稿紙上模擬一下，此處不需要翻轉(zhuǎn)
}

int main()
{
    char c[N];
    int lenc;
    vector<int> C,Res;
    scanf("%s",c+1);
    lenc=strlen(c+1);
    for(int i=lenc;i>=1;i--) C.push_back(c[i]-'0');
    int a,b;
    scanf("%d%d",&a,&b);
    Res=divi(C,a,b);
    for(int i=Res.size()-1;i>=0;i--) printf("%d",Res[i]);
    return 0;
}

方法二

\(()_x→()_{10}→()_y\)

12.啟發(fā)式合并

適用條件：\(\sum=N\)，無論合并的信息多么復(fù)雜。

時間復(fù)雜度：\(O(x*N \log N)\)，其中x是合并一次的復(fù)雜度。

12.1.啟發(fā)式合并

適用條件：初始多個集合，依次合并2個集合合并至最終1個集合。（不會把集合分裂，否則不能保證復(fù)雜度）

每次合并集合，操作小集合合并到大集合。

12.2.樹上啟發(fā)式合并

當(dāng)一個子樹的信息是數(shù)組級別，且要向上傳遞到父節(jié)點時（例如求出每個子樹的最多節(jié)點顏色）。可以只使用一個數(shù)組，先遞歸求解“輕兒子”，回溯時清空數(shù)據(jù)。再遞歸求解“重兒子”并保留數(shù)據(jù)。然后再遞歸除“重兒子”以外的節(jié)點，把他們的信息加入這份數(shù)據(jù)，就得到了這顆子樹的數(shù)據(jù)。

不能高效換根。

以求出每個子樹的最多節(jié)點顏色為例：

int siz[N],son[N];  //son[u]：節(jié)點u的重兒子
int ma,color[N],cnt[N];LL sum;  //color[i]：節(jié)點i的顏色；cnt[i]、ma、sum：顏色統(tǒng)計，除重兒子外，回溯時將被清空
LL ans[N];

int dfs_son(int u,int fa)//求出每棵子樹的"重兒子"
{
    siz[u]=1;
    for(int i=h[u];i!=0;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        siz[u]+=dfs_son(v,u);
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
    return siz[u];
}

void update(int u,int fa,int sign,int pson)//sign==1：二次遞歸求解；-1：數(shù)據(jù)清空器
{
    int c=color[u];
    cnt[c]+=sign;//二次遞歸求解或數(shù)據(jù)清空體現(xiàn)在這里
    if(cnt[c]>ma) ma=cnt[c],sum=c;
    else if(cnt[c]==ma) sum+=c;
    
    for(int i=h[u];i!=0;i=ne[i])
    {
        int v=e[i];
        if(v==fa || v==pson) continue;  //重兒子已經(jīng)統(tǒng)計過了。注意是pson而不是son[u]
        update(v,u,sign,pson);
    }
    
    return ;
}

void dfs(int u,int fa,bool is_son)//is_son==true表示u是fa的重兒子，回溯時不清空數(shù)據(jù)
{
    for(int i=h[u];i!=0;i=ne[i])
    {
        int v=e[i];
        if(v==fa || v==son[u]) continue;//先求解“輕兒子”
        dfs(v,u,false);
    }
    if(son[u]) dfs(son[u],u,true);//求解“重兒子”并儲存數(shù)據(jù)
    update(u,fa,1,son[u]);
    
    ans[u]=sum;
    
    if(!is_son) update(u,fa,-1,0),ma=sum=0;//“輕兒子”清空數(shù)據(jù)
    
    return ;
}

13.隨機化算法

13.1.模擬退火和爬山法

《搜索5.模擬退火》

《搜索6.爬山法》

13.2.隨機化dp

《動態(tài)規(guī)劃7.5.隨機化dp》

13.3.基于概率的隨機化算法

題目的某個性質(zhì)或做法雖然沒有得到證明，但是通過計算發(fā)現(xiàn)其正確率可高達(dá)99%以上。

模型一

特征：答案集合占總集合的比例較大，現(xiàn)需要選出x（x較小）個在答案集合里的元素。

計算隨機選出x個元素均在答案集合里的概率，再計算多次隨機選出均失敗的概率，發(fā)現(xiàn)極小。

多次隨機選出x個元素，驗證是否均在答案集合或求最值。

14.構(gòu)造

一般答案不唯一，但是可以通過某種規(guī)律找到一種答案。可能需要用到貪心，也可能是借助dp輸出方案來構(gòu)造方案。

很多構(gòu)造題都是思維題：

思維題

14.1.嚴(yán)格不等\(\Leftrightarrow\)非嚴(yán)格不等

給定一個整數(shù)序列 a1,a2,???,an。

請你求出一個遞增序列 b1<b2<???<bn，使得|a1?b1|+|a2?b2|+???+|an?bn| 最小。

1. 嚴(yán)格不等→非嚴(yán)格不等
   令$a_i $→ \(a_{i}'\)（\(a_i'=a_i-i\)），$b_i $→ \(b_{i}'\)（\(b_i'=b_i-i\)）。

   此時只需求出b1'≤b2'≤...≤bn'，且|a1?b1|+|a2?b2|+???+|an?bn| =|a1'?b1'|+|a2'?b2'|+???+|an'?bn'| 。

2. 非嚴(yán)格不等→嚴(yán)格不等

   令上面的-i改成+i即可。

• .2.構(gòu)造奇數(shù)價幻方

  首先將?1?寫在第一行的中間。

  之后，按如下方式從小到大依次填寫每個數(shù) K(K=2,3,…,N×N)：

  1.?若?(K?1)?在第一行但不在最后一列，則將 K 填在最后一行，(K?1)?所在列的右一列；?
  2.?若?(K?1)?在最后一列但不在第一行，則將 K 填在第一列，(K?1)?所在行的上一行；?
  3.?若?(K?1)?在第一行最后一列，則將 K 填在?(K?1)?的正下方；?
  4.?若?(K?1)?既不在第一行，也不在最后一列，如果?(K?1)?的右上方還未填數(shù)，則將 K 填在 (K?1) 的右上方，否則將 K 填在?(K?1)?的正下方。

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

const int N=40;
int n,x,y;
int a[N][N];

int main()
{
    scanf("%d",&n);
    int x=1,y=n/2+1;
    for(int i=1;i<=n*n;i++)
    {
        a[x][y]=i;
        if(x==1 && y==n) x++;
        else if(x==1) x=n,y++;
        else if(y==n) x--,y=1;
        else if(a[x-1][y+1]!=0) x++;
        else x--,y++;
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) printf("%d ",a[i][j]);
        puts("");
    }
    
    return 0;
}

14.2.抽屜原理

適用條件：遇到n/k這樣的操作次數(shù)。

將所有的元素分成k個集合。這樣根據(jù)抽屜原理，最小的集合的大小≤n/k，最大的集合的大小≥n/k。

有3個方向把所有的元素分類：把所有的元素分類后，

1. 選擇其中任意一個集合。

   要求分類后所有集合全都滿足要求。

2. 只對一個集合內(nèi)所有的元素操作。

   要求每個集合都完全覆蓋。

3. 給每個集合定一個屬性，把每個集合內(nèi)的所有元素都改成其所在集合的屬性。

   要求改完之后滿足題目條件。

14.3.歸納法

適用條件：1.操作的執(zhí)行有順序；2.在“判斷是否有解，有解輸出方案”中的題目可能會用到歸納法。

有的題目可能要先找到充要條件，有的可能要先執(zhí)行步驟2后才能發(fā)現(xiàn)充要條件。有的題目可能要通過充要條件判斷是否有解，有的可能要在步驟2無法執(zhí)行時判斷無解。

1. 找到有解的充要條件。它既可以有時判斷原問題是否有解，又可以輔助思考solve(n)如何轉(zhuǎn)化為solve(n-1)。
2. 將原問題solve(n)轉(zhuǎn)化為規(guī)模減一的一定有解的子問題solve(n-1)。既是歸納的證明，又是構(gòu)造的方案。可能的歸納方向：
   1. 假設(shè)已經(jīng)構(gòu)造了solve(n-1)的方案，現(xiàn)在把第n個元素加入。
   2. 逆向思考：先處理第n個元素，使得solve(n-1)一定有解并遞歸處理solve(n-1)。
3. 有的時候還需要配合：
   1. 增減法：分類討論第n個元素的權(quán)值大小，決定如何處理第n個元素，得到總權(quán)值的變化，證明solve(n-1)滿足充要條件。例題。
   2. 反證法：大膽猜測結(jié)論或特殊性質(zhì)，通過反證法證明結(jié)論或特殊性質(zhì)。例子。

14.4.dfs樹

適用條件：無向連通圖的題目中，數(shù)據(jù)范圍給了樹的特殊分，有時可以往“樹的做法+返祖邊→無向連通圖的做法”的方向想。

dfs樹的性質(zhì)：非樹邊只有返祖邊。

14.5.“兩個任務(wù)一定可以完成其中一個任務(wù)”

適用條件：給定兩個任務(wù)，一般任務(wù)都是要求找到由限制+本體組成的物體，選擇其中任意一個任務(wù)完成，保證兩個任務(wù)一定可以完成其中一個任務(wù)。

1. 先考慮其中較為簡單的任務(wù)。先不管限制找到本體，若找到的本體本來就滿足限制，直接輸出。
2. 若找到的本體不滿足限制，寫出此時的不等式。在滿足該不等式的情況下構(gòu)造完成另一個任務(wù)的方案。

14.6.轉(zhuǎn)化為圖論

沒有特定的適用條件。原題目可能與圖論無關(guān)，但是可以利用特殊圖的性質(zhì)轉(zhuǎn)化為圖論的等價條件，從而構(gòu)造方案。

1. 環(huán)。

   可以此構(gòu)造置換p[i]，然后可列出等式\(\sum i=\sum p[i]\)。

2. 鄰接矩陣。

   將只含0,1的矩陣乘法轉(zhuǎn)化為bool的鄰接矩陣。

   https://www.luogu.com.cn/problem/T268089

3. 二分圖

   二分圖染色可以解決2選1問題。二分圖本身還有建模應(yīng)用。

4. 2-sat

14.7.漢諾塔問題

核心：先移動除最大塔以外的其他塔，再移動最大塔，然后移動其他塔→先考慮最大塔，然后把問題遞歸為考慮除最大塔以外的其他塔的子問題。

14.7.1.求3柱漢諾塔從初始狀態(tài)轉(zhuǎn)移到目標(biāo)狀態(tài)的最小步數(shù)

結(jié)論：串a(chǎn)aa的長度為n，從aaa轉(zhuǎn)移到bbb的最小步數(shù)\(=2^n-1\)。

性質(zhì)：基于3進制的性質(zhì)，考慮第一步的決策后，后面可能的最優(yōu)決策是唯一確定的。

先考慮最大塔的決策，從xxxa→xxxb（則第三柱c=6-a-b，x表示任意柱）有2種路線

1. 從xxxa花費未知費用走到bbba，從bbba花費1費用走到bbbc，從bbbc花費\(2^{n-1}-1\)費用走到aaac，從aaac花費1費用走到aaab，從aaab花費未知費用走到xxxb。
2. 從xxxa花費未知費用走到ccca，從ccca花費1費用走到cccb，從cccb花費未知費用走到xxxb。

現(xiàn)在的問題變成了如何求出從xxx走到aaa/bbb/ccc的費用（從aaa/bbb/ccc走到xxx的費用=從xxx走到aaa/bbb/ccc的費用）。由于最終目標(biāo)是同一柱，所以可能的最優(yōu)決策是唯一確定的：以求從xxa走到bbb的費用，xxa的長度是i為例：從xxa花費未知費用走到cca，從cca花費1費用走到ccb，從ccb花費\(2^{i-1}-1\)費用走到bbb。現(xiàn)在的子問題變成了求xx走到cc的費用，直接遞歸求解即可。

例題。

//原題要寫壓位高精。這里因為只突出漢諾塔的思想，所以沒寫壓位高精
int n;
int a[N],b[N];
i128 ans1,ans2;

//路線1
void solve1()
{
    ans1+=1;    //從bbba花費1費用走到bbbc
    ans1+=(i128(1)<<(n-1))-1;   //從bbbc花費2^{n-1}-1費用走到aaac
    ans1+=1;    //從aaac花費1費用走到aaab
    
    /*
    從xxxa花費未知費用走到bbba、從aaab花費未知費用走到xxxb
    子問題都是求出從xxx走到aaa/bbb/ccc的費用（從aaa/bbb/ccc走到xxx的費用=從xxx走到aaa/bbb/ccc的費用）
    下面用迭代寫法代替遞歸寫法，實際上迭代寫法也很可讀
    */
    int c1=b[n],c2=a[n];    //當(dāng)前子問題的最大塔的目標(biāo)柱
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]!=c1)    //如果初始就在目標(biāo)柱的話就不用移動了
        {
            ans1+=1;    //從cca花費1費用走到ccb
            ans1+=(i128(1)<<(i-1))-1;   //從ccb花費2^{i-1}-1費用走到bbb
            c1=6-a[i]-c1;   //從xxa花費未知費用走到cca。下一輪的子問題變成了求xx走到cc的費用
        }
        if(b[i]!=c2)
        {
            ans1+=1;
            ans1+=(i128(1)<<(i-1))-1;
            c2=6-b[i]-c2;
        }
    }
    
    return ;
}

//路線2
void solve2()
{
    ans2+=1;    //從ccca花費1費用走到cccb
    
    //從xxxa花費未知費用走到ccca、從cccb花費未知費用走到xxxb
    int c1=6-a[n]-b[n],c2=6-a[n]-b[n];
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]!=c1)
        {
            ans2+=1;
            ans2+=(i128(1)<<(i-1))-1;
            c1=6-a[i]-c1;
        }
        if(b[i]!=c2)
        {
            ans2+=1;
            ans2+=(i128(1)<<(i-1))-1;
            c2=6-b[i]-c2;
        }
    }
    
    return ;
}

scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
while(n>=1 && a[n]==b[n]) n--;  //如果初始就在目標(biāo)柱的話就不用移動了
if(n==0)
{
    puts("0");
    return 0;
}
solve1();
solve2();
write(min(ans1,ans2));

15.打表

Copied from IceAge

適用于打表的情況：

• 輸入數(shù)據(jù)情況很少（全打表）

• 代碼能處理大部分?jǐn)?shù)據(jù)，但有些情況處理不了，對于處理不了的部分打表（部分打表）

• 配合打表：某些預(yù)處理難寫、容易TLE，但是容易手算，而且是固定的，我們會考慮把這些打表進去，然后再配合自己的正解。

  e.g.列數(shù)很少的插頭dp問題，可以手動枚舉一行的插頭有哪些狀態(tài)、哪些狀態(tài)可以轉(zhuǎn)移到哪些狀態(tài)并存入鄰接矩陣，然后直接利用鄰接矩陣進行狀態(tài)轉(zhuǎn)移。（注意考慮清楚初始狀態(tài)和結(jié)束狀態(tài)）

打表的注意問題：

• 趁早做打表題，做的越早，你能暴搜到的答案可能就更多。

• 注意壓縮代碼長度，代碼過長交不上去的。

  \(e.g.\)《基礎(chǔ)算法15.1.分塊打表》

15.1.分塊打表

當(dāng)題目是一個序列問題時，可以把分塊的思想和打表結(jié)合起來，打表求出一整塊內(nèi)的答案，對于零散部分再單獨暴力求，這樣就可以減少代碼的長度（代碼的長度從\(O(N)\)變成\(O(\sqrt N)\)）了。

16.交互題

除特殊說明外，不用快讀。

16.1.傳統(tǒng)題在交互題上的應(yīng)用

16.1.1.抽屜原理

16.1.2.博弈論

適用條件：給定初始局面，自選先后手，與系統(tǒng)交互，構(gòu)造交互方案使得自己勝利。

先把該題看作傳統(tǒng)博弈論題：判斷先后手勝利條件，并證明。

根據(jù)初始局面與先后手勝利條件來選擇先后手，根據(jù)先后手勝利條件的證明來構(gòu)造交互方案。

16.1.3.動態(tài)規(guī)劃

原本只是一道dp題，交互方案是該dp轉(zhuǎn)移中的決策最優(yōu)點就變成了一道交互題。

參見《基礎(chǔ)算法·16.2.最優(yōu)化操作次數(shù)》。

16.2.最優(yōu)化操作次數(shù)

適用條件：1.任務(wù)是猜集合中的一個元素，通過詢問縮小答案候選集合；2.交互庫是自適應(yīng)的；3.最優(yōu)化操作次數(shù)。

構(gòu)造的重心在于構(gòu)造詢問方案。

維護集合的所有子集，對于每一個子集，求出它的最小詢問次數(shù)及詢問方案。求解的方法是dp。

1. \(f[state]\)：當(dāng)前狀態(tài)state的最壞情況下的最少詢問次數(shù)。

   有時最小詢問次數(shù)只與集合大小有關(guān)，此時dp只需記錄集合大小。

   根據(jù)對當(dāng)前狀態(tài)state所有可能最優(yōu)的詢問設(shè)計dp的轉(zhuǎn)移。

   先dp求出所有的f[state]，同時還要記錄轉(zhuǎn)移到f[state]的最優(yōu)決策（對于每一種詢問得到的答案的得到的新集合的詢問次數(shù)最大值最小）。

2. 開始交互。設(shè)當(dāng)前狀態(tài)為state。轉(zhuǎn)移到f[state]的最優(yōu)決策即為當(dāng)前最優(yōu)詢問的內(nèi)容。根據(jù)詢問得到的答案轉(zhuǎn)移到新的狀態(tài)。每一輪答案候選集合都會縮小。直到答案候選集合大小為1直接輸出該集合的那一個元素。

   如果允許猜k次，則當(dāng)答案候選集合大小≤k時直接猜。

例題。

16.2.1.交互器說謊題

適用條件：在給定的集合中猜交互庫選擇了哪個元素，可以輸出一個子集詢問那個元素是否在該子集中，“只保證交互器對任意兩次連續(xù)詢問的回復(fù)中至少有一次回復(fù)是真的。”

如果把關(guān)注點放在分別根據(jù)回答yes還是no判斷它是否說謊，可以證明這樣做無解。

因此需要構(gòu)造一種方案，使得無論它回答yes/no都可以使用同一種策略縮小答案候選集合。

核心：排除法

一定可以排除元素x\(\Leftrightarrow\)連續(xù)2次回答元素x“不符”。“不符”：x在詢問的子集中，回答no；或x不在詢問的子集中，回答yes。

最優(yōu)化交互次數(shù)：設(shè)計dp

\(f_{i,j}\)：當(dāng)前有i個連續(xù)0次“不符”的元素（設(shè)為集合\(S_0\)），j個連續(xù)1次“不符”的元素（設(shè)為集合\(T_0\)），最壞情況下的最少詢問次數(shù)。

連續(xù)2次“不符”的元素已經(jīng)被排除了。因此答案的候選集合\(=S_0+T_0\)。

\(f_{i,j}=\min\limits_{k=0}^i\min\limits_{l=0}^j\max\{f_{k+l,i-k},f_{(i-k)+(j-l),k}\}+1\)。k：從\(S_0\)中挑k個（設(shè)該子集為集合\(S_1\)，設(shè)\(S_1\)的補集為\(S_2\)）放入即將詢問的子集中；l：從\(T_0\)中挑l個（設(shè)該子集為集合\(T_1\)，設(shè)\(T_1\)的補集為\(T_2\)）放入即將詢問的子集中；\(f_{k+l,i-k}\)：交互庫回答yes，\(S_2,T_2\)“不符”；\(f_{(i-k)+(j-l),k}\)：交互庫回答no，\(S_1,T_1\)“不符”。min：你在決定怎么問。max：交互器在決定怎么回答。

轉(zhuǎn)移：i+j為第一關(guān)鍵字從小到大（因為詢問一次后答案的候選集合將減小），j為第二關(guān)鍵字從大到小（轉(zhuǎn)移有后效性，但是當(dāng)i+j相等時，j越大狀態(tài)越優(yōu)。因為\(j=|T_0|\)越大，一次詢問后排除的\(|T_1|\)或\(|T_2|\)越多）。

邊界：當(dāng)i+j≤1時，\(f_{i,j}=0\)。答案的候選集合里只剩下1個元素了，直接猜。

答案：\(f_{n,0}\)。

性質(zhì)：i+j>20時打表發(fā)現(xiàn)決策k=i/2,l=j/2比最優(yōu)決策差不了多少。

根據(jù)dp轉(zhuǎn)移的最優(yōu)策略決定實際策略

初始把所有元素放入\(S_0\)，\(T_0\)為空（\(f_{n,0}\)）。

設(shè)當(dāng)前的狀態(tài)是\(f_{i,j}\)，轉(zhuǎn)移到其的最優(yōu)決策是k,l。則從\(S_0,T_0\)中隨意挑\(k,l\)個元素放入\(S_{1},T_{1}\)，剩下的元素放入\(S_2,T_2\)。詢問\(S_1+T_1\)。

若交互器回答yes，把\(S_1+T_1,S_2\)放入下一輪的集合\(S'_0,T'_0\)，轉(zhuǎn)移到\(f_{k+l,i-k}\)；否則，把\(S_2+T_2,S_1\)放入下一輪的集合\(S'_0,T'_0\)，轉(zhuǎn)移到\(f_{(i-k)+(j-l),k}\)。進入下一輪循環(huán)，直到i+j≤1時跳出循環(huán)。

例題。

16.3.二進制分組

適用條件：1.可詢問次數(shù)q較小；2.每次可詢問n個元素的一個子集，交互器將返回該子集內(nèi)所有元素的信息的綜合；3.任務(wù)是確定該n個元素，\(n≤C_{q}^{\lfloor\frac{q}{2}\rfloor}\)；4.信息滿足可重性和結(jié)合律（\(e.g.\)|、max/min、連通性……）。

1. 給n個元素分配不同的長度為詢問次數(shù)q且含有\(\lfloor\frac{q}{2}\rfloor\)個1的01串。

2. 元素x的01串第k位為0表示x不在第k次詢問的子集中，反之則在。開始進行q次詢問。

3. q次詢問結(jié)束后，在排除所有詢問子集包含元素x的詢問后，剩下的詢問得到的信息綜合起來，即為除元素x以外其他所有元素的信息的綜合。

   證明：由于第1步構(gòu)造的二進制分組，在排除所有詢問子集包含元素x的詢問后，其他任意一個元素y仍然一定會被至少一個詢問子集所包含。

q次詢問至多能確定\(C_{q}^{\lfloor\frac{q}{2}\rfloor}\)個元素。

例題。

16.4.隨機化

利用隨機化降低詢問次數(shù)的復(fù)雜度。

題型1：隨機詢問使數(shù)據(jù)隨機

適用條件：類似于猜測排列。

對于形如? u v的詢問，每次隨機選u,v，這就相當(dāng)于要猜測的排列是隨機的，詢問次數(shù)變?yōu)槠谕牧恕?/p>

題型2

適用條件：詢問次數(shù)q略小于n且1次詢問至少能確定1個元素。

思考如何1次詢問盡可能地直接確定2個元素。

題型3

適用條件：任務(wù)是通過詢問? i j交互器返回\(a_i\oplus a_j\)來猜出整個長度為n的序列，序列滿足\(\forall x\in[l,l+n-1],\exist a_i=x\)。詢問次數(shù)q=n+c。

1. 花費q-n次詢問+隨機化，找到一個關(guān)鍵數(shù)key，滿足通過一次詢問? key i就能直接求出\(a_i\)。

   找大質(zhì)數(shù)：多次隨機2個位置詢問他們的lcm，找到所有返回值中的最大質(zhì)因子。

   找重兒子：在子樹u內(nèi)隨機1個點v，若v在u的兒子son的子樹內(nèi)，則son很大概率為u的重兒子。即使不是，son的子樹大小也與重兒子的子樹相近，詢問次數(shù)復(fù)雜度仍然能保證。

2. 花費n-1次詢問? key i求出整個序列。

題型4

適用條件：有2種詢問，且2種詢問得到的信息量一致且近乎等價。交互庫不是自適應(yīng)的。詢問次數(shù)q略小于n。

每次隨機一種詢問。一定要充分利用好得到的信息。

題型5

有時需要結(jié)合其他算法。

\(e.g.\)通過詢問? u交互器返回子樹u內(nèi)的所有節(jié)點來猜出整棵樹的形態(tài)，此時需要結(jié)合樹上啟發(fā)式合并，只需詢問? u的輕兒子。

17.通信題

1. 充分利用信息量

   適用條件：所有可能的A的信息的總數(shù)<<A→B所需要的信息量。

   事先約定把所有可能的A的信息一一映射到唯一的編碼。在A、B兩個源程序里都預(yù)處理所有可能的A的信息唯一對應(yīng)的編碼。A→B直接傳輸編碼。

   \(O(信息量)\)，注意該做法無法繼續(xù)優(yōu)化。

2. 不要把A→B/B→A局限于直接需要傳遞的信息。腦洞大開，有時B→A可以根據(jù)B的情況告訴A下一步怎么行動。

   \(e.g.\)要使得兩個源程序的隨機種子一樣，可以A→B告訴B源程序A的隨機種子是什么。