算法基礎篇
前言
算法內容還有搜索，數據結構（進階），動態規劃和圖論
數學那個的話大家也知道比較難，放在最后講
這期包含的內容可以看目錄
模擬那個算法的話就是題說什么寫什么，就不再分入目錄中了
注意事項：
1.多組測試時，一定要考慮需不需要清空數據
一般是能覆蓋的話(沒覆蓋的部分不用就行了)不清空或者還能用就不清空
(權衡時間復雜度，清空是用時間換空間)
2.int類型的無窮大可以搞為 int inf = 0x3f3f3f3f
1.高精度
當數據的值特別大，各種類型都存不下的時候，要用高精度算法來加減乘除
步驟:
1.先用字符串讀入這個數，然后用數組逆序存儲該數的每一位
2.利用數組，模擬加減乘除運算的過程
高精度加法：(c= a+b，其字符串存在c[],a[],b[]中)例題：洛谷的 [P1601 A+B Problem（?精）]
la,lb是a,b的字符串長度
lc = max(la,lb)
for(int i = 0;i<lc；i++)
{c[i]=a[i]+b[i];//對應位相加c[i+1]=c[i]/10;//處理進位c[i]%=10;//處理余數
}
if(c[lc])lc++;//易忘，來讓lc為c字符串的長度
這里字符串的長度不用數組求
讀的時候先讀成string，再用size()求字符串長度，最后for循環讀到數組里（逆序存儲）
高精度減法:(z = x - y)存儲在z[],x[],y[]（逆序存儲）
例題: 洛谷P2142 ?精度減法
要讓大的數減小的數才行(判斷方法如下：)
1.位數不等，按照字符串的長度比較
2.位數相等，用字典序比較
bool cmp(string&x,string&y)
{
if(x.size()!=y.size()) return x.size()<y.size();//比長度return x<y//比字典序}if(cmp(x,y))
{swap(x,y);cout<<'-'; }高精度減法過程:(x大于y才行)
lz=max(lx,ly);for(int i = 0;i<lz；i++)z[i]+=x[i]-y[i];if(z[i]<0)
{z[i+1]-=1;//借位z[i]+=10;}
while(lz>1&&z[lz-1]==0)lz--;//處理前導0
高精度乘法:(c = a*b)(也要逆序存儲)
例題:洛谷 P1303 A*B Problem
lc = la+lb
//無進位相乘
for(int i =0;i<la,i++)
｛for(int j = 0,j<lb,j++){c[i+j] = a[i]*b[j];} ｝
//處理進位
for(int i = 0;i<lc,i++)
{c[i+1]+=c[i]/10;c[i]%=10;}
//處理前導0
while(lc>1&&c[lc-1]==0)lc--;
（高精度除低精度）
（數組也是逆著存的，即個位在a[0]）
高精度除法(這個模板是正數的，并且數組不用逆序存儲)(c=a/b)(0<b<10的9次方)
（如果要解決負數的，就先判斷是不是就一個負數，是就打印個-,之后轉換為此做）long long t = 0;//標記每次除完之后的余數
for(int i = la-1;i>=0;i--)
{
//計算當前的被除數t = t*10+a[i];c[i]=t/b;t%=b; }
//處理前導0
while(lc>1&&c[lc-1]==0)lc--;
2.枚舉和二進制枚舉
枚舉其實就是暴力求解
使用時一般都會超時，此時要先根據題目的數據范圍來判斷暴力枚舉能不能通過
不能的話就要使用后面的各種算法去優化(比如二分這些)，還有就是尋找題目的各種性質去簡化題目(eg:洛谷 P10449 費解的開關)
二進制枚舉:
用一個數的二進制表示中的0/1表示兩種狀態，從而達到枚舉各種情況
例題:力扣 子集
而且，把一個數的二進制存在數組中時，一般用反著存儲會讓過程變得簡單常用于的題型:
抽象圖都是矩陣，改變矩陣的值，產生效果達到要求，問有幾種途徑
eg: 洛谷 Even Parity
3.前綴和（一維和二維）
在使用前綴和數組時，下標最好從1開始
核心思想就是預處理(用空間代替時間)，避免多次重復運算
一維前綴和:
例題:牛客網 【模板】前綴和
其實就是把前面的和加在一起二維前綴和：
例題:牛客網 【模板】?維前綴和
用二維數組解決
前綴和矩陣一般為
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
4.差分(一維和二維)
核心思想也是預處理，也是用空間替換時間
其實，前綴和與差分是一對互逆的運算
一維差分:
例題:牛客網 【模板】差分洛谷 P1496 ?燒?壁步驟:
1.預處理出來差分數組
f[i]表示當前元素和前一個元素的差值f[i]+=a[i];f[i+1]-=a[i];2.利用差分數組解決m次修改操作
修改操作是：原數組[L,R]區間全部加k這個操作
相當于在差分數組中，f[L]+=k;f[R+1]-=k;3.還原原始的數組
直接對差分數組做前綴和運算即可
f[i]=f[i-1]+f[i];注意事項：
差分數組使用的時候，所有的操作必須全部進行完畢后，才能還原出操作之后的數組如果操作和查詢穿插在一起的話，不用差分數組，不然時間復雜度很高
eg:每操作若干次，就查詢一個操作之后的結果，然回還會繼續操作，繼續查詢
這種問題要用線段樹
二維差分：
例題:牛客網 【模板】?維差分利用差分矩陣解決問題
作用：快速處理"將二維數組中，某一個子矩陣加上一個元素的"的操作
這個子矩陣的左上是[x1][y1]，右上是[x2][y2]
與一維差分很不同的地方：
在于利用差分數組來解決m次修改
f[x1][y1]+=k;
f[x1][y2+1]-=k;
f[x2+1][y1]-=k;
f[x2+1][y2+1]+=k;
這里的前綴和的用法也是要注意的！(用的前面的二維前綴和)
5.雙指針(也叫尺取法或滑動窗口)
兩個指針不回退（回退沒啥用）時，才能用滑動窗口法
滑動窗口的時間復雜度是O(n平方)
是先分析暴力解法(發現第一行那個)，然后可以用滑動窗口法
滑動窗口步驟:
例題:洛谷 唯?的雪花 Unique Snowflakes
1.初始化:left right 哈希表(不一定每題都用的哈希表)
2.進窗口:right位置元素記錄到統計次數的哈希表中
3.判斷:當哈希表中right位置的值超過1次之后，窗口內子串不合法
4.出窗口:讓left所指位置的元素在哈希表中的次數減1
5.更新結果:判斷結束之后，窗口合法，此時更新窗口的大小
(在其他題時，這個更新結果不一定為這5步中的最后一步)
6.二分算法
如果逐個遍歷會超時時，常用此
使用條件:要研究的問題具有二段性才行
二段性:按某種要求可以分為兩部分(比如大于18歲和不大于18歲)
二分算法的時間復雜度是O(logN)
這里的模板就只用記兩點:
1.while(l<r)
2.if/else成立所要執行的語句中出現-1的話(這個好判斷)，前面的mid就要用有+1那個
3.如果想要最后的＞a，則if里面就填(f[mid]>a)
如果是有序數組中查找的話，直接用STL的lower_bound和upper_bound
這個的時間復雜度O(logN)
反之則要自己模擬實現模擬實現的細節問題：
a.while循環里面的判斷如何寫
b.求中點的方式選哪一種
c.二分結束之后，相遇點的情況
需要判斷一下，循環結束之后，是否是我們想要的結果
二分答案：
其實跟二分查找很類似，只不過把對象改成了答案
應用場景:求最大值最小和最小值最大問題
例題:洛谷 P1873 [COCI 2011/2012 #5] EKO / 砍樹
7.貪心
鼠目寸光，也就是想用局部最優找出全局最優
步驟:
1.把解決問題的過程分成若干步
2.解決每一步時，都選擇"當前看起來最優的"解法
3."希望"得到全局的最優解
在競賽時，如果根據貪心策略想出來的若干個邊界情況都能過的話，就大概率沒問題，不去證明了
8.倍增思想
它能夠使線性的處理轉化為對數級的處理，優化時間復雜度
例題:（一般只用于這倆個）
1.洛谷 P1226 【模板】快速冪LL qpow(LL a,LL b,LL p)//a的b次方對p取模{LL ret = 1;while(b)
{if(b&1)ret = ret*a%p;a = a*a%p;b>>=1;
}return ret;//這個;易忘}
2.洛谷 P10446 64位整數乘法
//a乘b對p取模
LL qmul(LL a,LL b,LL p)
{LL sum = 0;
while(b){if(b&1) sum=(sum+a)%p;a = (a+a)%p;//倍增b>>=1;}return sum;}
9.離散化
應用場景:當題目中數據的范圍很大，但是數據的總量不是很大，就可以用離散化的思想先預處理一下所有的數據
離散化模板:
排序+使用哈希表去重并且記錄離散化之后的值
(有時還需要再加一個統計每個位置出現幾次的數組去記錄每個位置出現了幾次)
離散化常要對模板進行修改
例題：洛谷 P1496 ?燒?壁
用到離散化時容易出現問題的地方(區分同種和異種)
同種被覆蓋的范圍的例題:洛谷 P1496 ?燒?壁異種被覆蓋的范圍的例題:洛谷 P3740 [HAOI2014] 貼海報
要在離散化區間[x,y]時，不僅考慮x,y這倆個值，還要把[x+1,y+1]也考慮進去。
可以讓單個區間內部和區間與區間之間都出現空隙
10.遞歸
應用場景：搞類似二叉樹和東西和有重復子問題并要dfs時常用
如果會多次重復已知計算的話，建議用遞推，而不是遞歸
注意事項:
1.遞歸的出口一般寫在開頭的
2.尾和頭處理的對就一般沒問題
3.用的全局變量和局部變量的值是多久的要注意(這倆個不同)
4.遞歸里面的輸出是從底到頭搞的
5.一定要設法轉化為重復子問題(利用傳參的增多來實現通用化)
11.分治
就是把一個問題分為多個子問題解決
一般分為左－右－中間
應用場景:
1.解決逆序對
例題：洛谷 P1908 逆序對
?12.其他
按照方向走的時候:
可以int d[x]={1,0,-1,0}int d[y]={0,1,0,-1}這樣來表示二維上的東西可以上下左右走一格這樣走
eg:洛谷的蛇形方陣
如果想要數從0開始變成從1開始的話:
可以在cin>>x之后就立馬x++
eg:如果a和b的和固定，那就只用記錄a的值 b的值到時候推就行了
這樣可以節省存儲空間
求中點用
mid = left+(right - left)/2
和 mid = left+(right - left+1)/2，避免溢出
做題時，常需要觀察的性質有：
1.是不是改變順序不影響結果
例題:洛谷 A-B 數對
取模運算技巧：
1.當計算過程中，只有"加法"和"乘法"時，想對結果取模的話，取模可以放在任意的位置
但是最后一定要有個取模
eg:(a*b*c*d)%p
和 (a%p*b*c%p*d)%p的結果一樣
這個在防止超出范圍時很好用
2.當計算過程中，存在"減法"時，取模結果可能是負數的，此時如果需要補正，就需要"模加模"
的技巧來補正--負的模給搞成正的那一個模
eg:寫為((a-b)%p+p)%p
3.如果當計算過程中，存在"除法"時，取模是會造成結果錯誤的
需要用求逆元的方法
解決頂出元素且"不插入"新元素的問題:
int cnt[N];
//用于標記第i行還有多少個老元素沒被頂出
讓a[i][cnt[i]]每次都是第i行的最后一個元素
//頂出元素之后要i--,下標為0的不存東西
13.例題鏈接傳送
洛谷的 [P1601 A+B Problem（?精）]
洛谷P2142 ?精度減法
洛谷 P1303 A*B Problem
洛谷 P1480 A/B Problem
力扣 子集
[牛客網 【模板】前綴和]
牛客網 【模板】?維前綴和
牛客網 【模板】差分
[洛谷 P1496 ?燒?壁]
牛客網 【模板】?維差分
洛谷 唯?的雪花 Unique Snowflakes
洛谷 P1873 [COCI 2011/2012 #5] EKO / 砍樹
洛谷 P1226 【模板】快速冪
洛谷 P10446 64位整數乘法
洛谷 P3740 [HAOI2014] 貼海報
洛谷 P1908 逆序對
)
