算法基礎課——基礎算法（模板整理）

?快速排序

快速排序

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int s[100000];
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>s[i];}sort(s,s+n);for(int i=0;i<n;i++){cout<<s[i]<<" ";}cout<<endl;return 0;
}

第K個數

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}nth_element(a+1,a+k,a+1+n);cout<<a[k]<<endl;return 0;
}

歸并排序?

歸并排序

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{if(l>=r){return;}int mid=(l+r)>>1;merge_sort(q,l,mid);merge_sort(q,mid+1,r);int k=1,i=l,j=mid+1;while(i<=mid&&j<=r){if(q[i]<=q[j]){tmp[k++]=q[i++];}else{tmp[k++]=q[j++];}}while(i<=mid){tmp[k++]=q[i++];}while(j<=r){tmp[k++]=q[j++];}for(int i=l,j=1;i<=r;i++,j++){q[i]=tmp[j];}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&q[i]);}merge_sort(q,1,n);for(int i=1;i<=n;i++){printf("%d ",q[i]);}return 0;
}

逆序對的數量

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int q[N],tmp[N];
ll merge_sort(int l,int r)
{if(l>=r){return 0;}int mid = (l+r)>>1;ll res=merge_sort(l,mid)+merge_sort(mid+1,r);//歸并的過程int k=1,i=l,j=mid+1;while(i<=mid&&j<=r){if(q[i]<=q[j]){tmp[k++]=q[i++];}else{tmp[k++]=q[j++];res+=(mid-i+1);}}//掃尾while(i<=mid){tmp[k++]=q[i++];}while(j<=r){tmp[k++]=q[j++];}//物歸原主for(int i=l,j=1;i<=r;i++,j++){q[i]=tmp[j];}return res;
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>q[i];}cout<<merge_sort(1,n)<<endl;return 0;
}

二分?

數的范圍

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){cin>>q[i];}while(m--){int x;cin>>x;int l=0,r=n-1;while(l<r){int mid=l+r>>1;if(q[mid]>=x){r=mid;}else l=mid+1;}if(q[l]!=x){cout<<"-1 -1"<<endl;}else{cout<<l<<" ";l=0;r=n-1;while(l<r){int mid=l+r+1>>1;if(q[mid]<=x){l=mid;}else r=mid-1;}cout<<l<<endl;}}return 0;
}

數的三次方根

#include <iostream>
using namespace std;
int main()
{double n;cin>>n;double l=-10000,r=10000;while(r-l>1e-8){double mid = (l+r)/2;if(mid*mid*mid>=n){r=mid;}else l=mid;}printf("%.6lf\n",l);return 0;
}

高精度

?高精度加法

Python一行就可以解決

print(int(input())+int(input()))
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B)
{vector<int>C;int t=0;for(int i=0;i<A.size()||i<B.size();i++){if(i<A.size()){t+=A[i];}if(i<B.size()){t+=B[i];}C.push_back(t%10);t/=10;}if(t){C.push_back(t);}return C;
}
int main()
{string a,b;cin>>a>>b;vector<int>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<<C[i];}return 0;
}

高精度減法

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//判斷是否有A>=B
bool cmp(vector<int> &A,vector<int> &B)
{if(A.size()!=B.size()){return A.size()>B.size();}for(int i=A.size()-1;i>=0;i--){if(A[i]!=B[i]){return A[i]>B[i];}}return true;
}
//C=A-B
vector<int> sub(vector<int> &A,vector<int> &B)
{vector<int>C;int t=0;for(int i=0;i<A.size();i++){t=A[i]-t;if(i<B.size()){t-=B[i];}C.push_back((t+10)%10);if(t<0){t=1;}else t=0;}while(C.size()>1&&C.back()==0){C.pop_back();}return C;
}
int main()
{string a,b;cin>>a>>b;vector<int>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');}if(cmp(A,B)){auto C = sub(A,B);for(int i=C.size()-1;i>=0;i--){cout<<C[i];}}else{auto C = sub(B,A);cout<<"-";for(int i=C.size()-1;i>=0;i--){cout<<C[i];}}return 0;
}

高精度乘法

#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A, int b)
{vector<int>C;int t = 0;for (int i = 0; i < A.size() || t; i++){if (i < A.size()){t += A[i] * b;}C.push_back(t % 10);t /= 10;}while(C.size()>1&&C.back()==0){C.pop_back();}return C;
}
int main()
{string a;int b;cin >> a >> b;vector<int>A;for (int i = a.size() - 1; i >= 0; i--){A.push_back(a[i] - '0');}auto C = mul(A, b);for (int i = C.size() - 1; i >= 0; i--){cout << C[i];}return 0;
}

高精度除法

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> div(vector<int>& A, int b,int &r)
{vector<int>C;r=0;for (int i = A.size()-1; i >= 0; i--){r = r * 10 + A[i];C.push_back(r/b);r%=b;}reverse(C.begin(),C.end());while(C.size()>1&&C.back()==0){C.pop_back();}return C;
}
int main()
{string a;int b;cin >> a >> b;vector<int>A;for (int i = a.size() - 1; i >= 0; i--){A.push_back(a[i] - '0');}int r;auto C = div(A, b,r);for (int i = C.size() - 1; i >= 0; i--){cout << C[i];}cout<<endl<<r<<endl;return 0;
}

前綴和與差分

前綴和

#include <iostream>
using namespace std;
const int N = 100005;
int a[N],s[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}while(m--){int l,r;cin>>l>>r;cout<<s[r]-s[l-1]<<endl;}return 0;
}

子矩陣的和

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main() 
{int n, m, q;cin >> n >> m >> q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){scanf("%d", &a[i][j]);s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; // 求前綴和}while (q--) {int x1,y1,x2,y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);// 算子矩陣的和printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); }return 0;
}

差分

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{b[l]+=c;b[r+1]-=c;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){insert(i,i,a[i]);}while(m--){int l,r,c;cin>>l>>r>>c;insert(l,r,c);}for(int i=1;i<=n;i++){b[i]+=b[i-1];}for(int i=1;i<=n;i++){cout<<b[i]<<" ";}return 0;
}

差分矩陣

#include <iostream>
using namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{b[x1][y1]+=c;b[x2+1][y1]-=c;b[x1][y2+1]-=c;b[x2+1][y2+1]+=c;
}
int main()
{cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){insert(i,j,i,j,a[i][j]);}}while(q--){int x1,y1,x2,y2,c;cin>>x1>>y1>>x2>>y2>>c;insert(x1,y1,x2,y2,c);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<b[i][j]<<" ";}cout<<endl;}return 0;
}

雙指針算法

最長連續不重復子序列

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N],s[N];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int res=0;for(int i=1,j=1;i<=n;i++){s[a[i]]++;while(s[a[i]]>1){s[a[j]]--;j++;}res=max(res,i-j+1);}cout<<res<<endl;return 0;
}

數組元素的目標和

#include <iostream>
using namespace std;
const int N = 100005;
int n,m,x;
int a[N],b[N];
int main()
{cin>>n>>m>>x;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}for(int i=1,j=m;i<=n;i++){while(j>=1&&a[i]+b[j]>x) j--;if(a[i]+b[j]==x){cout<<i-1<<" "<<j-1<<endl;break;}}return 0;
}

判斷子序列

#include <iostream>
using namespace std;
const int N = 100005;
int n,m;
int a[N],b[N];
int main()
{cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<m;i++){cin>>b[i];}int i=0,j=0;while(i<n&&j<m){if(a[i]==b[j])i++;j++;}if(i==n){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return 0;
}

位運算

二進制中1的個數

#include <iostream>
using namespace std;
int lowbit(int x)
{return x & -x;
}
int main()
{int n;cin>>n;while(n--){int x;cin>>x;int res=0;while(x){x-=lowbit(x);res++;}cout<<res<<" ";}return 0;
}

離散化

區間和

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010; //n次插入和m次查詢相關數據量的上界
int n, m;
int a[N];//存儲坐標插入的值
int s[N];//存儲數組a的前綴和
vector<int> alls;  //存儲（所有與插入和查詢有關的）坐標
vector<pair<int, int>> add, query; //存儲插入和詢問操作的數據int find(int x) 
{ //返回的是輸入的坐標的離散化下標int l = 0, r = alls.size() - 1;while (l < r) {int mid = l + r >> 1;if (alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1;
}int main() 
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {int x, c;scanf("%d%d", &x, &c);add.push_back({x, c});alls.push_back(x);}for (int i = 1; i <= m; i++) {int l , r;scanf("%d%d", &l, &r);query.push_back({l, r});alls.push_back(l);alls.push_back(r);}//排序，去重sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());//執行前n次插入操作for (auto item : add) {int x = find(item.first);a[x] += item.second;}//前綴和for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];//處理后m次詢問操作for (auto item : query) {int l = find(item.first);int r = find(item.second);printf("%d\n", s[r] - s[l-1]);}return 0;
}

區間和并

區間和并

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int>pii;
const int N = 100010;
int n;
vector<pii>segs;
void merge(vector<pii>&segs)
{vector<pii>res;sort(segs.begin(),segs.end());int st=-2e9,ed=-2e9;for(auto seg:segs){if(ed<seg.first){if(ed!=-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});cout<<res.size()<<endl;
}
int main()
{cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;segs.push_back({l,r});}merge(segs);return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/43619.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/43619.shtml
英文地址，請注明出處：http://en.pswp.cn/news/43619.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

4.物聯網LWIP之C/S編程

4.物聯網LWIP之C/S編程

LWIP配置 服務器端實現 客戶端實現 錯誤分析 一。LWIP配置&#xff08;FREERTOS配置&#xff0c;ETH配置&#xff0c;LWIP配置&#xff09; 1.FREERTOS配置 為什么要修改定時源為Tim1&#xff1f;不用systick&#xff1f; 原因&#xff1a;HAL庫與FREERTOS都需要使用systi…
閱讀更多...
leetcode做題筆記89. 格雷編碼

leetcode做題筆記89. 格雷編碼

n 位格雷碼序列 是一個由 2n 個整數組成的序列&#xff0c;其中&#xff1a; 每個整數都在范圍 [0, 2n - 1] 內&#xff08;含 0 和 2n - 1&#xff09;第一個整數是 0一個整數在序列中出現 不超過一次每對 相鄰 整數的二進制表示 恰好一位不同 &#xff0c;且第一個 和 最后一…
閱讀更多...
C語言好題解析（三）

C語言好題解析（三）

目錄 選擇題一選擇題二選擇題三選擇題四編程題一編程題二 選擇題一 以下程序段的輸出結果是&#xff08;&#xff09;#include<stdio.h> int main() { char s[] "\\123456\123456\t"; printf("%d\n", strlen(s)); return 0; }A: 12 B: 13 …
閱讀更多...
Lnton羚通關于【PyTorch】教程：torchvision 目標檢測微調

Lnton羚通關于【PyTorch】教程：torchvision 目標檢測微調

torchvision 目標檢測微調 本教程將使用Penn-Fudan Database for Pedestrian Detection and Segmentation 微調 預訓練的Mask R-CNN 模型。 它包含 170 張圖片&#xff0c;345 個行人實例。 定義數據集 用于訓練目標檢測、實例分割和人物關鍵點檢測的參考腳本允許輕松支持添加…
閱讀更多...
前端-輪詢

前端-輪詢

一、輪詢定義 輪詢是指在一定的時間間隔內&#xff0c;定時向服務器發送請求&#xff0c;獲取最新數據的過程。輪詢通常用于從服務器獲取實時更新的數據。 二、輪詢和長輪詢區別 輪詢是在固定的時間間隔內向服務器發送請求&#xff0c;即使服務器沒有數據更新也會繼續發送請求…
閱讀更多...
暴力模擬入門+簡單：零件組裝、塔子的簽到題、塔子哥考試、平均像素值、換座位

暴力模擬入門+簡單：零件組裝、塔子的簽到題、塔子哥考試、平均像素值、換座位

暴力模擬入門 P1038 小紅書-2022.9.23-零件組裝 #include <bits/stdc.h> #include <cstdint> using namespace std;typedef long long LL; const int N 100001; int num[4]; LL d; vector<vector<LL>> v(4, vector<LL>(N));int main() {for(in…
閱讀更多...
解決Pycharm的Settings中Project不見了也無法選擇Python Interpreter的方法

解決Pycharm的Settings中Project不見了也無法選擇Python Interpreter的方法

目錄 一、問題如下二、解決方法 一、問題如下 突然打開項目沒有python解釋器&#xff0c;也無法重新配置python Interpreter&#xff0c;而且整個文件夾是黃色高亮的形式&#xff0c;如下顯示&#xff0c;而且重新安裝了pycharm也沒用甚至說打開File–>Setting–>Projec…
閱讀更多...
日常BUG——普通頁面跳轉tabbar頁面報錯

日常BUG——普通頁面跳轉tabbar頁面報錯

&#x1f61c;作 者&#xff1a;是江迪呀??本文關鍵詞&#xff1a;日常BUG、BUG、問題分析??每日 一言 &#xff1a;存在錯誤說明你在進步&#xff01; 一、問題描述 微信小程序頁面跳轉的時候出現下面的問題&#xff1a; wx.redirectTo({url: /pages/index/i…
閱讀更多...
Linux學習之基本指令二

Linux學習之基本指令二

-----緊接上文 在了解cat指令之前&#xff0c;我們首先要了解到Linux下一切皆文件&#xff0c;在學習c語言時我們就已經了解到了 對文件輸入以及讀入的操作&#xff08;向顯示器打印&#xff0c;從鍵盤讀取數據&#xff09;&#xff0c;對于Linux下文件的操作&#xff0c;也是…
閱讀更多...
算法與數據結構（二十三）動態規劃設計：最長遞增子序列

算法與數據結構（二十三）動態規劃設計：最長遞增子序列

注&#xff1a;此文只在個人總結 labuladong 動態規劃框架&#xff0c;僅限于學習交流&#xff0c;版權歸原作者所有&#xff1b; 也許有讀者看了前文 動態規劃詳解&#xff0c;學會了動態規劃的套路&#xff1a;找到了問題的「狀態」&#xff0c;明確了 dp 數組/函數的含義&a…
閱讀更多...
js簡介以及在html中的2種使用方式（hello world）

js簡介以及在html中的2種使用方式（hello world）

簡介 javascript &#xff1a;是一個跨平臺的腳本語言&#xff1b;是一種輕量級的編程語言。 JavaScript 是 Web 的編程語言。所有現代的 HTML 頁面都使用 JavaScript。 HTML&#xff1a; 結構 css&#xff1a; 表現 JS&#xff1a; 行為 HTMLCSS 只能稱之為靜態網頁&#xff0…
閱讀更多...
Rust交叉編譯簡述 —— Arm

Rust交叉編譯簡述 —— Arm

使用系統&#xff1a;WSL2 —— Kali(Microsoft Store) 命令列表 rustup target list # 當前官方支持的構建目標架構列表 rustup target add aarch64-unknown-linux-gnu # 添加目標架構sudo apt-get install gcc-13-aarch64-linux-gnu gcc-13-aarch64-linux-gnu # 下載目標工具…
閱讀更多...
github以及上傳代碼處理

github以及上傳代碼處理

最近在github上傳代碼的時候出現了&#xff1a; /video_parser# git push -u origin main Username for https://github.com: gtnyxxx Password for https://gtny2010github.com: remote: Support for password authentication was removed on August 13, 2021. remote: Plea…
閱讀更多...
ROS局部路徑規劃器插件teb_local_planner流程梳理（上）

ROS局部路徑規劃器插件teb_local_planner流程梳理（上）

在我之前的文章《ROS導航包Navigation中的 Movebase節點路徑規劃相關流程梳理》中已經介紹過Move_base節點調用局部路徑規劃器插件的接口函數是computeVelocityCommands&#xff0c;接下來&#xff0c;我們就從這個函數入手梳理一下teb_local_planner功能包的工作流程。 ☆注&a…
閱讀更多...
推薦一個繪圖平臺（可替代Visio）

推薦一個繪圖平臺（可替代Visio）

不廢話&#xff0c;簡易記網址&#xff1a; draw.io 網站會重定向到&#xff1a;https://app.diagrams.net/
閱讀更多...
編程語言中的++和--運算符介紹

編程語言中的++和--運算符介紹

編程語言中的和--運算符介紹 和--是編程語言&#xff08;C/C、JavaScript、Java&#xff09;中的自增&#xff08;加一&#xff09;和自減&#xff08;減一&#xff09;運算符。它們可以應用于變量&#xff0c;并且具有前綴和后綴兩種形式。 前綴形式&#xff1a; variable&…
閱讀更多...
Databend 開源周報第 106 期

Databend 開源周報第 106 期

Databend 是一款現代云數倉。專為彈性和高效設計&#xff0c;為您的大規模分析需求保駕護航。自由且開源。即刻體驗云服務&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新進展&#xff0c;遇到更貼近你心意的 Databend 。 數據脫敏 Data…
閱讀更多...
云原生 AI 工程化實踐之 FasterTransformer 加速 LLM 推理

云原生 AI 工程化實踐之 FasterTransformer 加速 LLM 推理

作者&#xff1a;顏廷帥&#xff08;瀚廷&#xff09; 01 背景 OpenAI 在 3 月 15 日發布了備受矚目的 GPT4&#xff0c;它在司法考試和程序編程領域的驚人表現讓大家對大語言模型的熱情達到了頂點。人們紛紛議論我們是否已經跨入通用人工智能的時代。與此同時&#xff0c;基…
閱讀更多...
ISBN號碼(NOIP2008 普及組第一題)

ISBN號碼(NOIP2008 普及組第一題)

ISBN號碼 說明 每一本正式出版的圖書都有一個ISBN號碼與之對應&#xff0c;ISBN碼包括9位數字、1位識別碼和3位分隔符&#xff0c;其規定格式如“x-xxx-xxxxx-x”&#xff0c;其中符號“-”就是分隔符&#xff08;鍵盤上的減號&#xff09;&#xff0c;最后一位是識別碼&#x…
閱讀更多...
CCF C3 走進百度：大模型與可持續生態發展

CCF C3 走進百度：大模型與可持續生態發展

2023年8月10日&#xff0c;由CCF CTO Club發起的第22期C活動在百度北京總部進行&#xff0c;以“AI大語言模型技術與生態發展”主題&#xff0c;50余位企業界、學界專家、研究人員就此進行深入探討。 CCF C走進百度 本次活動&#xff0c;CCF秘書長唐衛清與百度集團副總裁、深…
閱讀更多...
最新文章

Copyright @ 2022~2023