Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

A+B problem

posted on 2021-08-30 22:27:21 | under 好东西 |

错解:

#include<cstdio>
using namespace std;
int main(){
    long long a,b;
    scanf("%lld%lld",&a,&b);
    printf("%lld",a+b);
}

正解:

一,递归

#include<cstdio>
using namespace std;
#define int long long
int a,b,c;
int f(int a){
    if(a<=5) return a;
    return f(a/2)+f(a-a/2);
}
signed main(){
    scanf("%lld%lld",&a,&b);
    c=f(a)+f(b);
    printf("%lld",c);
}

二,二分

#include<cstdio>
using namespace std;
long long a,b,c;
signed main(){
    long long l=-int(1e9)<<1,r=int(1e9)<<1;
    scanf("%lld%lld",&a,&b);
    while(r-l>1){
        c=(l+r)>>1;
        if(c-b<a) l=c;
        else if(c-b>a) r=c;
        else return printf("%lld",c),0;
    }
    if(l!=r) return printf("%lld",r),0;
}

三,模拟

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
int fu=1,f=1,a,b,c;
signed main(){
    scanf("%lld%lld",&a,&b);
    if(a<0&&b>0) fu=2;
    if(a>0&&b<0) fu=3;
    if(a<0&&b<0) f=-1;
    if(a==0) return printf("%lld",b),0;
    if(b==0) return printf("%lld",a),0;
    a=abs(a),b=abs(b);
    if(a>b&&fu==3) f=1;
    if(b>a&&fu==3) f=-1;
    if(b>a&&fu==2) f=1;
    if(b<a&&fu==2) f=-1;
    if(fu==1) c=a+b;
    if(fu>1) c=max(a,b)-min(a,b);
    c*=f;
    printf("%lld",c);
}

四,高精

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define int long long
int la,lb,lc,i,x,a[1000],b[1000],c[1000];
char a1[1000],b1[1000];
signed main(){
    cin>>a1>>b1;
    la=strlen(a1),lb=strlen(b1);
    for(i=0;i<=la-1;i++) a[la-i]=a1[i]-48;
    for(i=0;i<=lb-1;i++) b[lb-i]=b1[i]-48;
    lc=1,x=0;
    while(lc<=la||lc<=lb) c[lc]=a[lc]+b[lc]+x,x=c[lc]/10,c[lc]%=10,lc++;
    c[lc]=x;
    if(c[lc]==0) lc--;
    for(i=lc;i>=1;i--) printf("%lld",c[i]);
}

五,Floyd

#include<cstdio>
#include<iostream>
using namespace std;
#define int long long
int n=3,a,b,dis[4][4];
signed main(){
    scanf("%lld%lld",&a,&b);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) dis[i][j]=2147483647;
    dis[1][2]=a,dis[2][3]=b;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    printf("%lld",dis[1][3]);
}

六,Dijkstra+STL

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define int long long
const int N=405;
struct Edge{
    int v,w;
};
vector<Edge>edge[N*N];
int a,b,n,dis[N*N];
bool vis[N*N];
struct cmp{
    bool operator()(int a,int b){
        return dis[a]>dis[b];
    }
};
int Dijkstra(int start,int end){
    priority_queue<int,vector<int>,cmp>dijQue;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dijQue.push(start);
    dis[start]=0;
    while(!dijQue.empty()){
        int u=dijQue.top();
        dijQue.pop();
        vis[u]=0;
        if(u==end) break;
        for(int i=0;i<edge[u].size();i++) {
            int v=edge[u][i].v;
            if(dis[v]==-1||dis[v]>dis[u]+edge[u][i].w){
                dis[v]=dis[u]+edge[u][i].w;
                if(!vis[v]){
                    vis[v]=true;
                    dijQue.push(v);
                }
            }
        }
    }
    return dis[end];
}
signed main(){
    scanf("%lld%lld",&a,&b);
    Edge Qpush;
    Qpush.v=1,Qpush.w=a;
    edge[0].push_back(Qpush);
    Qpush.v=2,Qpush.w=b;
    edge[1].push_back(Qpush);
    printf("%lld",Dijkstra(0,2));
}

七,SPFA

#include<cstdio>
using namespace std;
#define int long long
int n,m,a,b,l,r,u,e,v1,op,head[200009],next[200009],dis[200009],len[200009],v[200009],team[200009],pd[100009];
int lt(int x,int y,int z){
    op++,v[op]=y;
    next[op]=head[x],head[x]=op,len[op]=z;
}
int SPFA(int s,int f){
    for(int i=1;i<=200009;i++) dis[i]=999999999;
    l=0,r=1,team[1]=s,pd[s]=1,dis[s]=0;
    while(l!=r){
        l=(l+1)%90000,u=team[l],pd[u]=0,e=head[u];
        while(e!=0){
            v1=v[e];
            if(dis[v1]>dis[u]+len[e]){
                dis[v1]=dis[u]+len[e];
                if(!pd[v1]){
                    r=(r+1)%90000,
                    team[r]=v1,
                    pd[v1]=1;
                }
            }
            e=next[e];
        } 
    }
    return dis[f];
}
signed main(){
    scanf("%lld%lld",&a,&b);
    lt(1,2,a);
    lt(2,3,b);
    printf("%lld",SPFA(1,3));
}

八,最小生成树

#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
#define INF 2140000000
struct tree{
    int x,y,t;
}a[10];
bool cmp(const tree&a,const tree&b){
    return a.t<b.t;
}
int f[11],i,j,k,n,m,x,y,t,ans;
int root(int x){
    if(f[x]==x) return x;
    f[x]=root(f[x]);
    return f[x];
}
signed main(){
    for(i=1;i<=10;i++) f[i]=i;
    for(i=1;i<=2;i++){
        scanf("%lld",&a[i].t);
        a[i].x=i+1;a[i].y=1;k++;
    }
    a[++k].x=1;a[k].y=3,a[k].t=INF;
    sort(a+1,a+1+k,cmp);
    for(i=1;i<=k;i++){
        x=root(a[i].x),y=root(a[i].y);
        if(x!=y) f[x]=y,ans+=a[i].t; 
    }
    printf("%lld",ans);
}

九,线段树

#include<cstdio>
using namespace std;
#define int long long
struct node{
    int val,l,r;
};
node t[5];
int n,m,a[5],f[5];
void build(int l,int r,int node){
    t[node].l=l;t[node].r=r;t[node].val=0;
    if(l==r){
        f[l]=node;
        t[node].val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,node*2);
    build(mid+1,r,node*2+1);
    t[node].val=t[node*2].val+t[node*2+1].val;
}
void update(int node){
    if(node==1) return;
    int fa=node>>1;
    t[fa].val=t[fa*2].val+t[fa*2+1].val;
    update(fa);
}
int find(int l,int r,int node){
    if(t[node].l==l&&t[node].r==r) return t[node].val;
    int sum=0;
    int lc=node*2;int rc=lc+1;
    if(t[lc].r>=l){
        if(t[lc].r>=r) sum+=find(l,r,lc);
        else sum+=find(l,t[lc].r,lc);
    }
    if(t[rc].l<=r){
        if(t[rc].l<=l) sum+=find(l,r,rc);
        else sum+=find(t[rc].l,r,rc);
    }
    return sum;
}
signed main(){
    for(int i=1;i<=2;i++) scanf("%lld",&a[i]);
    build(1,2,1);
    printf("%lld",find(1,2,1));
}

十,字典树

#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
struct node{
    int sum,str[26];
}s[1000];
char str1[100];
int t=0,tot=0,ss=0;
bool f1;
void built(){
    t=0;
    for(int i=0;i<strlen(str1);i++){
        if(str1[i]=='-'){
            f1=true;
            continue;
        }
        if(!s[t].str[str1[i]-'0'])
        s[t].str[str1[i]-'0']=++tot;
        t=s[t].str[str1[i]-'0'];
        s[t].sum=str1[i]-'0';
    }
}
int query(){
    int t=0;int s1=0;
    for(int i=0;i<strlen(str1);i++){
            if(str1[i]=='-') continue;
            if(!s[t].str[str1[i]-'0']) return s1;
            t=s[t].str[str1[i]-'0'];
            s1=s1*10+s[t].sum;
    }
    return s1;
}
signed main(){    
    for(int i=1;i<=2;i++){
        f1=false;
        scanf("%s",str1);
        built();
        if(f1)
        ss-=query();
        else ss+=query();
    }
    printf("%lld",ss);   
}

十一,LCA

#include<cstdio>
#define int long long
#define NI 2 
struct edge{
    int to,next,data;
}e[30];
int a,b,v[10],d[10],lca[10][NI+1],f[10][NI+1],tot=0;
void build(int x,int y,int z){
    e[++tot].to=y; e[tot].data=z; e[tot].next=v[x]; v[x]=tot;
    e[++tot].to=x; e[tot].data=z; e[tot].next=v[y]; v[y]=tot;
}
void dfs(int x){
    for(int i=1;i<=NI;i++)
        f[x][i]=f[x][i-1]+f[lca[x][i-1]][i-1],
        lca[x][i]=lca[lca[x][i-1]][i-1];
    for(int i=v[x];i;i=e[i].next){
        int y=e[i].to;
        if(lca[x][0]==y) continue;
        lca[y][0]=x;
        f[y][0]=e[i].data;
        d[y]=d[x]+1;
        dfs(y);
    }
}
int ask(int x,int y){                
    if(d[x]<d[y]){
        int t=x;
        x=y;
        y=t;
    }
    int k=d[x]-d[y],ans=0;
    for(int i=0;i<=NI;i++)
        if(k&(1<<i))
            ans+=f[x][i],
            x=lca[x][i];
    for(int i=NI;i>=0;i--)
        if(lca[x][i]!=lca[y][i])
            ans+=f[x][i]+f[y][i],
            x=lca[x][i],y=lca[y][i];
    return ans+f[x][0]+f[y][0];
}
signed main(){
    scanf("%lld%lld",&a,&b);
    build(1,2,a);
    build(1,3,b);
    dfs(1);
    printf("%lld",ask(2,3));
}

十二,LCT

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
struct node{
    int data,rev,sum;
    node *son[2],*pre;
    bool judge();
    bool isroot();
    void pushdown();
    void update();
    void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x){
    node *now=lct+ ++top;
    now->data=x;
    now->pre=now->son[1]=now->son[0]=lct;
    now->sum=0;
    now->rev=0;
    return now;
}
bool node::judge(){return pre->son[1]==this;}
bool node::isroot(){
    if(pre==lct)return true;
    return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown(){
    if(this==lct||!rev)return;
    swap(son[0],son[1]);
    son[0]->rev^=1;
    son[1]->rev^=1;
    rev=0;
}
void node::update(){sum=son[1]->sum+son[0]->sum+data;}
void node::setson(node *child,int lr){
    this->pushdown();
    child->pre=this;
    son[lr]=child;
    this->update();
}
void rotate(node *now){
    node *father=now->pre,*grandfa=father->pre;
    if(!father->isroot()) grandfa->pushdown();
    father->pushdown();now->pushdown();
    int lr=now->judge();
    father->setson(now->son[lr^1],lr);
    if(father->isroot()) now->pre=grandfa;
    else grandfa->setson(now,father->judge());
    now->setson(father,lr^1);
    father->update();now->update();
    if(grandfa!=lct) grandfa->update();
}
void splay(node *now){
    if(now->isroot())return;
    for(;!now->isroot();rotate(now))
    if(!now->pre->isroot())
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now){
    node *last=lct;
    for(;now!=lct;last=now,now=now->pre){
        splay(now);
        now->setson(last,1);
    }
    return last;
}
void changeroot(node *now){
    access(now)->rev^=1;
    splay(now);
}
void connect(node *x,node *y){
    changeroot(x);
    x->pre=y;
    access(x);
}
void cut(node *x,node *y){
    changeroot(x);
    access(y);
    splay(x);
    x->pushdown();
    x->son[1]=y->pre=lct;
    x->update();
}
int query(node *x,node *y){
    changeroot(x);
    node *now=access(y);
    return now->sum;
}
signed main(){
    scanf("%lld%lld",&a,&b);
    node *A=getnew(a);
    node *B=getnew(b);
    connect(A,B);
    cut(A,B);
    connect(A,B);
    printf("%lld",query(A,B));
}

十三,树剖

#include<iostream>
#include<vector>
using namespace std;
#define int long long
#define MAXN 100005
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
int n,x,y,tot,dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],top[MAXN],val[MAXN],idx[MAXN],mp[MAXN],sum[MAXN*4],lazy[MAXN*4];
vector<int>a[MAXN];
void pushdown(int x,int y,int p){
    int mid=(x+y)>>1;
    sum[lson(p)]+=(mid-x+1)*lazy[p];lazy[lson(p)]+=lazy[lson(p)];
    sum[rson(p)]+=(y-mid)*lazy[p];lazy[rson(p)]+=lazy[p];
    lazy[p]=0;
}
void build(int x,int y,int p){
    if(x==y){
        sum[p]=idx[x];
        return;
    }
    pushdown(x,y,p);
    int mid=(x+y)>>1;
    build(x,mid,lson(p));
    build(mid+1,y,rson(p));
    sum[p]=sum[lson(p)]+sum[rson(p)];
}
int query(int x,int y,int l,int r,int p){
    if(l<=x&&r>=y) return sum[p];
    pushdown(x,y,p);
    int mid=(x+y)>>1,ans=0;
    if(l<=mid)ans+=query(x,mid,l,r,lson(p));
    if(r>mid)ans+=query(mid+1,y,l,r,rson(p));
    sum[p]=sum[lson(p)]+sum[rson(p)];
    return ans;
}
void modify(int x,int y,int l,int r,int val,int p){
    if(l<=x&&r>=y){
        lazy[p]+=val;
        sum[p]+=val*(y-x+1);
        return;
    }
    pushdown(x,y,p);
    int mid=(x+y)>>1;
    if(l<=mid)modify(x,mid,l,r,val,lson(p));
    if(r>mid)modify(mid+1,y,l,r,val,rson(p));
    sum[p]=sum[lson(p)]+sum[rson(p)];
    return;
}
void dfs_build(int p){
    dep[p]=dep[fa[p]]+1;
    siz[p]=1;
    for(int i=0;i<a[p].size();++i){
        if(a[p][i]==fa[p])continue;
        fa[a[p][i]]=p;
        dfs_build(a[p][i]);
        siz[p]+=siz[a[p][i]];
        if(siz[son[p]]<siz[a[p][i]])
            son[p]=a[p][i];
    }
}
void dfs_top(int p){
    top[p]=son[fa[p]]!=p?p:top[fa[p]];
    idx[++tot]=val[p];mp[p]=tot;
    if(son[p])dfs_top(son[p]);
    for(int i=0;i<a[p].size();++i)
        if(a[p][i]!=fa[p]&&a[p][i]!=son[p])
            dfs_top(a[p][i]);
}
void OP1(int x,int y,int w){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        modify(1,n,mp[top[x]],mp[x],w,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    modify(1,n,mp[x],mp[y],w,1);
    return;
}
int OP2(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=query(1,n,mp[top[x]],mp[x],1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=query(1,n,mp[x],mp[y],1);
    return ans;
}
signed main(){
    n=3;
    a[1].push_back(2);a[1].push_back(3);
    a[2].push_back(1);a[3].push_back(1);
    dfs_build(1);
    dfs_top(1);
    build(1,n,1);
    scanf("%lld%lld",&x,&y);
    OP1(2,2,x);
    OP1(3,3,y);
    printf("%lld",OP2(2,3));
}

以上内容推荐在需要计算加法时使用