二分
二分的顯著特征是區間單調性
前一部分滿足條件A，後一部分滿足條件A的補集，求這兩者的分界點。有二分性再考慮二分。
假定一個解判斷是否可行 Cable Master
我們假定繩子長度為x，這是我們要二分的變量。
每二分出來一個結果，用C(x)函數來判斷是否滿足。
C(x)=L/x的結果>=K
如果滿足C(x)，就在x的右邊取繩子的長度；如果不滿足，就在x的左邊取繩子的長度。
上題繩子的長度可以是小數，而在二分一個隻取整數的a時，該如何處理呢？
在ACwing上看到的二分有兩種模闆：
1 找xxxxxxaoooooooo中的a
分為(L,mid)(mid+1,R)
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
2 找ooooooaxxxxxxxx中的a
分為(L,mid-1)(mid,R)
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
最大化最小值 Aggressive Cows
最大化最小值或者最小化最大值都是用二分來解決問題。
C（a）=牛的間距都大于等于a
a是我們的二分變量，即兩頭最近的牛的間距
寫二分的時候其實最難的就是check函數，通常都是想出一個貪心政策得到，用于驗證這個二分出來的x是否滿足條件。
本題可以用貪心法求解
- 對牛舍的位置進行排序
- 第一頭牛放入牛舍x[0]，剩下的牛按滿足距離大于a的條件下往後塞進牛舍。
應該用模闆2（書上的寫法也是對的，但是根據邊界情況不同模闆while(ub-lb>1)的判斷條件也會相應變化，容易記混）
最大化平均值
C(x)=機關重量的價格大于等于x
求滿足C(x）最大的x
将這個條件變形（很多題目數學變形就能發現新大陸）
check的貪心政策就是：排序後從大到小選取k個，看是否滿足>=0，滿足的話就搜x的右邊，不滿足就搜左邊。
從書上例題出發讨論幾個模拟的小技巧
3.2節介紹了尺取法、反轉問題、折半枚舉、離散化四個小技巧（彈性碰撞屬于實體範疇在這不再贅述）。
尺取法
其實就是不斷向後移動的雙指針s和t。移動的方式和判斷的方式因題目而異。
Subsequence
方法一：介于a[i]>0那麼确定了起點的字首和一定是單調遞增的，可以枚舉每個起點，二分尋找終點，再對每個起點的結果取min。
複雜度是O(nlogn)
方法二：
要想将其優化到O(n)就要起點和終點同時動起來。
初始化s=t=sum=0
用兩個指針s和t表示起點和終點。如果sum<S，就繼續t++
如果sum>=S,就更新ans為min(ans,sum)。然後将s++，繼續判斷。
看P148頁的圖就知道為什麼叫尺取法了。
J‘s Reading Problem
這個與上一題不一樣的是
1.判定條件，專門做一個數組看知識點有沒有全覆寫就行了。
2.先讓s=0，做出一個解，再不斷讓s++，把s覆寫的知識點cnt-1。那麼當某個知識點覆寫次數為0時，又可以讓t繼續後移。
反轉
反轉問題有三個特點：
- 可以使用二進制壓縮
- 同一操作區間反轉第二次是多餘操作
- 操作和順序無關
線性結構的反轉問題
藍橋杯 翻硬币
規定連着翻兩個。
簡單的貪心：隻要從左到右順次去翻硬币，見到不符合的翻就行了。
Face the Right Way
假如i後面還有k個，我們的目的是找出i是否需要翻轉。
取決于：
1.a[i]一開始是正面還是反面
2.i-k+1到i這一段位置翻轉對i位置的影響，用sum計算i位置被額外翻轉的次數，如果是偶數就相當于沒翻轉，是奇數就相當于翻轉了一次。
如果周遊到i，而i是需要翻轉的，就使f[i]=1表示從i到i+k-1被翻轉了
統計在j到j+k-1的期間的每一次翻轉
方法：對j到j+k-1中周遊的每個i，sum=sum+f[i]-f[i-k+1]
這樣就不用在對i翻轉的時候同時将後面k頭牛轉來轉去，降低了時間複雜度
int solve(int k)
{
int f[10001];
int sum=0,ans=0;
for(int i=0;i+k<=n;i++)
{
if((a[i]+sum)%2!=0)
{
ans++;
f[i]=1;
}
sum+=f[i];
if(i-k+1>=0)
sum-=f[i-k+1];
}
for(int i=n-k+1;i<n;i++)
{
if((a[i]+sum)%2!=0)
{
return -1;
}
if(i-k+1>=0)
sum-=f[i-k+1];
}
return ans;
}
方格結構的反轉問題 Fliptile
枚舉第一行的反轉方式即可。
#include<bits/stdc++.h>
using namespace std;
int mapp[600][600];
int a[600][600];
int d[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
void press(int x,int y)
{
a[x][y]=!a[x][y];
for(int i=0;i<4;i++)
{
int xx=x+d[i][0];
int yy=y+d[i][1];
if(xx>=0&&xx<=4&&yy>=0&&yy<=4)
{
a[xx][yy]=!a[xx][yy];
}
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
for(int i=0;i<5;i++)
{
string str;
cin>>str;
for(int j=0;j<5;j++)
{
mapp[i][j]=str[j]-'0';
}
}
int minstep=0x3f;
for(int i=0;i<1<<5;i++)
{
for(int k=0;k<5;k++)
for(int j=0;j<5;j++)
{
a[k][j]=mapp[k][j];
}
int p=i;
int cnt=0;
int pos=0;
while(p)
{
if(p&1==1)
{
press(0,pos);
cnt++;
}
p=p>>1;
pos++;
}
for(int k=1;k<5;k++)
{
for(int j=0;j<5;j++)
{
if(a[k-1][j]==0)
{
press(k,j);
cnt++;
}
}
}
int flag=1;
for(int k=0;k<5;k++)
{
if(a[4][k]==0)
{
flag=0;
break;
}
}
//cout<<endl;
if(flag)
{
minstep=min(minstep,cnt);
}
}
if(minstep>6)
cout<<-1;
else
cout<<minstep;
cout<<endl;
}
return 0;
}
反轉延伸出來的二進制壓縮問題
位運算無論是在狀壓dp還是二進制枚舉中都有非常大的用處。
折半枚舉
把要枚舉的一半結果hash打表，另一半正常枚舉得出結果後去表裡面查，查到了就是一種方案。
有時候要枚舉的是要打表的是兩維變量，比如：
超大背包問題
離散化
這是個對一維數組的去重操作，也是離散化的核心：
區域的個數
在這道題裡，用dfs求聯通快就可以求出區域個數了。（書上用bfs是防止爆棧）
但是整個地圖很大，有些行和上一行一樣或者有些列和上一列一樣可以忽略掉。
書上題解采用隻存儲有黑線的行（列）和他們的前一行（列）、後一行（列）。
for(int i=0;i<N;i++)
{
for(int d=-1;d<=1;d++)
{
//将周圍的行加進去，列同理
int tx1=x1[i]+d;
int tx2=x2[i]+d;
if(1<=tx1&&tx1<=w)
xs.push_back(tx1);
if(1<=tx2&&tx2<=w)
xs.push_back(tx2);
}
}
即便如此仍然會有重複，用離散化去重，轉化為新的坐标對。
//去重操作
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
//更新成新坐标
for(int i=0;i<N;i++)
{
x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin();
x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin();
}
得到對我們有用的行和列，組成新的地圖。
![ACM_程式設計競賽：窮舉法：DFS(深度優先)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)