模板

我收集的模板,希望对大家能有所帮助

常用优化

点击显/隐
1
2
3
4
5
6
7
8
9
10
#pragma comment(linker, "/STACK:102400000,102400000") //扩系统栈
#pragma GCC diagnostic error "-std=c++14" //暴力开C++14
#pragma GCC optimize ("O3") //开O3
#pragma GCC -mcmodle=large //开巨型数组不RE(编译时间变长)

std::ios::sync_with_stdio(false); //cin/cout
cin.tie(0);

#define min(x,y) ((y)^(((x)^(y))&(-((x)<(y)))))
#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))

背包

01背包

点击显/隐
1
2
3
void DP_01(int cost,int weight){
for (int v=V;v>=cost;v--)f[v]=max(f[v],f[v-cost]+weight);
}

完全背包

点击显/隐
1
2
3
void DP_WQ(int cost,int weight){
for (int v=cost;v<=V;v++)f[v]=max(f[v],f[v-c[i]]+w[i]);
}

多重背包

点击显/隐
1
2
3
4
5
6
void DP_DC(int cost,int weight,int amount){
if (cost*amount>=V){DP_WQ(cost,weight);return ;}
int k=1;
while (k<amount/*num?*/)DP_01(k*cost,k*weight),amount-=k,k*=2;
DP_01(amount*cost,amount*weight);
}

分组背包

点击显/隐
1
2
3
4
5
6
void DP_FZ(){
for (int k=1;k<=t;k++)
for (int v=V;v>=0;v--)
for (int i=1;i<=n[k];i++)
if(c[k][i]<=v)f[v]=max(f[v],f[v-c[k][i]]+w[k][i]);
}

IO优化(超快的见真正的IO优化

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <typename _Tp>
inline void read(_Tp &x){
int f=1;x=0;char ch=nc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=nc();}
x*=f;
}
inline void write(long long n){
if(n==0) return;
write(n/10);
putchar(n%10+'0');
}

高精简便模板$V_{1.1}$:支持两个string的加减乘除取余阶乘比较!

请注意加上string头文件!

高精加

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define L 100001
string add(string a,string b)//只限两个非负整数相加,不支持负数
{
string ans;
int na[L]={0},nb[L]={0};
int la=a.size(),lb=b.size();
for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
int lmax=la>lb?la:lb;
for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
if(na[lmax]) lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans;
}

高精减

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define L 100000
string sub(string a,string b)//只限大的非负整数减小的非负整数
{
string ans;
int na[L]={0},nb[L]={0};
int la=a.size(),lb=b.size();
for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
int lmax=la>lb?la:lb;
for(int i=0;i<lmax;i++)
{
na[i]-=nb[i];
if(na[i]<0) na[i]+=10,na[i+1]--;
}
while(!na[--lmax]&&lmax>0) ;lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans;
}

高乘高

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define L 100000
string mul(string a,string b)//高乘高
{
string s;
int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();
fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
for(int i=1;i<=La;i++)
for(int j=1;j<=Lb;j++)
nc[i+j-1]+=na[i]*nb[j];
for(int i=1;i<=La+Lb;i++)
nc[i+1]+=nc[i]/10,nc[i]%=10;
if(nc[La+Lb]) s+=nc[La+Lb]+'0';
for(int i=La+Lb-1;i>=1;i--)
s+=nc[i]+'0';
return s;
}

高乘单

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define L 100000
string mulint(string a,int b)//高精度a*单精度b
{
string ans;
int La=a.size(),na[L];
fill(na,na+L,0);
for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';
int w=0;
for(int i=0;i<La;i++) na[i]=na[i]*b+w,w=na[i]/10,na[i]=na[i]%10;
while(w) na[La++]=w%10,w/=10;
La--;
while(La>=0) ans+=na[La--]+'0';
return ans;
}

高除高

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#define L 100000
int sub(int *a,int *b,int La,int Lb)
{
if(La<Lb) return -1;//如果a小于b,则返回-1
if(La==Lb)
{
for(int i=La-1;i>=0;i--)
if(a[i]>b[i]) break;
else if(a[i]<b[i]) return -1;//如果a小于b,则返回-1

}
for(int i=0;i<La;i++)//高精度减法
{
a[i]-=b[i];
if(a[i]<0) a[i]+=10,a[i+1]--;
}
for(int i=La-1;i>=0;i--)
if(a[i]) return i+1;//返回差的位数
return 0;//返回差的位数

}
string div(string n1,string n2,int nn)//n1,n2是字符串表示的被除数,除数,nn是选择返回商还是余数
{
string s,v;//s存商,v存余数
int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;//a,b是整形数组表示被除数,除数,tp保存被除数的长度
fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);//数组元素都置为0
for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
if(La<Lb || (La==Lb && n1<n2)) {
//cout<<0<<endl;
return n1;}//如果a<b,则商为0,余数为被除数
int t=La-Lb;//除被数和除数的位数之差
for(int i=La-1;i>=0;i--)//将除数扩大10^t倍
if(i>=t) b[i]=b[i-t];
else b[i]=0;
Lb=La;
for(int j=0;j<=t;j++)
{
int temp;
while((temp=sub(a,b+j,La,Lb-j))>=0)//如果被除数比除数大继续减
{
La=temp;
r[t-j]++;
}
}
for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;//统一处理进位
while(!r[i]) i--;//将整形数组表示的商转化成字符串表示的
while(i>=0) s+=r[i--]+'0';
//cout<<s<<endl;
i=tp;
while(!a[i]) i--;//将整形数组表示的余数转化成字符串表示的
while(i>=0) v+=a[i--]+'0';
if(v.empty()) v="0";
//cout<<v<<endl;
if(nn==1) return s;
if(nn==2) return v;
}

高除单

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define L 100000
string div(string a,int b)//高精度a除以单精度b
{
string r,ans;
int d=0;
if(a=="0") return a;//特判
for(int i=0;i<a.size();i++)
{
r+=(d*10+a[i]-'0')/b+'0';//求出商
d=(d*10+(a[i]-'0'))%b;//求出余数
}
int p=0;
for(int i=0;i<r.size();i++)
if(r[i]!='0') {p=i;break;}
return r.substr(p);
}

高模单

点击显/隐
1
2
3
4
5
6
7
#define L 100000
int mod(string a,int b)//高精度a除以单精度b取模
{
int d=0;
for(int i=0;i<a.size();i++) d=(d*10+(a[i]-'0'))%b;//求出余数
return d;
}

高精阶乘

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define L 100000
string fac(int n)
{
int a[L];
string ans;
if(n==0) return "1";
fill(a,a+L,0);
int s=0,m=n;
while(m) a[++s]=m%10,m/=10;
for(int i=n-1;i>=2;i--)
{
int w=0;
for(int j=1;j<=s;j++) a[j]=a[j]*i+w,w=a[j]/10,a[j]=a[j]%10;
while(w) a[++s]=w%10,w/=10;
}
while(!a[s]) s--;
while(s>=1) ans+=a[s--]+'0';
return ans;
}

大整数比较模板(可比较负数)

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline bool compare(string a,string b) {
int i,la,lb;
la=a.length();
lb=b.length();
if(a[0]=='-'&&b[0]!='-')return 1;
if(a[0]!='-'&&b[0]=='-')return 0;
if(a[0]=='-'&&b[0]=='-'){
string x=a,y=b;
x[0]='0';y[0]='0';
return !compare(x,y);
}
if (la>lb) return 0;
if (la<lb) return 1;
for(i=la-1; i>=0; i--) {
if (a[i]>b[i]) return 0;
if (a[i]<b[i]) return 1;
}
return 0;
}

数据结构

最强栈模板$V_{1.0}$:简单易懂!比STL易懂!支持9种操作!

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
struct Stack{
int s[100001];
int maxn;
bool push(int x){
if(maxn==100000)return 0;
s[++maxn]=x;
return 1;
}
bool pop(){
if(maxn==0)return 0;
maxn--;
return 1;
}
int get(){
return maxn;
}
void clear(){
for(int i=0;i<=100000;i++){
s[i]=0;
}
maxn=0;
}
void visit(){
for(int i=1;i<=maxn;i++){
cout<<s[i]<<' ';
}
cout<<endl;
}
bool isin(int x){
for(int i=1;i<=maxn;i++){
if(s[i]==x)return true;
}
return false;
}
void Sort(){
sort(s+1,s+maxn+1);
}
void Unique(){
sort(s+1,s+maxn+1);
maxn=unique(s+1,s+maxn+1)-s-1;
}
};

线段树1

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N=100005;
#define ll long long
struct Tree{
ll ans[N<<2],tag[N<<2],a[N];
inline ll lson(ll p){return p<<1;}
inline ll rson(ll p){return (p<<1)|1;}
inline void push_up(ll p){ans[p]=ans[lson(p)]+ans[rson(p)];}
inline void build(ll p,ll l,ll r){
if (l==r){ans[p]=a[l];return ;}
ll mid=(l+r)>>1;
build(lson(p),l,mid);
build(rson(p),mid+1,r);
push_up(p);
tag[p]=0;
}
inline void lazy_tag(ll p,ll l,ll r,ll k){ans[p]+=(r-l+1)*k,tag[p]+=k;}
inline void push_down(ll p,ll l,ll r){
ll mid=(l+r)>>1;
lazy_tag(lson(p),l,mid,tag[p]);
lazy_tag(rson(p),mid+1,r,tag[p]);
tag[p]=0;
}
inline void change(ll p,ll nl,ll nr,ll l,ll r,ll k){//nl,nr->changing l,changing r;l,r->visiting l,visiting r
if (nl<=l&&nr>=r){ans[p]+=(r-l+1)*k,tag[p]+=k;return ;}
ll mid=(l+r)>>1;
push_down(p,l,r);
if (nl<=mid)change(lson(p),nl,nr,l,mid,k);
if (nr>mid)change(rson(p),nl,nr,mid+1,r,k);
push_up(p);
}
inline ll ask(ll p,ll nl,ll nr,ll l,ll r){
if (nl<=l&&nr>=r)return ans[p];
ll mid=(l+r)>>1,res=0;
push_down(p,l,r);
if (nl<=mid)res+=ask(lson(p),nl,nr,l,mid);
if (nr>mid)res+=ask(rson(p),nl,nr,mid+1,r);
return res;
}
}

线段树2

点击显/隐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#define ll long long
const int N=100005;
struct Segment_tree2{
ll a[N],ans[N<<2],taga[N<<2],tagc[N<<2],n,m,mod;
inline ll lson(ll p){return p<<1;}//左儿子
inline ll rson(ll p){return (p<<1)|1;}//右儿子
inline void push_up(ll p){ans[p]=(ans[lson(p)]+ans[rson(p)])%mod;}//合并子区间信息
inline void build(ll p,ll l,ll r){//建树
if (l==r){ans[p]=a[l];tagc[p]=1,taga[p]=0;return ;}
ll mid=(l+r)>>1;
build(lson(p),l,mid);
build(rson(p),mid+1,r);
push_up(p);
tagc[p]=1,taga[p]=0;
}
inline void push_down(ll p,ll l,ll r){//下传lazy_tag
ll mid=(l+r)>>1;
ans[lson(p)]=(ans[lson(p)]*tagc[p]+(mid-l+1)*taga[p])%mod;
tagc[lson(p)]=(tagc[lson(p)]*tagc[p])%mod;
taga[lson(p)]=(taga[lson(p)]*tagc[p]+taga[p])%mod;//左儿子下传
ans[rson(p)]=(ans[rson(p)]*tagc[p]+(r-mid)*taga[p])%mod;
tagc[rson(p)]=(tagc[rson(p)]*tagc[p])%mod;
taga[rson(p)]=(taga[rson(p)]*tagc[p]+taga[p])%mod;//右儿子下传
tagc[p]=1,taga[p]=0;
}
inline void change1(ll p,ll l,ll r,ll nl,ll nr,ll k){//区间加,(l,r)为当前访问区间,(nl,nr)为修改区间
if (nl<=l&&nr>=r){ans[p]=(ans[p]+(r-l+1)*k)%mod;taga[p]=(taga[p]+k)%mod;return ;}
if (l>nr||r<nl)return ;
push_down(p,l,r);
ll mid=(l+r)>>1;
change1(lson(p),l,mid,nl,nr,k);
change1(rson(p),mid+1,r,nl,nr,k);
push_up(p);
}
inline void change2(ll p,ll l,ll r,ll nl,ll nr,ll k){//区间乘,(l,r)为当前访问区间,(nl,nr)为修改区间
if (nl<=l&&nr>=r){ans[p]=(ans[p]*k)%mod;tagc[p]=(tagc[p]*k)%mod;taga[p]=(taga[p]*k)%mod;return ;}
if (l>nr||r<nl)return ;
push_down(p,l,r);
ll mid=(l+r)>>1;
change2(lson(p),l,mid,nl,nr,k);
change2(rson(p),mid+1,r,nl,nr,k);
push_up(p);
}
inline ll ask(ll p,ll l,ll r,ll nl,ll nr){//查询,(l,r)为当前访问区间,(nl,nr)为查询区间
if (nl<=l&&nr>=r){return ans[p];}
if (l>nr||r<nl)return 0;
push_down(p,l,r);
ll mid=(l+r)>>1,res=0;
res=(res+ask(lson(p),l,mid,nl,nr))%mod;
res=(res+ask(rson(p),mid+1,r,nl,nr))%mod;
return res;
}
}tree;

注:关于高精和栈的模板来自罗陈(天卜的心事)c++小组