模板
引领天下
2018-05-06 14:36:37
我收集的模板,希望对大家能有所帮助
# 拿了说一声,请不要做伸手党
```cpp
#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)))))
void DP_01(int cost,int weight){
for (int v=V;v>=cost;v--)f[v]=max(f[v],f[v-cost]+weight);
}
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]);
}
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);
}
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]);
}
template <typename _Tp>
inline void read(_Tp &x){
int w=1;char c=0;x=0;
while (c^'-'&&(c<'0'||c>'9'))c=getchar();
if (c=='-')w=-1,c=getchar();
while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
inline void write(int n){
if(n==0) return;
write(n/10);
putchar(n%10+'0');
}
最强栈模板:简单易懂!比STL易懂!支持9种操作!
V1.0V1.0
V1.0
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;
}
};
高精简便模板:
支持两个string的加减乘除取余阶乘!
请注意加上string头文件!
V1.0V1.0
V1.0
#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;
}
//////////////////////////////////////////////////////
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;
}
//////////////////////////////////////////////////////
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;
}
//////////////////////////////////////////////////////
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;
}
//////////////////////////////////////////////////////
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--;//将整形数组表示的余数转化成字符串表示的</span>
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;
}
//////////////////////////////////////////////////////
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);
}
//////////////////////////////////////////////////////
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;
}
//////////////////////////////////////////////////////
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;
}
大整数比较模板(更新,可比较负数)
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;
}
```
# 鸣谢:关于高精和栈的模板来自[罗陈(天卜的心事)c++小组](https://www.luogu.org/team/show?teamid=2342)