基礎算法總結
- 1、模擬
- 1.1 什么是模擬算法
- 1.2 算法題
- 1.2.1 多項式輸出
- 1.2.2 蛇形方陣
- 2 高精度算法
- 2.1 什么是高精度算法
- 2.2 算法題
- 2.2.1 高精度加法
- 2.2.2 高精度乘法
- 3 普通枚舉
- 3.1 算法題
- 3.1.1 鋪地毯
- 3.1.2 回文日期
- 4 前綴和算法
- 4.1 什么是前綴和
- 4.2 算法題
- 4.2.1 最大子段和
- 4.2.2 二維前綴和
- 5 差分
- 5.1 什么是差分
- 5.2 算法題
- 5.2.1 海底高鐵
- 5.2.2 地毯
- 6、雙指針
- 6.1 雙指針算法是什么
- 6.2 算法題
- 6.2.1 唯一的雪花
- 6.2.2 逛畫展
- 7 二分算法
- 7.1 什么是二分算法
- 7.2 算法題
- 7.2.1 牛可樂和魔法封印
- 7.2.2 A-B數對
- 8、貪心算法
- 8.1 什么是貪?算法?
- 8.2 貪?算法的特點
- 8.3. 如何學習貪??
- 8.4 相關算法題(2道)
- 1.4.1 貨倉選址
- 8.4.2 最大子段和
- 9、倍增算法
- 9.1 倍增,顧名思義就是翻倍。它能夠使線性的處理轉化為對數級的處理,極?地優化時間復雜度。
- 9.2.1 快速冪
- 9.2.2 64位整數乘法
- 10 離散化
- 10.1 算法:
- 10.2 離散模版
- 10.3 算法題
- 10.3.1 火燒赤壁
- 10.3.2
- 11、遞歸初階
- 11.1 算法概念
- 11.2 算法題
- 11.2.1 漢諾塔
- 11.2.2 占卜diy
- 12 、分治算法
- 12.1 算法概念
- 12.2 算法題
- 12.2.1 逆序對
- 12.2.2 求第k小的數
1、模擬
1.1 什么是模擬算法
模擬,顧名思義,就是題?讓你做什么你就做什么,考察的是將思路轉化成代碼的代碼能?。
這類題?般較為簡單,屬于競賽??的簽到題(但是,萬事?絕對,也有可能會出現讓??常難受的
模擬題),我們在學習語法階段接觸的題,?多數都屬于模擬題。
1.2 算法題
1.2.1 多項式輸出
https://www.luogu.com.cn/problem/P1067
#include<iostream>
#include<cmath>
using namespace std;int main()
{int n; cin >> n;for (int i = n; i >= 0; i--){int a; cin >> a;if (a == 0) continue;if (a < 0) cout << '-';if (a > 0){if (i != n) cout << '+';}//符號a = abs(a);if (a != 1 || (a == 1 && i == 0)) cout << a;//數字if (i > 1) cout << "x^" << i;if (i == 1) cout << "x";//指數}return 0;
}
1.2.2 蛇形方陣
https://www.luogu.com.cn/problem/P5731
#include<iostream>
using namespace std;const int N = 15;
//右,下,左,上
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
//向量數組
int arr[N][N];int main()
{int n; cin >> n;int x = 1, y = 1;int pos = 0;int cnt = 1;while (cnt <= n * n){arr[x][y] = cnt;cnt++;int a = x + dx[pos], b = y + dy[pos];if (a<1 || b>n || a > n || b < 1 || arr[a][b]){pos = (pos + 1) % 4;a = x + dx[pos], b = y + dy[pos];}x = a, y = b;}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){printf("%3d", arr[i][j]);}cout << endl;}return 0;
}
2 高精度算法
2.1 什么是高精度算法
當數據的值特別?,各種類型都存不下的時候,此時就要??精度算法來計算加減乘除:
? 先?字符串讀?這個數,然后?數組逆序存儲該數的每?位;
? 利?數組,模擬加減乘除運算的過程。
?精度算法本質上還是模擬算法,?代碼模擬?學列豎式計算加減乘除的過程。
2.2 算法題
2.2.1 高精度加法
https://www.luogu.com.cn/problem/P1601
#include<iostream>
using namespace std;const int N = 1e5;
int a[N], b[N], c[N];
int la, lb, lc;void add(int c[], int a[], int b[])
{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++;
}int main()
{string x, y; cin >> x >> y;la = x.size(), lb = y.size(); lc = max(la, lb);for (int i = 0; i < la; i++) a[i] = x[x.size() - i - 1] - '0';for (int i = 0; i < lb; i++) b[i] = y[y.size() - i - 1] - '0';add(c, a, b);for (int i = lc - 1; i >= 0; i--)cout << c[i];return 0;
}
2.2.2 高精度乘法
https://www.luogu.com.cn/problem/P1303
#include<iostream>
using namespace std;const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;void mul(int c[], int a[], int b[])
{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;}while (lc > 1 && c[lc - 1] == 0) lc--;
}int main()
{string x, y; cin >> x >> y;la = x.size(), lb = y.size(), lc = la + lb;for (int i = 0; i < la; i++) a[i] = x[x.size() - i - 1] - '0';for (int i = 0; i < lb; i++) b[i] = y[y.size() - i - 1] - '0';mul(c, a, b);for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}
3 普通枚舉
3.1 算法題
3.1.1 鋪地毯
https://www.luogu.com.cn/problem/P1003
#include <iostream>
using namespace std;const int N=1e5;
int a[N],b[N],g[N],k[N];
int n,x,y;int judge()
{for(int i=n;i>=1;i--){if(x>=a[i]&&y>=b[i]&&x<=a[i]+g[i]&&y<=b[i]+k[i])return i;}return -1;
}int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>g[i]>>k[i];cin>>x>>y;cout<<judge();return 0;
}
3.1.2 回文日期
https://www.luogu.com.cn/problem/P2010
#include<iostream>
using namespace std;int x,y;int day[]={0,31,29,31,30,31,30,31,31,30,31,30,31};int main()
{cin>>x>>y;int cnt=0;for(int i=1;i<=12;i++){for(int j=1;j<=day[i];j++)//11 22{int k=j%10*1000+j/10*100+i%10*10+i/10;int num=k*10000+i*100+j;if(x<=num&&num<=y) cnt++;}}cout<<cnt;return 0;}
4 前綴和算法
4.1 什么是前綴和
前綴和與差分的核?思想是預處理,可以在暴?枚舉的過程中,快速給出查詢的結果,從?優化時間
復雜度。是經典的?空間替換時間的做法。
4.2 算法題
4.2.1 最大子段和
https://www.luogu.com.cn/problem/P1115
/*#include<iostream>
using namespace std; const int N=2e5+10;
long long dp[N];
int n; int main()
{cin>>n;for(int i=1;i<=n;i++) {int x; cin>>x;dp[i]=dp[i-1]+x;}long long ret=-1e6;long long prevmin=0;for(int i=1;i<=n;i++){ret=max(ret,dp[i]-prevmin);prevmin=min(prevmin,dp[i]);}cout<<ret;return 0;
}*/
4.2.2 二維前綴和
https://ac.nowcoder.com/acm/problem/226333
#include<iostream>
using namespace std;const int N=1e3+10;
long long dp[N][N];
int n,m,q;int main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x; cin>>x;dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+x;}} while(q--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;cout<<dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]<<endl;}return 0;}
5 差分
5.1 什么是差分
前綴和與差分的核?思想是預處理,可以在暴?枚舉的過程中,快速給出查詢的結果,從?優化時間
復雜度。是經典的?空間替換時間的做法。
學完差分之后,?家會發現,前綴和與差分是?對互逆的運算。
5.2 算法題
5.2.1 海底高鐵
https://www.luogu.com.cn/problem/P3406
#include <iostream>
using namespace std;int n,m;
const int N=1e5+10;
long long f[N];int main()
{cin>>n>>m;int x; cin>>x;for(int i=2;i<=m;i++){int y; cin>>y;if(x>y) f[y]++,f[x]--;else f[x]++,f[y]--;x=y;}for(int i=1;i<=n;i++)f[i]=f[i]+f[i-1];long long ret=0;for(int i=1;i<n;i++){long long a,b,c; cin>>a>>b>>c;ret+=min(a*f[i],c+b*f[i]);}cout<<ret<<endl;return 0;}
5.2.2 地毯
https://www.luogu.com.cn/problem/P3397
#include<iostream>
using namespace std;const int N=1010;
int n,m;
int f[N][N];void add(int x1,int y1,int x2,int y2,int k)
{f[x1][y1]+=k;f[x1][y2+1]-=k;f[x2+1][y1]-=k;f[x2+1][y2+1]+=k;
}int main()
{cin>>n>>m;while(m--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;add(x1,y1,x2,y2,1);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=f[i][j-1]+f[i-1][j]+f[i][j]-f[i-1][j-1];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<f[i][j]<<' ';}cout<<endl;} return 0;}
6、雙指針
6.1 雙指針算法是什么
雙指針算法有時候也叫尺取法或者滑動窗?,是?種優化暴?枚舉策略的?段:
? 當我們發現在兩層 for 循環的暴?枚舉過程中,兩個指針是可以不回退的,此時我們就可以利?
兩個指針不回退的性質來優化時間復雜度。
? 因為雙指針算法中,兩個指針是朝著同?個?向移動的,因此也叫做同向雙指針。
注意:希望?家在學習該算法的時候,不要只是去記憶模板,?定要學會如何從暴?解法優化成雙指
針算法。不然往后遇到類似題?,你可能壓根都想不到?雙指針去解決。
6.2 算法題
6.2.1 唯一的雪花
https://www.luogu.com.cn/problem/UVA11572
#include <iostream>
#include<unordered_map>
using namespace std;const int N = 1e6 + 10;
int t, arr[N];int main()
{cin >> t;while (t--){int n; cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i];int left = 1, right = 1;unordered_map<int, int> mp;int ret = 0;while (right <= n){mp[arr[right]]++;while (mp[arr[right]] > 1){mp[arr[left++]]--;}ret = max(ret, right - left + 1);right++;}cout << ret << endl;}return 0;
}
6.2.2 逛畫展
https://www.luogu.com.cn/problem/P1638
#include<iostream>
using namespace std;int n,m,kinds;
const int N=1e6+10;
int a[N];
int mp[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int left=1,right=1;int ret=n,begin=1;while(right<=n){if(mp[a[right]]++==0) kinds++;while(kinds==m){int len=right-left+1;if(len<ret){begin=left;ret=len;}if(mp[a[left]]--==1) kinds--;left++;}right++;}cout<<begin<<' '<<begin+ret-1<<endl;return 0;
}
7 二分算法
7.1 什么是二分算法
?分算法是我覺得在基礎算法篇章中最難的算法。?分算法的原理以及模板其實是很簡單的,主要的
難點在于問題中的各種各樣的細節問題。因此,?多數情況下,只是背會?分模板并不能解決題?,
還要去處理各種亂七?糟的邊界問題。
7.2 算法題
7.2.1 牛可樂和魔法封印
https://ac.nowcoder.com/acm/problem/235558
#include <iostream>
using namespace std; const int N=1e5+10;
long long a[N],n;int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int q; cin>>q;while(q--){int l,r; cin>>l>>r;int left=1,right=n;while(left<right){int mid=(left+right)/2;if(a[mid]>=l) right=mid;else left=mid+1;}int lefti=left;if(a[lefti]<l){cout<<0<<endl;continue;}left=1,right=n;while(left<right){int mid=(left+right+1)/2;if(a[mid]<=r) left=mid;else right=mid-1;}int righti=right;if(a[righti]>r){cout<<0<<endl;continue;}cout<<righti-lefti+1<<endl;}return 0;
}
7.2.2 A-B數對
https://www.luogu.com.cn/problem/P1102
#include<iostream>
#include<algorithm>
using namespace std;const int N = 2e5 + 10;
long long a[N], c;
int n;int main()
{cin >> n >> c;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1,a+n+1);long long ret = 0;for (int i = n; i > 1; i--){long long b = a[i] - c;ret += upper_bound(a + 1, a + i, b) - lower_bound(a + 1, a + i, b);}cout << ret;return 0;
}
8、貪心算法
8.1 什么是貪?算法?
貪?算法,或者說是貪?策略:企圖?局部最優找出全局最優。
- 把解決問題的過程分成若?步;
- 解決每?步時,都選擇"當前看起來最優的"解法;
- "希望"得到全局的最優解。
8.2 貪?算法的特點
- 對于?多數題?,貪?策略的提出并不是很難,難的是證明它是正確的。因為貪?算法相較于暴?枚舉,每?步并不是把所有情況都考慮進去,?是只考慮當前看起來最優的情況。但是,局部最優并不等于全局最優,所以我們必須要能嚴謹的證明我們的貪?策略是正確的。?般證明策略有:反證法,數學歸納法,交換論證法等等。
- 當問題的場景不同時,貪?的策略也會不同。因此,貪?策略的提出是沒有固定的套路和模板
的。我們后?講的題?雖然分類,但是?家會發現具體的策略還是相差很?。
因此,不要妄想做?道貪?題?就能遇到?個會?個。有可能做完50道貪?題?之后,第51
道還是沒有任何思路。
8.3. 如何學習貪??
先有?個認知:做了??道貪?的題?,遇到?個新的?沒有思路,這時很正常的現象,把?態放
平。
- 前期學習的時候,重點放在各種各樣的策略上,把各種策略當成經驗來吸收;
- 在平常學習的時候,我們盡可能的證明?下這個貪?策略是否正確,這樣有利于培養我們嚴謹的思維。但是在?賽中,能想出來?個策略就已經不錯了,如果再花費?量的時間去證明,有點得不償失。這個時候,如果根據貪?策略想出來的若?個邊界情況都能過的話,就可以嘗試去寫代碼了。
8.4 相關算法題(2道)
1.4.1 貨倉選址
https://www.luogu.com.cn/problem/P10452
#include <iostream>
#include<algorithm>
using namespace std;const int N=1e5+10;
int n;
int a[N];int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);long long ret=0;for(int i=1;i<=n;i++){ret+=abs(a[i]-a[(1+n)/2]);}cout<<ret;return 0;
}
選中間位置即可
8.4.2 最大子段和
https://www.luogu.com.cn/problem/P1115
#include<iostream>
using namespace std;const int N=2e5+10;
int a[N],n;int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];long long ret=-1e10;long long sum=0;for(int i=1;i<=n;i++){sum+=a[i];ret=max(sum,ret);if(sum<0) sum=0; }cout<<ret<<endl;return 0;}
9、倍增算法
9.1 倍增,顧名思義就是翻倍。它能夠使線性的處理轉化為對數級的處理,極?地優化時間復雜度。
9.2.1 快速冪
https://www.luogu.com.cn/problem/P1226
#include<iostream>
using namespace std;long long a,b,p;long long qpow(long long a,long long b,long long p)
{long long ret=1;while(b){if(b&1) ret=ret*a%p;a=a*a%p;b>>=1; }return ret;
}int main()
{cin>>a>>b>>p;printf("%lld^%lld mod %lld=%lld",a,b,p,qpow(a,b,p));return 0;}
9.2.2 64位整數乘法
https://www.luogu.com.cn/problem/P10446
#include<iostream>
using namespace std;typedef long long=LL;
LL 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;
}int main()
{cin>>a>>b>>p;cout<<qmul(a,b,p)<<endl;return 0;}
10 離散化
10.1 算法:
當題?中數據的范圍很?,但是數據的總量不是很?。此時如果需要?數據的值來映射數組的下標
時,就可以?離散化的思想先預處理?下所有的數據,使得每?個數據都映射成?個較?的值。之后再?離散化之后的數去處理問題。
?如:[99, 9, 9999, 999999] 離散之后就變成[2, 1, 3, 4] 。
10.2 離散模版
離散化模板 排序+去重+?分離散化之后的值
模版一:
10.3 算法題
10.3.1 火燒赤壁
https://www.luogu.com.cn/problem/P1496
10.3.2
11、遞歸初階
11.1 算法概念
11.2 算法題
11.2.1 漢諾塔
http://ybt.ssoier.cn:8088/problem_show.php?pid=1205
#include<iostream>
using namespace std;int n;
char a,b,c;void dfs(int n,char x,char y,char z)//把x上的盤子借助y的幫助全部放到z上
{if(n==0) return;dfs(n-1,x,z,y);printf("%c->%d->%c\n",x,n,z);dfs(n-1,y,x,z);
}int main()
{cin>>n>>a>>b>>c;dfs(n,a,c,b);return 0;
}
11.2.2 占卜diy
https://www.luogu.com.cn/problem/P10457
#include<iostream>
using namespace std;int n=13,m=4;
int a[14][5];
int cnt[14];void dfs(int x)
{if(x==13) return;int t=a[x][cnt[x]];cnt[x]--;dfs(t);
}int main()
{for(int i=1;i<=n;i++){cnt[i]=4;for(int j=1;j<=m;j++){char x; cin>>x;if(x>='2'&&x<='9') a[i][j]=x-'0';else if(x=='A') a[i][j]=1;else if(x=='J') a[i][j]=11;else if(x=='Q') a[i][j]=12;else if(x=='K') a[i][j]=13;else a[i][j]=10;}}for(int i=1;i<=m;i++){dfs(a[n][i]);}int ret=0;for(int i=1;i<=n;i++)if(cnt[i]==0) ret++;cout<<ret;return 0;
}
12 、分治算法
12.1 算法概念
12.2 算法題
12.2.1 逆序對
https://www.luogu.com.cn/problem/P1908
#include <iostream>
using namespace std;const int N=5e5+10;
int n;
int a[N],b[N];long long merge(int left,int right)
{if(left>=right) return 0;long long ret=0;int mid=(left+right)/2;ret+=merge(left,mid);ret+=merge(mid+1,right);int cur1=left,cur2=mid+1,i=left;while(cur1<=mid&&cur2<=right){if(a[cur1]<=a[cur2]) b[i++]=a[cur1++];else{ret+=mid-cur1+1;b[i++]=a[cur2++];}}while(cur1<=mid) b[i++]=a[cur1++];while(cur2<=right) b[i++]=a[cur2++];for(int j=left;j<=right;j++) a[j]=b[j];return ret;
}int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cout<<merge(1,n);return 0;
}
12.2.2 求第k小的數
https://www.luogu.com.cn/problem/P1923
#include<iostream>
#include<ctime>
using namespace std;const int N = 5e6 + 10;
int n, k;
int a[N];int getrand(int left, int right)
{return a[rand() % (right - left + 1) + left];
}int quick_select(int left, int right, int k)
{if (left >= right) return a[left];// 1. 選擇基準元素int p = getrand(left, right);// 2. 數組分三塊int l = left - 1, i = left, r = right + 1;while (i < r){if (a[i] < p) swap(a[++l], a[i++]);else if (a[i] == p) i++;else swap(a[--r], a[i]);}// 3. 選擇存在最終結果的區間// [left, l] [l + 1, r - 1] [r, right]int a = l - left + 1, b = r - 1 - l, c = right - r + 1;if (k <= a) return quick_select(left, l, k);else if (k <= a + b) return p;else return quick_select(r, right, k - a - b);
}int main()
{scanf("%d%d", &n, &k);k++;srand(time(0));for (int i = 1; i <= n; i++) scanf("%d", &a[i]);printf("%d\n", quick_select(1, n, k));return 0;
}