Acwing算法模板(自己用)
Acwing算法模板（⾃⼰⽤）题⽬均可以在acwing中搜索得到
⽬录
基础算法
⼆分
整数⼆分模板
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int a[maxn];
int main(){
int n,q; cin>>n>>q;
for(int i=0;i<n;i++) cin>>a[i];
while(q--){
int x; cin>>x;
int l=0,r=n-1;
while(l<r){
int mid = l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x)cout<<"-1 -1\n";
else{
cout<<l<<" ";
l=0,r=n-1;
while(l<r){
int mid = l+r+1>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
//                cout<<mid<<" "<<l<<" "<<r<<endl;
}
cout<<l<<endl;
}
}
return 0;
}
实数⼆分模板
//求根号
#include<bits/stdc++.h>
using namespace std;
int main(){
double x;  cin>>x;
double l=0,r=x;
while(r-l>1e-6){
double mid = (l+r)/2;
if(mid*mid>=x) r=mid;
else l=mid;
}
cout<<l;
return 0;
}
求三次⽅
#include<bits/stdc++.h>
using namespace std;
int main(){
double n;  cin>>n;
/
/确定边界
double l=-1000,r=1000;
while(r-l>1e-8){
double mid=(l+r)/2;
if(mid*mid*mid>=n) r=mid;
else l=mid;
}
printf("%.6lf",l);
return 0;
}
⾼精度
⾼精度加法
#include<bits/stdc++.h>
using namespace std;
vector<int> a,b;
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 s1,s2;  cin>>s1>>s2;
for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');    for(int i=s2.size()-1;i>=0;i--) b.push_back(s2[i]-'0');    auto c = add(a,b);
for(int i=c.size()-1;i>=0;i--) cout<<c[i];
return 0;
}
⾼精度减法
#include<bits/stdc++.h>
using namespace std;
vector<int> 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;
}
vector<int> sub(vector<int> &a,vector<int> &b){
vector<int> c;
for(int i=0,t=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 s1,s2;  cin>>s1>>s2;
for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');
for(int i=s2.size()-1;i>=0;i--) b.push_back(s2[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<bits/stdc++.h>
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;
}
//去除前导 0
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
int main(){
string s1;  cin>>s1;
int b;  cin>>b;
vector<int> a;
for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');
auto c = mul(a,b);
for(int i=c.size()-1;i>=0;i--) cout<<c[i];
return 0;
}
⾼精度除法
#include<bits/stdc++.h>
using namespace std;
vector<int> div(vector<int> &a,int b,int &r){
vector<int> c;
for(int i=a.size()-1;i>=0;i--){//对A从最⾼位开始处理
r=r*10+a[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
c.push_back(r/b);//所得即为商在这⼀位的数字
r%=b;
}
//由于在除法运算中，⾼位到低位运算，因此C的前导零都在vector的前⾯⽽不是尾部
//，vector只有删除最后⼀个数字pop_back是常数复杂度，⽽对于删除第⼀位没有相应的库函数可以使⽤    //    ⽽且删除第⼀位，其余位也要前移，
//因此我们将C翻转，这样0就位于数组尾部，可以使⽤pop函数删除前导0
reverse(c.begin(),c.end());
while(c.size()>1&&c.back()==0) c.pop_back();
return c;
}
int main(){
string s1;  cin>>s1;
int b;  cin>>b;
vector<int> a;
for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');
int r=0;
auto c = div(a,b,r);
for(int i=c.size()-1;i>=0;i--) cout<<c[i];
cout<<endl<<r;
return 0;
}
前缀和
⼀维的
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
int n,m;    scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int t;  scanf("%d",&t);
a[i]=a[i-1]+t;
}
while(m--){
int l,r;    scanf("%d%d",&l,&r);
printf("%d",a[r]-a[l-1]);
if(m!=0) printf("\n");
}
return 0;
}
⼆维的
eg: ⼦矩阵的和
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int maxn = 1010;
int a[maxn][maxn],s[maxn][maxn];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
s[i][j]=s[i-1][j]+s[i][j-1]-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[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);    }
return 0;
}
差分
⼀维的
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int a[maxn],b[maxn];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
//牢记 a数组是 b数组的前缀和
while(m--){
int l,r,c;  cin>>l>>r>>c;
b[l]+=c;//
b[r+1]-=c;//这⾥要记得-c  不然 a 数组后⾯的会被多 +c
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];//这⾥就是移项了⼀下
cout<<a[i]<<" ";
}
return 0;
}
双指针
最长不重读⼦序列
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int n,ans=0;
int a[maxn],b[maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0,j=0;i<n;i++){
b[a[i]]++;
while(j<i&&b[a[i]]>1) b[a[j++]]--;
ans=max(ans,i-j+1);
}
cout<<ans;
return 0;
}
基础数据结构
单调队列
#include<bits/stdc++.h>
using namespace std;
int n,k,hh=0,tt=-1;// hh 单调队列头部  tt 单调队列尾部
int a[1000010],q[1000010];// q数组⽤来装单调队列元素的下标
int main(){
cin.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
/
/检查是否超过窗⼝长度若超过则对头 +1
if(i-q[hh]+1>k) hh++;
//判断队列是否单调递增(求的是窗⼝最⼩值，队头则是最⼩值)        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i+1>=k) cout<<a[q[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(i-q[hh]+1>k) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i+1>=k) cout<<a[q[hh]]<<" ";
}
return 0;
}
单调栈
#include<bits/stdc++.h>
using namespace std;
int tot,sta[1000010];
int main(){
cin.tie(0);
int n;  cin>>n;
while(n--){
int x;  cin>>x;
while(tot&&sta[tot]>=x) tot--;
if(!tot) cout<<"-1 ";
else cout<<sta[tot]<<" ";
sta[++tot] = x;
}
return 0;
}
怎么创建自己的博客单链表
#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int head,nex[maxn],val[maxn],idx;
void init(){
head = -1;
idx=0;
}
//插⼊到头结点
void insertHead(int x){
val[idx] = x;
nex[idx]=head;
head = idx++;
}
//将x插到下标是k的点后⾯
void insertOne(int k,int x){
val[idx] = x;
nex[idx] = nex[k];
nex[k] = idx++;
}
// 将下标是k的点后⾯的点删掉
void remove(int k){
nex[k] = nex[nex[k]];
}
int main(){
init();
int m; cin>>m;
while(m--){
string s; cin>>s;
if(s=="H"){
int x; cin>>x;
insertHead(x);
}else{
if(s=="D"){
int k; cin>>k;
if (!k) head = nex[head];
remove(k-1);
}else{
int k,x; cin>>k>>x;
insertOne(k-1,x);
}
}
}
for(int i=head;i != -1 ;i = nex[i]){
cout<<val[i]<<" ";
}
return 0;
}
Trie树
快速存储字符集合和快速查询字符集合
//Trie树快速存储字符集合和快速查询字符集合
#include <iostream>
using namespace std;
const int N = 100010;
//son[][]存储⼦节点的位置，分⽀最多26条；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。