柚子快報(bào)邀請(qǐng)碼778899分享：算法基礎(chǔ)課一刷
柚子快報(bào)邀請(qǐng)碼778899分享：算法基礎(chǔ)課一刷
第一遍代碼
基礎(chǔ)算法好用的技巧c++11萬(wàn)能頭文件基礎(chǔ)模板關(guān)閉同步流輸入輸出好用的函數(shù)常用變量
二分?jǐn)?shù)的范圍數(shù)的三次方根
排序快速排序第k個(gè)數(shù)歸并排序逆序?qū)?shù)量
高精度高精度加法高精度減法高精度乘法高精度除法
雙指針最長(zhǎng)連續(xù)不重復(fù)子序列
離散化（區(qū)間和）區(qū)間合并
數(shù)據(jù)結(jié)構(gòu)常見結(jié)構(gòu)單鏈表雙鏈表單調(diào)棧單調(diào)隊(duì)列（滑動(dòng)窗口）
kmp字符串字典樹（樹狀數(shù)組）字符串統(tǒng)計(jì)最大異或?qū)?/p>
并查集合并集合連通塊中點(diǎn)的數(shù)量食物鏈
堆堆排序模擬堆
哈希表模擬散列表字符串哈希
搜索和圖論dfs排序數(shù)字n皇后問題
bfs走迷宮八數(shù)碼
樹圖的搜索dfs樹的重心圖中點(diǎn)的層次拓?fù)渑判?/p>
最短路算法單源最短路樸素版dijkstra堆優(yōu)化版dijsktrabellman-ford算法（可存在負(fù)權(quán)邊）spfa算法（可存在負(fù)權(quán)邊）
多源最短路Floyd算法
最小生成樹primkruskal
二分圖染色法判斷二分圖二分圖的最大匹配
數(shù)學(xué)知識(shí)質(zhì)數(shù)試除法判斷質(zhì)數(shù)分解質(zhì)因數(shù)質(zhì)數(shù)篩
約數(shù)試除法求約數(shù)約數(shù)個(gè)數(shù)約數(shù)之和最大共約數(shù)
歐拉函數(shù)求歐拉函數(shù)質(zhì)數(shù)篩求多個(gè)數(shù)的歐拉函數(shù)之和
快速冪快速冪模板快速冪求逆元（p為質(zhì)數(shù)時(shí)）
擴(kuò)展歐幾里得算法模板線性同余方程
中國(guó)剩余定理（表達(dá)整數(shù)的奇怪方式）表達(dá)整數(shù)的奇怪方式
高斯消元解線性方程組
求組合數(shù)一般四種情況組合數(shù)的應(yīng)用（卡特蘭數(shù)）
容斥原理博弈論Nim游戲（尼姆博弈）臺(tái)階-Nim游戲（尼姆的應(yīng)用）集合-Nim游戲（seg函數(shù)將問題轉(zhuǎn)換為尼姆博弈）拆分-Nim游戲
日期問題回文日期
動(dòng)態(tài)規(guī)劃背包問題01背包完全背包問題多重背包分組背包
線性dp數(shù)字三角形子序列最長(zhǎng)上升子序列最長(zhǎng)公共子序列最長(zhǎng)公共上升子序列
編輯距離最短編輯距離編輯距離應(yīng)用
區(qū)間dp計(jì)數(shù)類dp數(shù)位統(tǒng)計(jì)類dp狀態(tài)壓縮dp （二進(jìn)制表示狀態(tài)）蒙德里安的夢(mèng)想最短Hamilton路徑
樹形dp記憶化搜索
貪心區(qū)間問題區(qū)間選點(diǎn)最大不相交區(qū)間數(shù)量區(qū)間分組區(qū)間覆蓋
Huffman樹（合并果子）排序不等式（排隊(duì)打水）絕對(duì)值不等式（貨倉(cāng)選址）推公式（耍雜技的牛）
基礎(chǔ)算法
好用的技巧
c++11
-std=c++11
萬(wàn)能頭文件
#include
基礎(chǔ)模板
#include
using namespace std;
//#defien int long long
#define x first
#define y second
#define endl '\n'
#define rep(i,a,b) for(int i=(a);i<=b;i++)
#define lep(i,a,b) for(int i=(a);i>=b;i--)
#define mem(a,x) memset(a,x,sizeof a)
#define mep(a,x) memcpy(a,x,sizeof x)
typedef long long ll;
typedef pair
typedef pair
typedef pair
typedef pair
const int N=1e6+10;
int n,m,k;
signed main(){
return 0;
}
關(guān)閉同步流
//關(guān)了同步流后只能用endl不能用'\n'了, 也要避免scanf和cin混用
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
輸入輸出
輸入帶空格的字符、字符串
#include
#include
using namespace std;
int main(){
//帶空格的字符輸入
char name[20];
char ch;
string s;
cout<<"輸入字符：" ;
ch=cin.get();
cout< fflush(stdin); cout<<"輸入字符串："; cin.get(name,20);//'\n'還在緩沖區(qū)，建議用getline cout< fflush(stdin);//清空緩沖區(qū) while(getchar()!='\n'); cout<<"輸入字符串："; cin.getline(name,20); cout< fflush(stdin); cout<<"輸入字符串："; getline(cin,s); cout< return 0; } gets(char *str)讀取一行字符串，并將回車去除丟掉。 scanf(“%[^\n]”,str)相當(dāng)于gets，只是用完要用getchar清空回車。 輸出 好用的函數(shù) 常用變量 二分 數(shù)的范圍 #include #include using namespace std; const int N=100; int q[N]; int main(){ int n,m; cin>>n>>m; for(int i=0;i while(m--){ int x; cin>>x; //求第一個(gè)大于（等于）x的數(shù)下標(biāo) 下標(biāo)從0開始 int l=0,r=n-1; while(l int mid=r+l>>1;//注意mid每次要更新，所有放循環(huán)內(nèi)部 if(q[mid]>=x) r=mid; else l=mid+1; } if(q[l]!=x) cout<<"-1 -1"< else{ cout< //求第最后一個(gè)小于（等于）x的數(shù)下標(biāo) int l=0,r=n-1; while(l int mid=l+r+1>>1; if(x>=q[mid]) l=mid; else r=mid-1; } cout< } } return 0; } 數(shù)的三次方根 #include using namespace std; int main(){ double x; cin>>x; double l=-100,r=100; while(r-l>1e-8){//l和r是浮點(diǎn)數(shù) double mid=(l+r)/2;//每次都要更新中間值，所有注意要把mid放循環(huán)內(nèi)部 if(mid*mid*mid>=x) r=mid; else l=mid; } cout< } 排序 快速排序 /* 快速排序 */ #include #include using namespace std; const int N=1000; int n,a[N]; void qs(int a[],int l,int r){ if(l>=r) return; int i=l-1,j=r+1,x=a[l+r>>1]; while(i do i++;while(a[i] do j--;while(a[j]>x); if(i } qs(a,l,j),qs(a,j+1,r); } int main(){ cin>>n; for(int i=0;i qs(a,0,n-1); for(int i=0;i } 第k個(gè)數(shù) #include using namespace std; const int N = 100010; int q[N]; int quick_sort(int q[], int l, int r, int k) { if (l >= r) return q[l]; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } if (j - l + 1 >= k) return quick_sort(q, l, j, k); else return quick_sort(q, j + 1, r, k - (j - l + 1)); } int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); cout << quick_sort(q, 0, n - 1, k) << endl; return 0; } 歸并排序 #include #include using namespace std; const int N=1000; int q[N],temp[N]; void s(int q[N],int l,int r){ //遞歸終止條件 if(l>=r) return; int mid=l+r>>1; //先循環(huán)，要先讓左右兩邊有序 s(q,l,mid),s(q,mid+1,r); //然后讓該部分總體有序 int i=l,j=mid+1,k=0; while(i<=mid&&j<=r){ if(q[i] else temp[k++]=q[j++]; } while(i<=mid) temp[k++]=q[i++]; while(j<=r) temp[k++]=q[j++]; //最后記得把排好的數(shù)組換回來 for(int i=l,j=0;i<=r;i++) q[i]=temp[j++]; } int main(){ int n; cin>>n; for(int i=0;i s(q,0,n-1); for(int i=0;i return 0; } 逆序?qū)?shù)量 #include #include using namespace std; const int N=1e6; int n,q[N],temp[N]; long long res;//開數(shù)據(jù)要注意 void s(int q[],int l,int r){ if(l>=r) return; int mid=l+r>>1,i=l,j=mid+1,k=0; s(q,l,mid),s(q,mid+1,r); while(i<=mid&&j<=r){ if(q[i]<=q[j]) temp[k++]=q[i++];//注意這里有等號(hào) else{ res+=mid-i+1;//左邊后面的也都會(huì)比q[j]大，mid-i+1是從i到mid的個(gè)數(shù) temp[k++]=q[j++]; } } while(i<=mid) temp[k++]=q[i++]; while(j<=r) temp[k++]=q[j++]; for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j]; } int main(){ cin>>n; for(int i=0;i s(q,0,n-1); cout< return 0; } 高精度 高精度加法 /* 高精度加法 1.先將兩數(shù)用字符串輸入，再轉(zhuǎn)換成數(shù)字，然后逆序壓入數(shù)組中 2.執(zhí)行加法步驟，注意要明確那個(gè)數(shù)位數(shù)比較多，t表示進(jìn)位數(shù)，本位余數(shù)，進(jìn)位除數(shù) 3.逆序輸出 當(dāng)兩數(shù)過大時(shí)，可用壓位加法 */ #include #include using namespace std; vector if(a.size() int t=0; vector for(int i=0;i if(i if(i c.push_back(t%10); t/=10; } return c; } int main(){ string a,b; vector cin>>a>>b; for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0'); auto c=add(A,B); for(int i=c.size()-1;i>=0;i--) cout< return 0; } 壓九位（數(shù)字比較大時(shí)） #include #include #include using namespace std; const int base=1e9; vector if(a.size() int t=0; vector for(int i=0;i if(i if(i c.push_back(t%base); t/=base; } return c; } int main(){ string a,b; cin>>a>>b; vector for(int i=a.size()-1,j=0,s=0,t=1;i>=0;i--){ s+=(a[i]-'0')*t; j++,t*=10; if(j==9||i==0){ A.push_back(s); j=0,s=0,t=1; } } for(int i=b.size()-1,j=0,s=0,t=1;i>=0;i--){ s+=(b[i]-'0')*t; j++,t*=10; if(j==9||i==0){ B.push_back(s); j=0,s=0,t=1; } } auto c=add(A,B); cout< for(int i=c.size()-2;i>=0;i--) printf("%09d",c[i]); return 0; } %9d表示占九個(gè)字符位置，前面補(bǔ)空格，%-9d表示后面補(bǔ)空格。%09d表示前面補(bǔ)0。 高精度減法 /* 高精度減法 1.先將兩數(shù)用字符串輸入，再轉(zhuǎn)換成數(shù)字，然后逆序壓入數(shù)組中 2.執(zhí)行減法步驟，注意要明確那個(gè)數(shù)比較大cmp函數(shù)，t表示借位數(shù)0或1，本位正余數(shù) 3.逆序輸出 */ #include #include using namespace std; bool cmp(vector if(a.size()!=b.size()) return a.size()>b.size(); else{ for(int i=a.size()-1;i>=0;i--){ if(a[i]!=b[i]) return a[i]>b[i]; } } return true; } vector int t=0; vector for(int i=0;i if(i if(i c.push_back((t+10)%10); if(t<0) t=1; else t=0; } if(c.size()>1&&c.back()==0) c.pop_back(); return c; } int main(){ string a,b; vector cin>>a>>b; for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0'); vector if(cmp(A,B)) c=sul(A,B); else{ cout<<'-'; c=sul(B,A);//注意換位 } for(int i=c.size()-1;i>=0;i--) cout< return 0; } 高精度乘法 /* 高精度乘法 1.先將兩數(shù)用字符串輸入，再轉(zhuǎn)換成數(shù)字，然后逆序壓入數(shù)組中 2.執(zhí)行乘法步驟，t表示進(jìn)位數(shù)，本位余數(shù)，進(jìn)位除數(shù) 3.逆序輸出 */ #include #include using namespace std; vector int t=0; vector for(int i=0;i if(i c.push_back(t%10); t/=10; } if(c.size()>1&&c.back()==0) c.pop_back(); return c; } int main(){ string a; int b; vector cin>>a>>b; for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } vector c=mul(A,b); for(int i=c.size()-1;i>=0;i--) cout< return 0; } 高精度除法 /* 高精度除法 1.先將兩數(shù)用字符串輸入，再轉(zhuǎn)換成數(shù)字，然后逆序壓入數(shù)組中 2.執(zhí)行除法步驟，t表示除位數(shù) 3.逆序輸出 */ #include #include #include using namespace std; vector int t=0; vector for(int i=a.size()-1;i>=0;i--){ t=t*10+a[i]; c.push_back(t/b);//此處與前面三個(gè)不同 t%=b; } reverse(c.begin(),c.end()); if(c.size()>1&&c.back()==0) c.pop_back(); return c; } int main(){ string a; int b; vector cin>>a>>b; for(int i=a.size()-1;i>=0;i--){ A.push_back(a[i]-'0'); } vector c=div(A,b); for(int i=c.size()-1;i>=0;i--) cout< return 0; } 總結(jié)：除了除法函數(shù)里的步驟循環(huán)是從數(shù)組后往前，然后完了反轉(zhuǎn)一下reverse，這點(diǎn)不同。其他都是逆序輸入逆序輸出，然后函數(shù)里面數(shù)組從前往后。t都是初始化為0 雙指針 最長(zhǎng)連續(xù)不重復(fù)子序列 #include using namespace std; const int N=1000; int q[N],a[N]; int main(){ int n,res=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1,j=1;i<=n;i++){ q[a[i]]++; while(j res=max(res,i-j+1); } cout< return 0; } 離散化（區(qū)間和） #include #include #include using namespace std; const int N=100010; typedef pair vector vector int n,m; int a[N],s[N]; int find(int x){ int l=0,r=alls.size()-1; while(l int mid=l+r>>1; if(x<=alls[mid]) r=mid; else l=mid+1; } return l+1; } int main(){ cin>>n; for(int i=0;i int x,c; cin>>x>>c; add.push_back({x,c}); alls.push_back(x); } cin>>m; for(int i=0;i int l,r; cin>>l>>r; req.push_back({l,r}); alls.push_back(l); alls.push_back(r); } for(auto adds:add){ a[find(adds.first)]+=adds.second; } sort(alls.begin(),alls.end());//第一個(gè)數(shù)指針和最后一個(gè)數(shù)的后一位指針 alls.erase(unique(alls.begin(),alls.end()),alls.end()); for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; for(auto re:req){ int l=find(re.first),r=find(re.second); cout< } return 0; } 區(qū)間合并 /* 區(qū)間覆蓋 1.一般用pair存區(qū)間左右端點(diǎn)，然后放入vector數(shù)組中 2.初始化，將當(dāng)前的起始和終止位置初始化為最小，然后根據(jù)每個(gè)區(qū)間 的左端點(diǎn)從小到大排序 3.枚舉遍歷每個(gè)區(qū)間，當(dāng)新區(qū)間左端點(diǎn)大于目前的ed并且ed不是初始值時(shí)， 將前面的st和ed區(qū)間放入res，然后以新區(qū)間的左右端點(diǎn)作為新的st和ed；否則 用當(dāng)前區(qū)間的右端點(diǎn)更新ed，比較誰(shuí)大。 4.最后有區(qū)間放入時(shí)，st不等于初始值，要記得把最后一個(gè)st和ed放入res 5.然后將res賦值給segs。 */ #include #include #include using namespace std; typedef pair void merge(vector vector sort(segs.begin(),segs.end()); int st=-2e9,ed=-2e9; for(auto seg:segs){ if(ed if(st!=-2e9) res.push_back({st,ed}); st=seg.first,ed=seg.second; } else ed=max(ed,seg.second); } if(st!=-2e9) res.push_back({st,ed}); segs=res; } int main(){ int n; cin>>n; vector for(int i=0;i int l,r; cin>>l>>r; segs.push_back({l,r}); } merge(segs); cout< return 0; } 數(shù)據(jù)結(jié)構(gòu) 常見結(jié)構(gòu) 單鏈表 #include #include using namespace std; const int N=100010; int h,e[N],ne[N],idx;//一般都將頭結(jié)點(diǎn)下標(biāo)初始化為-1，idx表示當(dāng)前已經(jīng)用了第幾個(gè)點(diǎn)了，是下標(biāo)（指針） 。 //初始化 void init(){ idx=0; h=-1; } //將x插入到頭結(jié)點(diǎn) void addh(int x){ e[idx]=x,ne[idx]=h,h=idx++; } //在k下標(biāo)節(jié)點(diǎn)后面插入x void addx(int k,int x){ e[idx]=x,ne[idx]=ne[k],ne[k]=idx++; } //刪除k下標(biāo)節(jié)點(diǎn)后面一個(gè)數(shù) void delx(int k){ ne[k]=ne[ne[k]]; } 雙鏈表 #include #include using namespace std; const int N=100010; int l[N],r[N],idx; //初始化 void init(){ r[0]=1; l[1]=0; idx=2; } //在下標(biāo)為k的節(jié)點(diǎn)后插入值x void addx(int k,int x){ ne[idx]=x; l[idx]=k,r[idx]=r[k]; l[r[k]]=idx,r[k]=idx++; } //刪除下標(biāo)為k的節(jié)點(diǎn) void del(int k){ r[l[k]]=r[k]; l[r[k]]=l[k]; } 單調(diào)棧 不管棧還是隊(duì)列，tt都是指向最后一個(gè)元素（最后一個(gè)元素下標(biāo)） //單調(diào)棧求距離x最近的小于（大于）x的數(shù) //棧還是隊(duì)列，tt都是指向最后一個(gè)元素 #include #include using namespace std; const int N=100010; int tt,s[N]; int main(){ int n; cin>>n; while(n--){ int x; cin>>x; while(tt&&s[tt]>=x) tt--; if(!tt) cout<<"-1"; else cout< s[++tt]=x; } return 0; } 單調(diào)隊(duì)列（滑動(dòng)窗口） //單調(diào)隊(duì)列求窗口內(nèi)最大（?。┲?/p> /* n個(gè)數(shù)n重循環(huán) 1.隊(duì)列不空，看隊(duì)頭元素有沒有超出范圍 2.隊(duì)列不空，按條件更新隊(duì)尾元素 3.隊(duì)列不空，按條件輸出隊(duì)頭元素 */ #include #include using namespace std; const int N=100010; int hh=0,tt=-1,q[N],a[N];//棧還是隊(duì)列，tt都是指向最后一個(gè)元素 int main(){ int n,k; cin>>n>>k; for(int i=0;i //求窗口最內(nèi)大值，隊(duì)列里面是遞減的，只保留價(jià)值比a[i]大的 int hh=0,tt=-1; for(int i=0;i if(hh<=tt&&q[hh] while(hh<=tt&&a[q[tt]]<=a[i]) tt--; q[++tt]=i;//包括這個(gè)數(shù)在內(nèi)的窗口 if(i>=k-1) cout< } puts(""); //求窗口內(nèi)最小值 hh=0,tt=-1; for(int i=0;i if(hh<=tt&&q[hh] while(hh<=tt&&a[q[tt]]>=a[i]) tt--; q[++tt]=i; if(i>=k-1) cout< } return 0; } kmp字符串 #include using namespace std; const int N=100010,M=1000010; int n,m; int ne[N];//ne[i]=j表示的是p字符串中以i為終點(diǎn)的子串p[1~j]=p[i-j+1,i] 是相等的 char s[M],p[N];//s是母串，p是子串 int main(){ cin>>n>>p+1>>m>>s+1;//下標(biāo)從1開始 //求ne數(shù)組 for(int i=2,j=0;i<=n;i++){ while(j&&p[i]!=p[j+1]) j=ne[j]; if(p[i]==p[j+1]) j++; ne[i]=j; } //匹配過程 for(int i=1,j=0;i<=m;i++){ while(j&&s[i]!=p[j+1]) j=ne[j]; if(s[i]==p[j+1]) j++; if(j==n){ cout< j=ne[j]; } } return 0; } 字典樹（樹狀數(shù)組） 字符串統(tǒng)計(jì) #include using namespace std; const int N=100010; /* 字典樹，樹狀數(shù)組 son存的是本字母的下標(biāo)，也是下個(gè)字母的一維（指向下一個(gè)字母），二維是本字母的ascll碼， idx下標(biāo)，一維從1開始 */ int son[N][26],cnt[N],idx; char str[N]; void insert(char *str){ int p=0; for(int i=0;str[i];i++){//字符串遍歷 int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int query(char *str){ int p=0; for(int i=0;str[i];i++){ int u=str[i]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return cnt[p]; } int main(){ int n; cin>>n; while(n--){ char op[2]; scanf("%s%s",op,str); if(*op=='I') insert(str);//第一個(gè)字符 else printf("%d\n",query(str)); } return 0; } 最大異或?qū)?/p> /* 最大異或?qū)€是利用樹狀數(shù)組和位運(yùn)算的知識(shí) */ #include #include using namespace std; const int N=100010,M=3100010; int n; int a[N],son[M][2],idx; void insert(int x){ int p=0; for(int i=30;i>=0;i--){ int &s=son[p][x>>i&1]; if(!s) s=++idx; p=s; } } int search(int x){ int p=0,res=0; for(int i=30;i>=0;i--){ int s=x>>i&1; if(son[p][!s]){ res+=1< p=son[p][!s]; } else p=son[p][s]; } return res; } int main(){ cin>>n; for(int i=0;i cin>>a[i]; insert(a[i]); } int res=0; for(int i=0;i cout< return 0; } 并查集 合并集合 /* 合并集合 */ #include #include using namespace std; const int N=100010; int p[N]; //這個(gè)函數(shù)本質(zhì)是找到節(jié)點(diǎn)x的祖宗節(jié)點(diǎn)，并且路徑壓縮了，使得路徑上的所有點(diǎn)都指向祖宗節(jié)點(diǎn) int find(int x){ if(p[x]!=x) p[x]=find(p[x]);//讓x的父節(jié)點(diǎn)指向父節(jié)點(diǎn)的父節(jié)點(diǎn)，一直遞歸，直到p[x]是x的祖宗節(jié)點(diǎn) return p[x]; } int main(){ int n,m; cin>>n>>m; for(int i=0;i>n;i++) p[i]=i;//初始化，使每個(gè)點(diǎn)父節(jié)點(diǎn)都指向自己 while(m--){ char op[2]; int a,b; cin>>op>>a>>b; if(*op=='M') p[find(a)]=find(b);//a的父節(jié)點(diǎn)指向b，讓b成為a的父節(jié)點(diǎn) else{ if(find(a)==find(b)) puts("YES"); else puts("NO"); } } return 0; } 連通塊中點(diǎn)的數(shù)量 /* 連通塊中的數(shù)量，再開一個(gè)數(shù)組存儲(chǔ)連通塊點(diǎn)數(shù)，一般是祖宗節(jié)點(diǎn)的cnt.并查集加點(diǎn)數(shù)維護(hù) 調(diào)試小技巧，一般輸入輸出有問題，先看for循環(huán)的輸入輸出 */ #include #include using namespace std; const int N=100010; int p[N],cnt[N]; //這個(gè)函數(shù)本質(zhì)是找到節(jié)點(diǎn)x的祖宗節(jié)點(diǎn)，并且路徑壓縮了，使得路徑上的所有點(diǎn)都指向祖宗節(jié)點(diǎn) int find(int x){ if(p[x]!=x) p[x]=find(p[x]);//讓x的父節(jié)點(diǎn)指向父節(jié)點(diǎn)的父節(jié)點(diǎn)，一直遞歸，直到p[x]是x的祖宗節(jié)點(diǎn) return p[x]; } int main(){ int n,m; cin>>n>>m; for(int i=0;i p[i]=i; cnt[i]=1; } while(m--){ string op;//字符串輸入操作信號(hào) int a,b; cin>>op; if(op=="C"){ cin>>a>>b; a=find(a),b=find(b); if(a!=b){ p[a]=b; cnt[b]+=cnt[a]; } } else if(op=="Q1"){ cin>>a>>b; if(find(a)==find(b)) puts("YES"); else puts("NO"); } else{ cin>>a; cout< } } return 0; } 食物鏈 /* 食物鏈，并查集加距離維護(hù) A←B←C←A: A吃B, B吃C, C吃A,若距離%3余數(shù)為0同類，1B被根節(jié)點(diǎn)吃，2C吃根節(jié)點(diǎn) */ #include #include using namespace std; const int N=500010; int p[N],d[N];//d數(shù)組存放離父節(jié)點(diǎn)距離，路徑壓縮優(yōu)化完就是到根節(jié)點(diǎn)距離 //遞歸調(diào)用，找到根節(jié)點(diǎn)，完成路徑壓縮+尋找根節(jié)點(diǎn) int find(int x){ if(p[x]!=x){ int t=find(p[x]);//向上搜索根節(jié)點(diǎn) d[x]+=d[p[x]];//到根節(jié)點(diǎn)的距離等于到父節(jié)點(diǎn)的距離+父節(jié)點(diǎn)到根節(jié)點(diǎn)的距離 p[x]=t;//父節(jié)點(diǎn)變根節(jié)點(diǎn) } return p[x]; } int main(){ int n,m,res=0; cin>>n>>m; for(int i=1;i<=n;i++){//初始化，使每個(gè)點(diǎn)父節(jié)點(diǎn)都指向自己 p[i]=i; } while(m--){ int op,x,y; cin>>op>>x>>y; if(x>n||y>n) res++; else{ int px=find(x),py=find(y); if(op==1){//x,y是同類的判斷。x，y到根節(jié)點(diǎn)距離相等 if(px==py&&(d[x]-d[y])%3) res++;//在同一個(gè)集合中，但不是同類關(guān)系，錯(cuò)誤 else if(px!=py){//沒在一個(gè)集合，加在一個(gè)集合中，維持距離是同類 **** p[px]=py; d[px]=d[y]-d[x]; } } else{//判斷x吃y，若x吃y，則要x，y在同一個(gè)集合中，x到根節(jié)點(diǎn)的距離要比y小1 if(px==py&&(d[y]-1-d[x])%3) res++;//在同一集合中，但不是x吃y的關(guān)系 else if(px!=py){ p[px]=py; d[px]=d[y]-d[x]-1; } } } } cout< return 0; } 堆 堆排序 /* 堆排序 */ #include #include using namespace std; const int N=500010; int n,m; int h[N],cnt;//cnt表示堆中最后一個(gè)數(shù)的下標(biāo)，從1開始 void down(int u){//傳堆的下標(biāo) int t=u;//t為最小數(shù)的下標(biāo) if(u*2<=cnt&&h[u*2] if(u*2+1<=cnt&&h[u*2+1] if(u!=t){ swap(h[u],h[t]); down(t); } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>h[i]; cnt=n; for(int i=n/2;i>0;i--) down(i);//整理成小根堆 while(m--){ cout< h[1]=h[cnt--]; down(1); } puts(""); return 0; } 模擬堆 /* 模擬堆。要重寫交換函數(shù) */ #include #include #include using namespace std; const int N=500010; int n,m;//m代表第m個(gè)插入的數(shù) int h[N],ph[N],hp[N],cnt;//cnt表示堆中最后一個(gè)數(shù)的下標(biāo)，從1開始 //ph[k]:第k個(gè)插入的數(shù)在堆中的編號(hào)，hp[i]:在堆中編號(hào)為i的位置是第幾個(gè)插入的 void heap_swap(int a,int b){//a,b表示堆的編號(hào)（下標(biāo)） swap(ph[hp[a]],ph[hp[b]]); swap(hp[a],hp[b]); swap(h[a],h[b]); } void down(int u){//傳堆的下標(biāo) int t=u;//t為最小數(shù)的下標(biāo) if(u*2<=cnt&&h[u*2] if(u*2+1<=cnt&&h[u*2+1] if(u!=t){ heap_swap(u,t); down(t); } } void up(int u){ while(u/2&&h[u] heap_swap(u,u/2); u=u/2; } } int main(){ cin>>n; while(n--){ char op[5]; int k,x; cin>>op; if(!strcmp(op,"I")){//若op定義為string，則可以用op=="I"判斷 cin>>x; cnt++; m++; ph[m]=cnt,hp[cnt]=m; h[cnt]=x; up(cnt); } else if(!strcmp(op,"PM")) cout< else if(!strcmp(op,"DM")){ heap_swap(1,cnt); cnt--; down(1); } else if(!strcmp(op,"D")){ cin>>k;//刪除第k個(gè)插入的數(shù) k=ph[k];//變?yōu)橄聵?biāo)編號(hào) heap_swap(cnt,k); cnt--; up(k); down(k); } else{ cin>>k>>x; k=ph[k]; h[k]=x; up(k); down(k); } } return 0; } 哈希表 模擬散列表 開放尋址法 /* 模擬散列表。開放尋址法,用x余數(shù)來存放，可以減小范圍 */ #include #include #include using namespace std; const int N=200003,null=0x3f3f3f3f;//N最好是質(zhì)數(shù) int h[N]; int find(int x){//找到x的所在位置下標(biāo)或者x應(yīng)該存放位置下標(biāo) int t=(x%N+N)%N; while(h[t]!=null&&h[t]!=x){ t++; if(t==N) t=0; } return t; } int main(){ memset(h,0x3f,sizeof h); int n; cin>>n; while(n--){ char op[2]; int x; cin>>op>>x; if(*op=='I') h[find(x)]=x; else{ if(h[find(x)]==null) puts("NO"); else puts("YES"); } } return 0; } 拉鏈法 /* 模擬散列表。拉鏈法 */ #include #include #include using namespace std; const int N=100003;//N最好是質(zhì)數(shù) int h[N],e[N],ne[N],idx; bool find(int x){//判斷鏈表中是否有x這個(gè)數(shù) int t=(x%N+N)%N; for(int i=h[t];~i;i=ne[i]){ if(e[i]==x) return true; } return false; } void insert(int x){//插入x到相應(yīng)鏈表中 int t=(x%N+N)%N; e[idx]=x,ne[idx]=h[t],h[t]=idx++;//頭插法 } int main(){ memset(h,-1,sizeof h); int n; cin>>n; while(n--){ char op[2]; int x; cin>>op>>x; if(*op=='I') insert(x); else{ if(!find(x)) puts("NO"); else puts("YES"); } } return 0; } 字符串哈希 /* 字符串哈希 */ #include #include #include using namespace std; typedef unsigned long long ull; const int N=100010,P=131; //p進(jìn)制或取13331 int n,m; char str[N]; ull h[N],p[N];//h[i]表示前i為和，從右往左的前綴和，像一般的數(shù)字一樣，左邊是高位。 //p[i]表示第i位的權(quán)重。p[i]=p^i。p[0]=1。 ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } int main(){ cin>>n>>m>>str+1; p[0]=1; for(int i=1;i<=n;i++){ h[i]=h[i-1]*P+str[i];//前i個(gè)字符轉(zhuǎn)換成的數(shù) p[i]=p[i-1]*P;//表示P的i次方。 } while(m--){//m次詢問 int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2; if(get(l1,r1)==get(l2,r2)) puts("YES"); else puts("NO"); } return 0; } 搜索和圖論 dfs 排序數(shù)字 /* 排列數(shù)字 */ #include #include #include using namespace std; typedef unsigned long long ull; const int N=10; int n; int path[N],st[N]; void dfs(int u){ if(u==n){ for(int i=0;i cout< puts(""); } for(int i=1;i<=n;i++){ if(!st[i]){ path[u]=i; st[i]=true; dfs(u+1); st[i]=false; } } } int main(){ cin>>n; dfs(0); return 0; } n皇后問題 直接考慮 #include using namespace std; const int N = 10; int n; bool row[N], col[N], dg[N * 2], udg[N * 2]; char g[N][N]; void dfs(int x, int y, int s) { if (s > n) return; if (y == n) y = 0, x ++ ; if (x == n) { if (s == n) { for (int i = 0; i < n; i ++ ) puts(g[i]); puts(""); } return; } g[x][y] = '.'; dfs(x, y + 1, s); if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) { row[x] = col[y] = dg[x + y] = udg[x - y + n] = true; g[x][y] = 'Q'; dfs(x, y + 1, s + 1); g[x][y] = '.'; row[x] = col[y] = dg[x + y] = udg[x - y + n] = false; } } int main() { cin >> n; dfs(0, 0, 0); return 0; } 優(yōu)化情況 /* n皇后問題 */ #include #include #include using namespace std; const int N=10; int n; int p[N][N],col[N],dg[N*2],udg[N*2]; char g[N][N];//char類型 void dfs(int u,int t){ if(t>n) return;//剪枝 if(u==n){//我們所需要的結(jié)果 if(t==n){ for(int i=0;i puts(g[i]);//輸出一串并自動(dòng)換行 } puts(""); return; } for(int i=0;i if(!col[i]&&!dg[i-u+n]&&!udg[i+u]){ g[u][i]='Q'; col[i]=dg[i-u+n]=udg[i+u]=true; dfs(u+1,t+1); col[i]=dg[i-u+n]=udg[i+u]=false; g[u][i]='.'; } } } int main(){ cin>>n; for(int i=0;i for(int j=0;j g[i][j]='.'; dfs(0,0); return 0; } 總結(jié)： 1.dfs的本質(zhì)是利用遞歸這種思想（遞歸內(nèi)部用棧實(shí)現(xiàn)），用for來遍歷此層的所有可能的取值情況，然后把已經(jīng)取值的情況標(biāo)記，避免下面遞歸再用此值，再進(jìn)入下層繼續(xù)遞歸，在調(diào)用遞歸結(jié)束后取消標(biāo)記回溯，進(jìn)入此層的下個(gè)可能情況 2.dfs的一般步驟是退出遞歸的條件，有剪枝和遞歸到最后一層的下一層可取結(jié)果這兩種情況。然后就是每層（此層）可取的可能情況枚舉（多個(gè)用for循環(huán)，兩個(gè)直接枚舉了），對(duì)于取完一個(gè)情況進(jìn)入下層遞歸前需要標(biāo)記這個(gè)情況避免影響下面遞歸，遞歸執(zhí)行完后再進(jìn)行回溯，需要把標(biāo)記取消 bfs 走迷宮 /* 走迷宮 */ #include #include #include #include using namespace std; typedef pair const int N=110; int n,m; int g[N][N],d[N][N]; int bfs(){ queue memset(d,-1,sizeof d); d[0][0]=0; q.push({0,0}); int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; while(q.size()){ auto t=q.front(); q.pop(); for(int i=0;i<4;i++){ int x=t.first+dx[i],y=t.second+dy[i]; if(x>=0&&x d[x][y]=d[t.first][t.second]+1; q.push({x,y}); } } } return d[n-1][m-1]; } int main(){ cin>>n>>m; for(int i=0;i for(int j=0;j cin>>g[i][j]; } cout< return 0; } 八數(shù)碼 /* 八數(shù)碼 */ #include #include #include #include #include using namespace std; string state; int bfs(){ queue unordered_map string end="12345678x"; q.push(state); d[state]=0; int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; while(q.size()){ auto t=q.front(); q.pop(); if(t==end) return d[t]; int di=d[t]; int k=t.find('x');//字符串查找下標(biāo)函數(shù) int x=k/3,y=k%3; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>=0&&a<3&&b>=0&&b<3){ swap(t[a*3+b],t[k]);//交換字符串中下標(biāo)為a*3+b與k的字符 if(!d.count(t)){//map中判斷key是否存在 d[t]=di+1;//此時(shí)的t為交換后的字符串（另一種狀態(tài)） q.push(t); } swap(t[a*3+b],t[k]);//交換回來進(jìn)行下次移動(dòng)，不影響下次 } } } return -1; } int main(){ char s[2];//這個(gè)挺好用 for(int i=0;i<9;i++){ cin>>s; state+=*s; } cout< return 0; } 總結(jié)： bfs的本質(zhì)是利用隊(duì)列，有最短路的性質(zhì)。一般步驟是將滿足條件的情況入隊(duì)，有距離數(shù)組需要初始化的初始化，然后while隊(duì)列不空，取隊(duì)頭并將其出隊(duì)，再將于隊(duì)頭有關(guān)的情況或者隊(duì)頭的下一步的所有情況入隊(duì)，最后返回我們需要的“情況。 樹圖的搜索 dfs樹的重心 /* 樹的重心。用dfs來求 */ #include #include #include #include using namespace std; const int N=100010,M=N*2; int n; int h[N],e[N],ne[M],idx; int ans=N;//所需要的答案，每個(gè)子樹個(gè)數(shù)最大的最小值 bool st[N];//標(biāo)記已經(jīng)走過的點(diǎn) void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int dfs(int u){//求以u(píng)為根的所有子樹的節(jié)點(diǎn)個(gè)數(shù)，包括根節(jié)點(diǎn) int res=0,sum=1;//res求子樹個(gè)數(shù)最大值，sum是包括根節(jié)點(diǎn)的總節(jié)點(diǎn)數(shù) st[u]=true;//判斷那個(gè)是重心，每個(gè)點(diǎn)都遍歷到 for(int i=h[u];~i;i=ne[i]){//求res和sum int j=e[i]; if(!st[j]){ int s=dfs(j);//s是以j為根節(jié)點(diǎn)的總節(jié)點(diǎn)個(gè)數(shù) res=max(res,s);//求最大的子樹節(jié)點(diǎn)數(shù) sum+=s; } } res=max(res,n-sum);//求最大 ans=min(ans,res);//答案是res的最小值 return sum; } int main(){ cin>>n; memset(h,-1,sizeof h); for(int i=0;i int a,b; cin>>a>>b; add(a,b),add(b,a);//樹無(wú)向邊 } dfs(1); cout< return 0; } 圖中點(diǎn)的層次 /* 圖中點(diǎn)的層次。bfs來求 */ #include #include #include #include #include using namespace std; const int N=100010,M=N*2; //在上面定義的一些數(shù)組記得初始化 int n,m; int h[N],e[N],ne[M],idx; int d[N];//存儲(chǔ)每個(gè)點(diǎn)的層次，d[i]表示點(diǎn)i所在層次 void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int bfs(){ memset(d,-1,sizeof d); d[1]=0; queue q.push(1); while(q.size()){ auto t=q.front(); q.pop(); for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(d[j]==-1){ d[j]=d[t]+1; q.push(j); } } } return d[n]; } int main(){ cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i int a,b; cin>>a>>b; add(a,b); } cout< return 0; } 拓?fù)渑判?/p> /* 拓?fù)渑判?。用bfs來求，手寫隊(duì)列 */ #include #include #include #include #include using namespace std; const int N=100010,M=N*2; //在上面定義的一些數(shù)組記得初始化 int n,m; int h[N],e[N],ne[M],idx; int d[N];//存儲(chǔ)每個(gè)點(diǎn)的入度 int q[N],hh,tt=-1;//手寫隊(duì)列 void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool topsort(){ for(int i=1;i<=n;i++){ if(!d[i]) q[++tt]=i; } while(hh<=tt){ auto t=q[hh++]; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(--d[j]==0) q[++tt]=j; } } if(tt else return true; } int main(){ cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i int a,b; cin>>a>>b; add(a,b);//a→b d[b]++;//b點(diǎn)入度加1 } if(!topsort()) puts("-1"); else{ for(int i=0;i cout< puts(""); } return 0; } 最短路算法 單源最短路 樸素版dijkstra /* 樸素版dijkstra。用領(lǐng)接矩陣來表示 */ #include #include #include #include #include using namespace std; const int N=510; //在上面定義的一些數(shù)組記得初始化 int n,m; int g[N][N];//領(lǐng)接矩陣來存儲(chǔ)圖 int d[N];//存儲(chǔ)每個(gè)點(diǎn)到源點(diǎn)的距離 bool st[N];//判斷點(diǎn)是否在s集合中。s集合表示已經(jīng)確定了最短路的點(diǎn)集 int dj(){ //初始化 memset(d,0x3f,sizeof d); d[1]=0; //將所有點(diǎn)都放入s集合中，每次找到里源點(diǎn)最近的點(diǎn)，然后用此點(diǎn)來更新其他點(diǎn) for(int i=0;i int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(d[j] t=j; } } st[t]=true; for(int j=1;j<=n;j++){ if(d[j]>d[t]+g[t][j]) d[j]=d[t]+g[t][j]; } } if(d[n]==0x3f3f3f3f) return -1; return d[n]; } int main(){ cin>>n>>m; memset(g,0x3f,sizeof g); while(m--){ int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c);//重邊用最短的路徑 } cout< return 0; } 堆優(yōu)化版dijsktra /* 堆優(yōu)化版dijkstra。用小根堆優(yōu)化，直接取每次距離源點(diǎn)最近的點(diǎn) */ #include #include #include #include #include using namespace std; typedef pair const int N=1e6+10; int n,m; int h[N],e[N],ne[N],w[N],idx;//鄰接表存儲(chǔ) int d[N];//每個(gè)點(diǎn)到源點(diǎn)距離 bool st[N]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } int dj(){ //初始化 memset(d,0x3f,sizeof d); d[1]=0; priority_queue q.push({0,1}); while(q.size()){ auto t=q.top(); q.pop(); int di=t.first,v=t.second; if(st[v]) continue; st[v]=true; for(int i=h[v];~i;i=ne[i]){ int j=e[i]; if(d[j]>d[v]+w[i]){//注意是w[i]而不是w[j],i是下標(biāo)，j是點(diǎn) d[j]=d[v]+w[i]; if(!st[j]) q.push({d[j],j}); } } } if(d[n]==0x3f3f3f3f) return -1; return d[n]; } int main(){ cin>>n>>m; memset(h,-1,sizeof h); while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c);//有向圖 } cout< return 0; } bellman-ford算法（可存在負(fù)權(quán)邊） /* 有邊數(shù)限制的最短路，bellman-ford算法 */ #include #include #include #include #include using namespace std; const int N=510,M=10010; struct Edge{ int a,b,c; }e[M]; int n,m,k;//點(diǎn)數(shù)，邊數(shù)，限制邊數(shù) int d[N]; int last[N];//上層限制邊數(shù)條件下，各點(diǎn)到源點(diǎn)距離 void bellman_ford(){ memset(d,0x3f,sizeof d); d[1]=0; for(int i=0;i memcpy(last,d,sizeof d);//用memset轉(zhuǎn)換無(wú)效，上層邊數(shù)限制 for(int j=0;j int a=e[j].a,b=e[j].b,c=e[j].c; if(d[b]>last[a]+c){ d[b]=last[a]+c; } } } } int main(){ cin>>n>>m>>k; for(int i=0;i int a,b,c; cin>>a>>b>>c; e[i]={a,b,c}; } bellman_ford(); if(d[n]>0x3f3f3f3f/2) puts("impossible");//存在負(fù)權(quán)可能會(huì)使INF變小 else cout< return 0; } spfa算法（可存在負(fù)權(quán)邊） spfs是bellman-ford算法用隊(duì)列優(yōu)化的算法，每次松弛不用每各點(diǎn)都判斷更新，只有某個(gè)點(diǎn)的前驅(qū)節(jié)點(diǎn)更新才會(huì)導(dǎo)致改點(diǎn)更新，st數(shù)組來表示被更新的點(diǎn)，入隊(duì)true，出隊(duì)false，可逆。 1.求最短路 /* spfa算法求最短路，用鄰接表存儲(chǔ)，用隊(duì)列來優(yōu)化 */ #include #include #include #include #include using namespace std; const int N=10010; int n,m;//點(diǎn)數(shù)，邊數(shù) int h[N],e[N],ne[N],w[N],idx;//鄰接表第一反應(yīng)要記得初始化h數(shù)組 int d[N]; bool st[N];//表示被更新的點(diǎn)，而不是判斷是否在s集合中 void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void spfa(){ memset(d,0x3f,sizeof d); d[1]=0; queue q.push(1); st[1]=true; while(q.size()){ auto t=q.front(); q.pop(); st[t]=false; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(d[j]>d[t]+w[i]){ d[j]=d[t]+w[i]; if(!st[j]){ q.push(j); st[j]=true; } } } } } int main(){ cin>>n>>m; memset(h,-1,sizeof h);//不要忘了初始化，不然沒有輸出程序一直運(yùn)行。 for(int i=0;i int a,b,c; cin>>a>>b>>c; add(a,b,c); } spfa(); if(d[n]==0x3f3f3f3f) puts("impossible");//存在負(fù)權(quán)可能會(huì)使INF變小 else cout< return 0; } 2.求是否存在負(fù)環(huán) /* spfa算法求是否有負(fù)權(quán)回路，用鄰接表存儲(chǔ)，用隊(duì)列來優(yōu)化 要多一個(gè)cnt數(shù)組來存儲(chǔ)到達(dá)每個(gè)點(diǎn)的邊數(shù)，若邊數(shù)大于n-1則說明有負(fù)權(quán)回路 然后全部點(diǎn)也要先入隊(duì) */ #include #include #include #include #include using namespace std; const int N=10010; int n,m;//點(diǎn)數(shù)，邊數(shù) int h[N],e[N],ne[N],w[N],idx;//鄰接表第一反應(yīng)要記得初始化h數(shù)組 int d[N]; int cnt[N];//表示到達(dá)i點(diǎn)所經(jīng)過的邊數(shù) bool st[N];//表示被更新的點(diǎn)，而不是判斷是否在s集合中 void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } bool spfa(){ memset(d,0x3f,sizeof d); d[1]=0; queue for(int i=i;i<=n;i++){//將所有的點(diǎn)全部入隊(duì) q.push(i); st[i]=true; } while(q.size()){ auto t=q.front(); q.pop(); st[t]=false; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(d[j]>d[t]+w[i]){ d[j]=d[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>n-1) return true; if(!st[j]){ q.push(j); st[j]=true; } } } } return false; } int main(){ cin>>n>>m; memset(h,-1,sizeof h);//不要忘了初始化，不然沒有輸出程序一直運(yùn)行。 for(int i=0;i int a,b,c; cin>>a>>b>>c; add(a,b,c); } if(spfa()) puts("YES");//存在負(fù)權(quán)可能會(huì)使INF變小 else puts("NO"); return 0; } 多源最短路 Floyd算法 /* Floyd算法求多源回路問題。點(diǎn)的取值范圍三個(gè)for循環(huán) */ #include #include #include #include #include using namespace std; const int N=210,inf=1e9; int n,m;//點(diǎn)數(shù)，邊數(shù) int d[N][N];//d[x][y]表示點(diǎn)x到點(diǎn)y的距離 void floyd(){ for(int k=1;k<=n;k++)//點(diǎn)的取值范圍 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int Q; cin>>n>>m>>Q; //初始化距離 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) d[i][j]=0; else d[i][j]=inf; for(int i=0;i int a,b,c; cin>>a>>b>>c; d[a][b]=min(d[a][b],c); } floyd(); while(Q--){ int a,b; cin>>a>>b; int t=d[a][b]; if(t>inf/2) puts("impossible"); else cout< } return 0; } 總結(jié)：距離數(shù)組記得初始化，圖的表示方式也要記得初始化。 然后h數(shù)組沒有初始化，輸完數(shù)據(jù)不管怎么按都沒有反應(yīng)，也不會(huì)結(jié)束，程序會(huì)一直執(zhí)行。切記要初始化為-1。 最小生成樹 prim /* prim算法求最小生成樹的權(quán)值 */ #include #include #include #include #include using namespace std; const int N=210,inf=0x3f3f3f3f; int n,m; //點(diǎn)邊 int g[N][N];//領(lǐng)接矩陣存儲(chǔ) int d[N];//每個(gè)點(diǎn)到s的距離 bool st[N];//判斷是否是已經(jīng)加入s的點(diǎn) int prim(){ memset(d,0x3f,sizeof d); d[1]=0; int res=0;//最小生成樹的權(quán)值 for(int i=0;i int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||d[t]>d[j])){ t=j; } } if(i) res+=d[t];//先累加在更新 if(i&&d[t]==inf) return inf; st[t]=true; for(int j=1;j<=n;j++) d[j]=min(d[j],g[t][j]); } return res; } int main(){ cin>>n>>m; memset(g,0x3f,sizeof g); while(m--){ int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c); } int t=prim(); if(t==inf) puts("impossible"); else cout< return 0; } kruskal /* kruskal算法求最小生成樹的權(quán)值 */ #include #include #include #include #include using namespace std; const int N=100010,M=200010,inf=0x3f3f3f3f; int n,m; //點(diǎn)邊 int p[N];//并查集 struct Edge{ int a,b,w; bool operator<(const Edge&W) const{ return w } }e[M]; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int kruskal(){ sort(e,e+m); int cnt=0;//積累的邊數(shù) int res=0;//權(quán)值 for(int i=0;i int a=e[i].a,b=e[i].b,w=e[i].w; if(find(a)!=find(b)){ p[find(a)]=find(b); cnt++; res+=w; } } if(cnt else return res; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ p[i]=i; } for(int i=0;i int a,b,w; cin>>a>>b>>w; e[i]={a,b,w}; } int t=kruskal(); if(t==inf) puts("impossible"); else cout< return 0; } 二分圖 染色法判斷二分圖 /* 染色法判斷二分圖,用dfs染色 */ #include #include #include #include #include using namespace std; const int N=100010,M=200010; int n,m; //點(diǎn)邊 int h[N],e[M],ne[M],idx; int color[N];//標(biāo)記每個(gè)點(diǎn)的顏色 void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool dfs(int u,int c){//將u點(diǎn)染成c顏色，并將與u點(diǎn)有關(guān)的也染成相應(yīng)顏色 color[u]=c; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(!color[j]){ if(!dfs(j,3-c)) return false; }else if(color[j]==c){//與u相連的點(diǎn)顏色和u染成一樣不行 return false; } } return true; } int main(){ cin>>n>>m; memset(h,-1,sizeof h); while(m--){ int a,b; cin>>a>>b; add(a,b),add(b,a); } bool flag=true; for(int i=1;i<=n;i++){ if(!color[i]){ if(!dfs(i,1)){ flag=false; break; } } } if(flag) puts("YES"); else puts("NO"); return 0; } 二分圖的最大匹配 /* 染色法判斷二分圖,用dfs染色 */ #include #include #include #include #include using namespace std; const int N=510,M=100010; int n1,n2,m,res; //點(diǎn)邊 int h[N],e[M],ne[M],idx; int match[N];//妹子是否與左邊匹配了，匹配了的話就是左邊的數(shù) bool st[N];//判斷左邊對(duì)妹子是否考慮了 void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool find(int x){//左邊的點(diǎn)x嘗試匹配右邊的妹子 for(int i=h[x];~i;i=ne[i]){ int j=e[i];//j點(diǎn)是右邊的 if(!st[j]){ st[j]=true; if(!match[j]||find(match[j])){ match[j]=x; return true; } } } return false; } int main(){ cin>>n1>>n2>>m; memset(h,-1,sizeof h); while(m--){ int a,b; cin>>a>>b; add(a,b); } for(int i=1;i<=n1;i++){ memset(st,false,sizeof st);//每個(gè)左邊都要初始化一下st數(shù)組 if(find(i)) res++; } cout< return 0; } 數(shù)學(xué)知識(shí) 質(zhì)數(shù) 試除法判斷質(zhì)數(shù) /* 試除法判斷質(zhì)數(shù)。質(zhì)數(shù)大于1，除了1只有本身這兩個(gè)約數(shù) */ #include #include #include #include #include using namespace std; bool is_prime(int x){ if(x<2) return false; for(int i=2;i<=x/i;i++){ if(x%i==0) return false; } return true; } int main(){ int n; cin>>n; while(n--){ int x; cin>>x; if(is_prime(x)) puts("YES"); else puts("NO"); } return 0; } 分解質(zhì)因數(shù) /* 分解質(zhì)因數(shù) */ #include #include #include #include #include using namespace std; void divide(int x){ for(int i=2;i<=x/i;i++){ if(x%i==0){ int res=0; while(x%i==0){ res++; x/=i; } cout< } } if(x>1) cout< } int main(){ int n; cin>>n; while(n--){ int x; cin>>x; divide(x); } return 0; } 質(zhì)數(shù)篩 /* 優(yōu)化的質(zhì)數(shù)篩 若i是primes[j]倍數(shù)，則s=primes[j+1]*i也是primes[j]倍數(shù)， 則s就不是其最小公因數(shù)標(biāo)記的。例如12是i=6時(shí)被標(biāo)記，而不是i=4時(shí)就被標(biāo)記 */ #include #include #include #include #include using namespace std; const int N=10000; int primes[N],cnt; bool st[N]; void get_primes(int x){ for(int i=2;i<=x;i++){ if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]<=x/i;j++){ st[primes[j]*i]=true;//每個(gè)非質(zhì)數(shù)都由其最小公因數(shù)（質(zhì)數(shù)）標(biāo)記 if(i%primes[j]==0) break; } } } int main(){ int n; cin>>n; get_primes(n); for(int i=0;i return 0; } 約數(shù) 試除法求約數(shù) /* 試除法求約數(shù) */ #include #include #include #include #include using namespace std; const int N=10000; int di[N],cnt; void get(int x){ for(int i=1;i<=x/i;i++){ if(x%i==0){ di[cnt++]=i; if(x/i!=i) di[cnt++]=x/i; } } } int main(){ int n; cin>>n; get(n); sort(di,di+cnt); for(int i=0;i cout< return 0; } 約數(shù)個(gè)數(shù) /* 約數(shù)的個(gè)數(shù)，首先分解質(zhì)因數(shù)，如何根據(jù)每個(gè)質(zhì)因數(shù)的個(gè)數(shù)來求約數(shù)的個(gè)數(shù) */ #include #include #include #include #include using namespace std; const int N=10000; int get(int x){ int res=0,ans=1; for(int i=2;i<=x/i;i++){ res=0; if(x%i==0){ while(x%i==0){ x/=i; res++; } ans=(res+1)*ans; } } if(x>1) ans=ans*2; return ans; } int main(){ int n; cin>>n; int s=get(n); cout< return 0; } 用數(shù)據(jù)結(jié)果unordered_map /* 約數(shù)的個(gè)數(shù)，首先分解質(zhì)因數(shù)，如何根據(jù)每個(gè)質(zhì)因數(shù)的個(gè)數(shù)來求約數(shù)的個(gè)數(shù) */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=110,mod=1e9; int main(){ int n; cin>>n; unordered_map while(n--){ int x; cin>>x; for(int i=2;i<=x/i;i++){ if(x%i==0){ while(x%i==0){ x/=i; primes[i]++; } } } if(x>1) primes[x]++; } int res=1; for(auto prime:primes) res=res*(prime.second+1)%mod; cout< return 0; } 約數(shù)之和 /* 求n個(gè)數(shù)的乘積的約數(shù)之和 約數(shù)之和，首先分解質(zhì)因數(shù)，然后根據(jù)每個(gè)質(zhì)因數(shù)和其指數(shù)來求和 18=3^2*2^1; 質(zhì)因數(shù)時(shí)3，2；指數(shù)分別是2，1； 約數(shù)之和=(3^0+3^1+3^2)*(2^0+2^1); 3^0+3^1+3^2=(1+3(1+3)); */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=110,mod=1e9; int main(){ int n; cin>>n; unordered_map while(n--){ int x; cin>>x; for(int i=2;i<=x/i;i++){ if(x%i==0){ while(x%i==0){ x/=i; primes[i]++; } } } if(x>1) primes[x]++; } ll res=1; for(auto prime:primes){ int a=prime.first,b=prime.second; ll t=1; while(b--) t=(1+a*t)%mod;//用公式可以要用費(fèi)馬小定理 res=res*t%mod; } cout< return 0; } 最大共約數(shù) /* 求最大公約數(shù) */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=110,mod=1e9; int gcd(int a,int b){ return b?gcd(b,a%b):a; } int main(){ int n; cin>>n; while(n--){ int a,b; cin>>a>>b; int t=gcd(a,b);//gcd(a,b)=gcd(b,a%b)=......=gcd(x,0)=x;求最大公約數(shù) cout< } return 0; } 歐拉函數(shù) 求歐拉函數(shù) /* 歐拉函數(shù)：數(shù)n，求1~n內(nèi)與n互質(zhì)的數(shù)的個(gè)數(shù)，互質(zhì)是指兩個(gè)數(shù)只有一個(gè)公約數(shù)1； 質(zhì)數(shù)n的歐拉函數(shù)是n-1；因?yàn)樵?~n內(nèi)與n互質(zhì)的數(shù)有n-1個(gè) 公式與n的公因數(shù)有關(guān) */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=110,mod=1e9; int phi(int x){ int res=x;//公式 for(int i=2;i<=x/i;i++){ if(x%i==0){ res=res*(i-1)/i;//公式 while(x%i==0) x/=i; } } if(x>1) res=res*(x-1)/x; return res; } int main(){ int n; cin>>n; while(n--){ int x; cin>>x; cout< } return 0; } 質(zhì)數(shù)篩求多個(gè)數(shù)的歐拉函數(shù)之和 用質(zhì)數(shù)篩的同時(shí)求1~n的里面的所有數(shù)的歐拉函數(shù)，注意1的歐拉函數(shù)是1，要先寫出來 /* 歐拉函數(shù)：數(shù)n，求1~n內(nèi)與n互質(zhì)的數(shù)的個(gè)數(shù)，互質(zhì)是指兩個(gè)數(shù)只有一個(gè)公約數(shù)1； 質(zhì)數(shù)n的歐拉函數(shù)是n-1；因?yàn)樵?~n內(nèi)與n互質(zhì)的數(shù)有n-1個(gè) 公式與n的公因數(shù)有關(guān) */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=1000010,mod=1e9; int primes[N],eul[N],cnt; bool st[N]; void get_eulors(int x){ eul[1]=1; for(int i=2;i<=x;i++){ if(!st[i]){ primes[cnt++]=i; eul[i]=i-1; } for(int j=0;primes[j]<=x/i;j++){ int s=i*primes[j]; st[s]=true; if(i%primes[j]==0){ eul[s]=primes[j]*eul[i]; break; } else{ eul[s]=(primes[j]-1)*eul[i]; } } } } int main(){ int n; cin>>n; get_eulors(n); int res=0; for(int i=1;i<=n;i++) res+=eul[i]; cout< return 0; } 快速冪 快速冪模板 /* 快速冪模板 */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=1000010,mod=1e9; int qmi(int a,int b,int p){ int res=1%p; while(b){ if(b&1) res=res*a%p; a=a*(ll)a%p; b>>=1; } return res; } int main(){ int n; cin>>n; while(n--){ int a,b,p; cin>>a>>b>>p;//求a^b%p cout< } return 0; } 快速冪求逆元（p為質(zhì)數(shù)時(shí)） /* 快速冪求逆元a*a^-1==1(%p)。當(dāng)a，p互質(zhì)時(shí)，存在逆元，那么a，p的最大公約數(shù)是1=gcd(a,p) 當(dāng)p是質(zhì)數(shù)時(shí)，逆元a^-1是a^p-2; 當(dāng)p不是質(zhì)數(shù)時(shí)，可用擴(kuò)展歐幾里得算法，a*x+p*y=1=exgcd(a,p,x,y)可求出x */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=1000010,mod=1e9; ll qmi(int a,int b,int p){ ll res=1%p; while(b){ if(b&1) res=(ll)res*a%p; a=a*(ll)a%p; b>>=1; } return res; } int main(){ int n; cin>>n; while(n--){ int a,p; cin>>a>>p;//求a%p的乘法逆元，a^-1*a==1(%p) 求a^-1. if(a%p) cout< else//a,p不互質(zhì)則逆元不存在 puts("impossible"); } return 0; } 擴(kuò)展歐幾里得算法 模板 /* 擴(kuò)展歐幾里得算法模板 快速冪求逆元a*a^-1==1(%p)。當(dāng)a，p互質(zhì)時(shí)，存在逆元，那么a，p的最大公約數(shù)是1=gcd(a,p) 當(dāng)p是質(zhì)數(shù)時(shí)，逆元a^-1是a^p-2; 當(dāng)p不是質(zhì)數(shù)時(shí)，可用擴(kuò)展歐幾里得算法，a*x+p*y=1=exgcd(a,p,x,y)可求出x，逆元為（x%p+p)%p */ #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=1000010,mod=1e9; int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int x1,y1; int d=exgcd(b,a%b,x1,y1); x=y1; y=x1-(a/b)*y1; return d; } int main(){ int n; cin>>n; while(n--){ int a,b; cin>>a>>b; int x,y; int d=exgcd(a,b,x,y);//求a*x+b*y=gcd(a,b)一對(duì)x，y；結(jié)果不唯一，d是最大公約數(shù)即gcd(a,b) cout< } return 0; } 線性同余方程 #include using namespace std; typedef long long ll; ll exgcd(int a,int b,int &x,int &y){ if(!b){ x=1; y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } int main(){ int n; cin>>n; while(n--){ int a,b,m,x,y; cin>>a>>b>>m; int d=exgcd(a,m,x,y); if(b%d) cout<<"impossible"< else cout<<(long long)x*b/d%m< } } 中國(guó)剩余定理（表達(dá)整數(shù)的奇怪方式） 表達(dá)整數(shù)的奇怪方式 #include #include using namespace std; typedef long long LL; int n; LL exgcd(LL a, LL b, LL &x, LL &y){ if(b == 0){ x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } LL inline mod(LL a, LL b){ return ((a % b) + b) % b; } int main(){ scanf("%d", &n); LL a1, m1; scanf("%lld%lld", &a1, &m1); for(int i = 1; i < n; i++){ LL a2, m2, k1, k2; scanf("%lld%lld", &a2, &m2); LL d = exgcd(a1, -a2, k1, k2); if((m2 - m1) % d){ puts("-1"); return 0; } k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d)); m1 = k1 * a1 + m1; a1 = abs(a1 / d * a2); } printf("%lld\n", m1); return 0; } 高斯消元 解線性方程組 /* 高斯消元四步 1.找到絕對(duì)值最大的一行 2.將該行換到目前最頂端并將其首位變?yōu)? 3.用該行將下面的行首位消為0 4.判斷解條件 */ #include #include #include using namespace std; typedef long long ll; const int N=110; const double eps=1e-8; int n;//在再main函數(shù)中定義n是不一樣的 double a[N][N];//不能開得很大，一般不超過10^8 int gauss(){ int c,r; for(c=0,r=0;c int t=r;//找此列中絕對(duì)值最大的一行 for(int i=r;i