yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

模板

posted on 2018-05-06 14:36:37 | under 未分类 |

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

拿了说一声,请不要做伸手党

#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++小组