高精度加法
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int A[N],B[N],C[N],al,bl,cl;
void add(int A[],int B[],int C[])
{for(int i=cl-1;~i;i--){C[cl]=A[i]+B[i];C[cl+1]=C[cl]/10;C[cl]%=10;}if(C[cl])cl++;
}
int main()
{string a,b;cin>>a>>b;al=a.size(),bl=b.size(),cl=max(al,bl);for(int i=al-1;~i;i--)A[i]=a[i]-'0';for(int i=bl-1;~i;i--)B[i]=b[i]-'0';add(A,B,C);for(int i=cl-1;~i;i--)cout<<C[i];return 0;
}
高精度減法
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int A[N],B[N],C[N];
int al,bl,cl;
//Eg:數是1234存儲在數組中是倒敘存儲的
bool cmp(int A[],int B[])
{if(al!=bl)return al>bl;//如果bl>al結果為負數 for(int i=al-1;~i;i--)//如果長度相同一個一個比較 if(A[i]!=B[i]) return A[i]>B[i];return true;//避免結果位-0
}
void sub(int A[],int B[],int C[])
{for(int i=0;i<cl;i++){if(A[i]<B[i])A[i+1]--,A[i]+=10;//位數不夠想前面借一位 C[i]=A[i]-B[i];//存儲差 }while(cl&&C[cl]==0)cl--;//處理前導0,當前cl!=0且C[cl]==0
}
int main()
{string a,b;cin>>a>>b;al=a.size(),bl=b.size(),cl=max(al,bl);for(int i=al-1;~i;i--)A[al-1-i]=a[i]-'0';for(int i=bl-1;~i;i--)B[bl-1-i]=b[i]-'0';if(!cmp(A,B))swap(A,B),cout<<'-';//當A<B時將2個數交換并且打印負數 sub(A,B,C);for(int i=cl;~i;i--)cout<<C[i];return 0;
}
高進度乘法
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int al,bl,cl;
int A[N],B[N],C[N];
void mul(int A[],int B[],int C[])
{for(int i=0;i<bl;i++){for(int j=0;j<al;j++){C[i+j]+=A[j]*B[i];//累加乘積 C[i+j+1]+=C[i+j]/10;//進位C[i+j]%=10; //存于 }}while(cl&&C[cl]==0)cl--; //處理前導0
}
int main()
{string a,b;cin>>a>>b;al=a.size(),bl=b.size(),cl=al+bl;for(int i=al-1;~i;i--)A[al-1-i]=a[i]-'0';for(int i=bl-1;~i;i--)B[bl-1-i]=b[i]-'0';mul(A,B,C); for(int i=cl;~i;i--)cout<<C[i];return 0;
}
高精度除法
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int al,b,cl;
int A[N],B[N],C[N];
void div(int A[],int b,int C[])
{long long r=0;for(int i=al-1;~i;i--){r=r*10+A[i];//被除數 C[al-1-i]=r/b;//存商 r%=b;//除數 }reverse(C,C+cl);while(cl&&C[cl]==0)cl--;//處理多余0
}
int main()
{string a;cin>>a>>b;cl=al=a.size();for(int i=al-1;~i;i--)A[al-1-i]=a[i]-'0';div(A,b,C);for(int i=cl;~i;i--)cout<<C[i]; return 0;
}
簡單的前綴和模板
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int a[N],s[N],n,c;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i]; }cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;cout<<s[r]-s[l-1]<<endl;}
}
選擇排序
//選擇排序就是從第一個下標的數開始
//以第一個數為基準向后進行比較選出最小的
//然后換下表進行排序
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,ans[N];
void selection(int a[N],int k)
{for(int i=0;i<k-1;i++){int minindex=i;//從初始的下標進行比較 for(int j=i+1;j<k;j++)if(a[j]<a[minindex])minindex=j;//比對到大小進行交換 if(minindex!=i)swap(a[i],a[minindex]);}
}
int main()
{cin>>n;for(int i=0;i<n;i++)cin>>ans[i];selection(ans,n);for(int i=0;i<n;i++)cout<<ans[i]<<" ";return 0;
}
冒泡排序
//冒泡排序每次從頭到尾比較一次就會確定最后面的的一個元素的位置
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,ans[N];
void bubble(int a[N],int k)
{for(int i=0;i<n-1;i++){bool flag=false;for(int j=0;j<n-i-1;j++)//防止越界 {if(ans[j]>ans[j+1]){swap(ans[j],ans[j+1]);flag=true;}if(!flag)break;//當數沒有進行交換就說明后面已經排序過來不需要在進行排序了直接退出 }}
}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>ans[i];}bubble(ans,n);for(int i=0;i<n;i++)cout<<ans[i]<<" ";
}
插入排序
//插入排序用當前一個數與前一個數進行比較
//如果當前的數任然比前一個數要小任然不斷往前放
//數組中第一個數認為他已經有序
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int ans[N],n;
void insertion(int a[N],int k)
{for(int i=1;i<n;i++)//第一個數認為已經有序 {int key=a[i];int j=i-1;while(j>=0&&a[j]>key)//如果當前的數大于前一個數 {a[j+1]=a[j];//進行交換 j--;//將當數與前一個數進行比較 } a[j+1]=key;}
}
int main()
{cin>>n;for(int i=0;i<n;i++)cin>>ans[i];insertion(ans,n);for(int i=0;i<n;i++)cout<<ans[i]<<" ";return 0;
}
二分查找
模板
//二分查找模板
//模板一
// 在單調遞增序列a中查找>=x的數中最小的一個(即x或x的后繼)
while(l<r)
{int mid=l+r>>l;if(check(mid)) r=mid;elsel=mind+1;
}
//模板二
// 在單調遞增序列a中查找<=x的數中最大的一個(即x或x的前驅)
while(l<r)
{int mid=l+r>>l;if(check(mid)) l=mid;elser=mid-1
}
//浮點二分
while(r-l<1e-5)//需要一個精確度保障
{double mind=(l+r)/2;if(check(mid)) l=mid;elser=mid;
}
題目
/*題目描述
牛牛同學拿到了 2 組數字,請你編程幫他找出,第 2 組中的哪些數,在第 1 組數中出現了,從小到大輸出所有滿足條件的數。比如:
第 1 組數有:8 7 9 8 2 6 3
第 2 組數有:9 6 8 3 3 2 1 0
那么應該輸出:2 3 3 6 8 9
輸入格式
第一行兩個整數 n 和 m,分別代表 2 組數的數量
第二行 n 個正整數
第三行 m 個正整數
對于 60% 的數據 1≤n,m≤1000,每個數 <=210^9
對于 100% 的數據 1≤n,m≤100000,每個數 <=210^9
輸入樣例
7 7
8 7 9 8 2 6 3
9 6 8 3 3 2 10
輸出樣例
2 3 3 6 8 9*/
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,a[N],b[N],ans;
int search(int x)
{int l=0,r=n+1;while(l+1!=r){int mid=(l+r)>>1;if(a[mid>x])r=mid;else if(a[mid]<x)l=mid;elsereturn 1;}return 0;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int j=1;j<=m;j++){cin>>b[j];}sort(a+1,a+n+1);sort(b+1,b+m+1);for(int i=1;i<=m;i++){if(search(b[i]))cout<<b[i]<<" ";}return 0;
}
/*題目描述
請在一個有序遞增數組中(不存在相同元素),
采用二分查找,找出值 x 的位置,
如果 x 在數組中不存在,請輸出 -1!
輸入格式:
第一行,一個整數 n,代表數組元素個數(n≤10 6)。
第二行,n 個數,代表數組的 n 個遞增元素(1≤數組元素值≤10 8)。
第三行,一個整數 x,代表要查找的數(0≤x≤10 8)。
輸出格式:
x 在數組中的位置,或者 -1。
輸入樣例
10
1 3 5 8 9 10 13 19 24 35
24
輸出樣例
9 */
#include <bits/stdc++.h>
using namespace std;
const int N=1000001;
int n,a[N],end,ans;
int search(int x)
{int l=0,r=n+1;while(l+1!=r){int mid=(l+r)>>1;//想當于(l+r)/2 if(a[mid]>x)r=mid;//取中間的數大 ,向左邊縮小 else if(a[mid]<x)l=mid;else //取中間的數小 ,向右邊縮小 return mid; }
}
int main()
{cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];}cin>>end;ans=search(end);cout<<ans;return 0;
}
01背包-P1048_luo
//dp[i][j]:1-i物品自由選擇,容量不超過j的情況 下的最大價值
//i:第多少件商品;j:商品的體積;dp[i][j]:商品的價值
//將其想像為一個二維表
//體積cost[i] 價值val[i]
// 不選第i個:dp[i-1][j]
//選擇i個物品:
#include<bits/stdc++.h>
using namespace std;int vol[101],value[101],dp[101][1001];int main(){//t:表示時間,m:表示藥品的個數 int t,m;cin>>t>>m;for(int i=1;i<=m;i++)cin>>vol[i]>>value[i];for(int i=1;i<=m;i++){for(int j=0;j<=t;j++){if(vol[i]>j)//當前物品的體積大于背包的容量dp[i][j]=dp[i-1][j];//當放不進去是放上一行的數據else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-vol[i]]+value[i]);//放的進去求這一行和上一行的最大值 }}}cout<<dp[m][t];return 0;}
bfs模板題走迷宮
//bfs模板題
//起點初始化放進隊列中--->如果隊列不為空一直進行擴展
//彈出隊列的點判斷是否為終點--->不為終點進行4各方向擴張
//將擴展的點放入到隊列中,將隊首元素進行彈出
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,a[N][N],v[N][N];
int startx,starty,p,q;
struct point{int x;int y;int step;
};
queue<point> r;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main()
{//輸入 cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];cin>>startx>>starty>>p>>q;//BFSpoint s;s.x=startx;s.y=starty;s.step=0;r.push(s);//將起始點入隊 v[startx][starty]==1;//將擴展過的點都標記 int flag=0;while(!r.empty()){int x=r.front().x,y=r.front().y;//找到終點進行打印步數 if(x==p&&y==q){flag=1;cout<<r.front().step;break;}for(int k=0;k<=3;k++){int tx,ty;tx=x+dx[k];ty=y+dy[k];//當前點沒有障礙物,沒有經過 if(a[tx][ty]==1&&v[tx][ty]==0){point temp;temp.x=tx; temp.y=ty;temp.step=r.front().step+1;r.push(temp);//將新擴展的點放入到隊列 v[tx][ty]=1;//將訪問過的點進行標記 }}r.pop();//擴展完的元素需要將隊首進行出隊 } if(flag==0)cout<<"-1";return 0;
}
/*5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3*/
dfs模板題做迷宮
//dfs模板題做迷宮
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int m,n,startx,starty,p,q,minx=99999999;
int a[N][N];//1:表示空地;2:表示障礙物
int v[N][N];//1:表示訪問;2:表示未訪問 //先判斷是否到達終點,在向4個方向進行展開
//展開時要標記此點已經進過之后要回溯要清除這個點
void dfs(int x,int y,int step)
{if(x==p&&y==q){if(step<minx)minx=step;return; } //順時針試探//右if(a[x+1][y]==1&&v[x+1][y]==0){v[x+1][y]=1;dfs(x+1,y,step+1);v[x+1][y]=0;}//下if(a[x][y+1]==1&&v[x][y+1]==0){v[x][y+1]=1;dfs(x,y+1,step+1);v[x][y+1]=0;}//左if(a[x-1][y]==1&&v[x-1][y]==0){v[x-1][y]=1;dfs(x-1,y,step+1);v[x-1][y]=0;}//上if(a[x][y-1]==1&&v[x][y-1]==0){v[x][y-1]=1;dfs(x,y-1,step+1);v[x][y-1]=0;}return;
}
int main()
{cin>>m>>n;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)cin>>a[i][j];cin>>startx>>starty>>p>>q;dfs(startx,starty,0);cout<<minx;return 0;
}
/*5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3*/
dfs全排列模板題
#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//數字是否被用過
int n;
void dfs(int u)
{if(u > n)//數字填完了,輸出{for(int i = 1; i <= n; i++)//輸出方案cout << path[i] << " ";cout << endl;}for(int i = 1; i <= n; i++)//空位上可以選擇的數字為:1 ~ n{if(!state[i])//如果數字 i 沒有被用過{path[u] = i;//放入空位state[i] = 1;//數字被用,修改狀態dfs(u + 1);//填下一個位state[i] = 0;//回溯,取出 i}}
}int main()
{cin >> n;dfs(1);
}
vector、queue、typedef的使用
//vector、queue、typedef的使用
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
typedef vector<vector<int>> VVI;
typedef vector<PII> V;
int main()
{vector<int> v;v.push_back(8);//尾部插入一個元素v.push_back(9);v.push_back(3);v.push_back(5); v.pop_back();//刪除隊尾元素int len=v.size();//返回元素個數cout<<len<<endl;for(int i=0;i<=len-1;i++)cout<<v[i]<<" ";sort(v.begin(),v.end());cout<<endl;for(int i=0;i<=len-1;i++)cout<<v[i]<<" ";cout<<endl;cout<<"-----------------------------------"<<endl;queue<int> q;q.push(48);q.push(8);q.push(1);q.push(92);//隊尾插入元素int x=q.front();//訪問隊首元素cout<<x<<endl;q.pop();//刪除隊首元素int chang=q.size();//反水元素的個數cout<<chang<<endl;int flage=q.empty(); cout<<flage<<endl;while(!q.empty()){cout<<q.front()<<" ";q.pop();}cout<<endl;int flag=q.empty(); cout<<flag<<endl;cout<<"-----------------------------------"<<endl;PII p1={1,2};cout<<p1.first<<" "<<p1.second<<endl;V v1={{1,2},{8,9}};cout<<v1[0].first<<" "<<v1[0].second<<endl;cout<<v1[1].first<<" "<<v1[1].second<<endl;cout<<"-----------------------------------"<<endl;int ou[]={1,9,58,3,75,6,2,4,8,2,3,65};sort(ou,ou+12,greater<int>());for(int i=0;i<12;i++)cout<<ou[i]<<" "<<endl;
}
最大公約數和最小公倍數
//輸入兩個正整數 m 和 n,求其最大公約數和最小公倍數。
#include <iostream>
using namespace std;int gcd(int a,int b)
{while(b != 0){int c = a % b;a = b;b = c;}return a;
}int main()
{int n,m;cin >> n >> m;cout << gcd(n,m) << " " << n * m / gcd(n,m);return 0;
}
質數的個數
//給定一個正整數 n,請你求出 1到n中質數的個數。
//設置2層循環在外面的循環時遍歷數的
//里面的循環是用來將當前i的倍數進行標記的;
#include <iostream>
#include <cstring>
using namespace std;
int n;
int st[1001000], primes[1001000], p[1001000];
int cnt;void v(int n){memset(st, false, sizeof st);st[0] = true;st[1] = true;for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i;for(int j= i; j <= n; j+=i){st[j] = true;}}
}
int main(){cin >> n;v(n);cout << cnt;return 0;
}
質數的判斷
#include <bits/stdc++.h>
using namespace std;
int check(int x)
{for(int i=2;i<=x/i;i++)if(x%i==0)return 1;
return 0;
}
int main()
{int n;//輸入你要判斷質數的個數 cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;if(x==1)cout<<"no"<<endl;else if(check(x))cout<<"no"<<endl;elsecout<<"yes"<<endl;}return 0;
}