模板

发表于 更新于 阅读次数： Waline：

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

常用优化

点击展开/收起

 
1
2
3
4
5
6
7
8
9
10
11
#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;
    }
};

线段树

支持区间/单点的乘/加/查询，维护了 $\min,\max,\text{sum}$。可以通过注释一条代码实现有Mod和无Mod的转换。

点击展开/收起

 
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
template<class _Tp>class Segment_Tree{
    #define N 100005
    // #define INF INT_MAX
    // #define Enable_Mod
    #define Tree_sum_tag 1
    // #define Tree_min_tag 1
    // #define Tree_max_tag 1
    #define Tree_add_tag 1
    // #define Tree_mul_tag 1
    public:
        _Tp a[N];
        int n;
        #ifdef Enable_Mod
            _Tp mod=_Tp(0);
        #endif
    private:
        #define N 100005
        #ifdef Tree_sum_tag
        _Tp sum[N<<2];
        #endif
        #ifdef Tree_max_tag
        _Tp mx[N<<2];
        #endif
        #ifdef Tree_min_tag
        _Tp mn[N<<2];
        #endif
        #ifdef Tree_add_tag
        _Tp taga[N<<2];
        #endif
        #ifdef Tree_mul_tag
        _Tp tagm[N<<2];
        #endif
        inline int lson(int p){return p<<1;}
        inline int rson(int p){return (p<<1)|1;}
        inline void push_up(int p){
            #ifdef Tree_sum_tag
                sum[p]=sum[lson(p)]+sum[rson(p)];
                #ifdef Enable_Mod
                sum[p]%=mod;
                #endif
            #endif
            #ifdef Tree_min_tag
                mn[p]=min(mn[lson(p)],mn[rson(p)]);
            #endif
            #ifdef Tree_max_tag
                mx[p]=max(mx[lson(p)],mx[rson(p)]);
            #endif
        }
        inline void push_down(int p,int l,int r){
            register int mid=l+r>>1;
            #ifdef Tree_mul_tag
                tagm[lson(p)]*=tagm[p],tagm[rson(p)]*=tagm[p];
                #ifdef Enable_Mod
                tagm[lson(p)]%=mod,tagm[rson(p)]%=mod;
                #endif
                #ifdef Tree_sum_tag
                    sum[lson(p)]*=tagm[p],sum[rson(p)]*=tagm[p];
                    #ifdef Enable_Mod
                    sum[lson(p)]%=mod,sum[rson(p)]%=mod;
                    #endif
                #endif
                #ifdef Tree_add_tag
                    taga[lson(p)]*=tagm[p],taga[rson(p)]*=tagm[p];
                    #ifdef Enable_Mod
                    taga[lson(p)]%=mod,taga[rson(p)]%=mod;
                    #endif
                #endif
                #ifdef Tree_min_tag
                    mn[lson(p)]*=tagm[p],mn[rson(p)]*=tagm[p];
                    #ifdef Enable_Mod
                    mn[lson(p)]%=mod,mn[rson(p)]%=mod;
                    #endif
                #endif
                #ifdef Tree_max_tag
                    mx[lson(p)]*=tagm[p],mx[rson(p)]*=tagm[p];
                    #ifdef Enable_Mod
                    mx[lson(p)]%=mod,mx[rson(p)]%=mod;
                    #endif
                #endif
            #endif
            #ifdef Tree_add_tag
                taga[lson(p)]+=taga[p],taga[rson(p)]+=taga[p];
                #ifdef Enable_Mod
                taga[lson(p)]%=mod,taga[rson(p)]%=mod;
                #endif
                #ifdef Tree_sum_tag
                    sum[lson(p)]+=(mid-l+1)*taga[p],sum[rson(p)]+=(r-mid)*taga[p];
                    #ifdef Enable_Mod
                    sum[lson(p)]%=mod,sum[rson(p)]%=mod;
                    #endif
                #endif
                #ifdef Tree_max_tag
                    mx[lson(p)]+=taga[p],mx[rson(p)]+=taga[p];
                    #ifdef Enable_Mod
                    mx[lson(p)]%=mod,mx[rson(p)]%=mod;
                    #endif
                #endif
                #ifdef Tree_min_tag
                    mn[lson(p)]+=taga[p],mn[rson(p)]+=taga[p];
                    #ifdef Enable_Mod
                    mn[lson(p)]%=mod,mn[rson(p)]%=mod;
                    #endif
                #endif
            #endif
            #ifdef Tree_mul_tag
            tagm[p]=_Tp(1);
            #endif
            #ifdef Tree_add_tag
            taga[p]=_Tp(0);
            #endif
        }
        #ifdef Tree_add_tag
        inline void _add(int p,int nl,int nr,int l,int r,int k){
            if(nl<=l&&nr>=r){
                taga[p]+=k;
                #ifdef Enable_Mod
                taga[p]%=mod;
                #endif
                #ifdef Tree_sum_tag
                    sum[p]+=(r-l+1)*k;
                    #ifdef Enable_Mod
                    sum[p]%=mod;
                    #endif
                #endif
                #ifdef Tree_max_tag
                    mx[p]+=k;
                    #ifdef Enable_Mod
                    mx[p]%=mod;
                    #endif
                #endif
                #ifdef Tree_min_tag
                    mn[p]+=k;
                    #ifdef Enable_Mod
                    mn[p]%=mod;
                    #endif
                #endif
                return;
            }
            if(nl>r||nr<l)return ;
            push_down(p,l,r);
            register int mid=l+r>>1;
            _add(lson(p),nl,nr,l,mid,k);
            _add(rson(p),nl,nr,mid+1,r,k);
            push_up(p);
        }
        #endif
        #ifdef Tree_mul_tag
            inline void _mul(int p,int nl,int nr,int l,int r,_Tp k){
                if(nl<=l&&nr>=r){
                    tagm[p]*=k;
                    #ifdef Enable_Mod
                    tagm[p]%=mod;
                    #endif
                    #ifdef Tree_sum_tag
                        sum[p]*=k;
                        #ifdef Enable_Mod
                        sum[p]%=mod;
                        #endif
                    #endif
                    #ifdef Tree_add_tag
                        taga[p]*=k;
                        #ifdef Enable_Mod
                        taga[p]%=mod;
                        #endif
                    #endif
                    #ifdef Tree_max_tag
                        mx[p]*=k;
                        #ifdef Enable_Mod
                        mx[p]%=mod;
                        #endif
                    #endif
                    #ifdef Tree_min_tag
                        mn[p]*=k;
                        #ifdef Enable_Mod
                        mn[p]%=mod;
                        #endif
                    #endif
                    return;
                }
                if(nl>r||nr<l)return;
                push_down(p,l,r);
                register int mid=l+r>>1;
                _mul(lson(p),nl,nr,l,mid,k);
                _mul(rson(p),nl,nr,mid+1,r,k);
                push_up(p);
            }
        #endif
        #ifdef Tree_sum_tag
            inline _Tp _ask_sum(int p,int nl,int nr,int l,int r){
                if(nl<=l&&nr>=r)return sum[p];
                if(nl>r||nr<l)return _Tp(0);
                push_down(p,l,r);
                register int mid=l+r>>1;
                register _Tp res=0;
                res+=_ask_sum(lson(p),nl,nr,l,mid);
                #ifdef Enable_Mod
                res%=mod;
                #endif
                res+=_ask_sum(rson(p),nl,nr,mid+1,r);
                #ifdef Enable_Mod
                res%=mod;
                #endif
                return res;
            }
        #endif
        #ifdef Tree_max_tag
            inline _Tp _ask_max(int p,int nl,int nr,int l,int r){
                if(nl<=l&&nr>=r)return mx[p];
                if(nl>r||nr<l)return _Tp(-INF);
                push_down(p,l,r);
                register int mid=l+r>>1;
                register _Tp res=_Tp(-INF);
                res=max(res,_ask_max(lson(p),nl,nr,l,mid));
                res=max(res,_ask_max(rson(p),nl,nr,mid+1,r));
                return res;
            }
        #endif
        #ifdef Tree_min_tag
            inline _Tp _ask_min(int p,int nl,int nr,int l,int r){
                if(nl<=l&&nr>=r)return mn[p];
                if(nl>r||nr<l)return _Tp(INF);
                push_down(p,l,r);
                register int mid=l+r>>1;
                register _Tp res=_Tp(INF);
                res=min(res,_ask_min(lson(p),nl,nr,l,mid));
                res=min(res,_ask_min(rson(p),nl,nr,mid+1,r));
                return res;
            }
        #endif
        inline void _build(int p,int l,int r){
            #ifdef Tree_add_tag
                taga[p]=_Tp(0);
            #endif
            #ifdef Tree_mul_tag
                tagm[p]=_Tp(1);
            #endif
            if(l==r){
                #ifdef Tree_sum_tag
                    sum[p]=a[l];
                #endif
                #ifdef Tree_min_tag
                    mn[p]=a[l];
                #endif
                #ifdef Tree_max_tag
                    mx[p]=a[l];
                #endif
                #ifdef Tree_min_tag
                    mn[p]=a[l];
                #endif
                return ;
            }
            register int mid=l+r>>1;
            _build(lson(p),l,mid);
            _build(rson(p),mid+1,r);
            push_up(p);
        }
    public:
        inline void build(){_build(1,1,n);}
        #ifdef Tree_add_tag
            inline void add(int l,int r,int k){_add(1,l,r,1,n,k);}
        #endif
        #ifdef Tree_mul_tag
            inline void mul(int l,int r,int k){_mul(1,l,r,1,n,k);}
        #endif
        #ifdef Tree_sum_tag
        inline _Tp ask_sum(int l,int r){return _ask_sum(1,l,r,1,n);}
        #endif
        #ifdef Tree_min_tag
        inline _Tp ask_min(int l,int r){return _ask_min(1,l,r,1,n);}
        #endif
        #ifdef Tree_max_tag
        inline _Tp ask_max(int l,int r){return _ask_max(1,l,r,1,n);}
        #endif
        inline void clear(){
            memset(a,0,sizeof(a));
            #ifdef Tree_sum_tag
            memset(sum,0,sizeof(sum));
            #endif
        }
}

注：关于高精和栈的模板来自罗陈（天卜的心事）c++小组