板子合集

chen_qian · 2021-10-20 09:52:27 · 个人记录

以下板子如果被hack了请私信我

1. 普通带符号高精加减乘

#include<bits/stdc++.h>
#define N 1005
#define ull unsigned long long 
using namespace std;
ull base=233;
struct bigint{
    int a[N],len;
    int op; 
    ull h[N];
    bigint(){
        memset(a,0,sizeof(a));
        len=1;
        op=1;
    }
    void get(){
        for(int i=len;i>=1;i--) h[i]=h[i+1]*base+a[i]+1;
    }
    void build(string s){
        if(s[0]=='-') op=-1;
        else s=" "+s,op=1;
        len=s.size()-1;
        for(int i=1;i<=len;i++) a[len-i+1]=s[i]-'0';
        get();
    }
    void print(){
        if(op==-1) putchar('-');
        for(int i=len;i>=1;i--) printf("%d",a[i]);
    }
};
bigint operator +(bigint a,bigint b){       
    if(a.len<b.len) swap(a,b);
    for(int i=1;i<=a.len;i++){
        a.a[i]+=b.a[i];
        if(a.a[i]>=10){
            a.a[i+1]+=a.a[i]/10;
            a.a[i]%=10;
        }
    }
    if(a.a[a.len+1]>0) a.len++;
    if(!a.len) a.len=1;
    a.get();
    return a;
}
bigint operator -(bigint a,bigint b){
    for(int i=1;i<=b.len;i++){
        a.a[i]-=b.a[i];
        if(a.a[i]<0){
            a.a[i+1]--;
            a.a[i]+=10;
        }
    }
    while(a.a[a.len]==0&&a.len>=1) a.len--;
    if(!a.len) a.len=1;
    a.get();
    return a;
}
bigint operator *(bigint a,bigint b){
    bigint res;
    res.len=a.len+b.len-1;
    for(int i=1;i<=a.len;i++){
        for(int j=1;j<=b.len;j++){
            res.a[i+j-1]+=a.a[i]*b.a[j];
            if(res.a[i+j-1]>=10){
                res.a[i+j]+=res.a[i+j-1]/10;
                res.a[i+j-1]%=10;
            }
        }
    }
    while(res.a[res.len+1]>0) res.len++;
    res.get();
    return res;
}
bool operator <(bigint a,bigint b){
    if(a.op!=b.op)return a.op<b.op; 
    if(a.op==1){
        if(a.len!=b.len) return a.len<b.len;
        int l=1,r=a.len,ans=a.len+1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(a.h[mid]==b.h[mid]) ans=mid,r=mid-1;
            else l=mid+1;  
        }
        if(ans==1) return false;
        return a.a[ans-1]<b.a[ans-1];
    } 
    else{
        if(a.len!=b.len) return a.len>b.len;
        int l=1,r=a.len,ans=a.len+1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(a.h[mid]==b.h[mid]) ans=mid,r=mid-1;
            else l=mid+1;  
        }
        if(ans==1) return false;
        return a.a[ans-1]>b.a[ans-1];
    }
}
bigint add(bigint a,bigint b){
    if(a.op==b.op){
        int v=a.op;
        bigint tmp=(a+b);
        tmp.op=v;
        return tmp;
    }
    else{
        if(a.op==-1) swap(a,b);
        bigint tmp;
        b.op=1;
        if(a<b){tmp=b-a;tmp.op=-1;}
        else{tmp=a-b;tmp.op=1;}
        return tmp;
    }
}
bigint sub(bigint a,bigint b){
    if(a.op==-1){
        if(b.op==-1){
            a.op=b.op=1;
            if(b<a){
                bigint tmp=a-b;
                tmp.op=-1;
                return tmp;
            } 
            else{
                bigint tmp=b-a;
                tmp.op=1;
                return tmp;
            }
        }
        else{
            bigint tmp=(a+b);
            tmp.op=-1;
            return tmp;
        }
    }
    else{
        if(b.op==1){
            if(a<b){
                bigint tmp=b-a;
                tmp.op=-1;
                return tmp;
            } 
            else{
                bigint tmp=a-b;
                tmp.op=1;
                return tmp;
            }
        }
        else{
            bigint tmp=(a+b);
            tmp.op=1;
            return tmp;
        }
    }
}
bigint mul(bigint a,bigint b){
    bigint tmp=a*b;
    if(a.op==b.op) tmp.op=1;
    else tmp.op=-1;
    return tmp;
}
int main(){
    string a,b;
    cin>>a>>b;  
    bigint p,q;
    p.build(a),q.build(b);
    char c;
    cin>>c;
    if(c=='+') p=add(p,q);
    if(c=='-') p=sub(p,q);
    if(c=='*') p=mul(p,q);
    p.print();  
    return 0;
} 

• 出现的问题

  • 正反搞错，记住字符串的低位要放到高位

  • 减法时符号搞成加号

  • 乘法 i,j 写错

  • hash 处理有问题

2. 单链表（模板来源acwing）

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int head,nxt[N],v[N];
int idx;
int main(){
    int m;
    scanf("%d",&m);
    while(m--){
        char op;
        cin>>op;
        int x,y;
        if(op=='H'){
            scanf("%d",&x);
            v[++idx]=x;
            nxt[idx]=head;
            head=idx;
        }
        if(op=='D'){
            scanf("%d",&x);
            if(!x) head=nxt[head];
            else nxt[x]=nxt[nxt[x]];
        }
        if(op=='I'){
            scanf("%d%d",&x,&y);
            v[++idx]=y;
            nxt[idx]=nxt[x];
            nxt[x]=idx; 
        }
    } 
    for(int i=head;i;i=nxt[i]) printf("%d ",v[i]);
    return 0;
}