世纪难题A+B problem的解法

userId_undefined

i 莒勽（回关）鼚袃氜褎嬽槼鑸丌

时间刺客空间掌握者出道萌新分支·分支解题者循环·循环打卡人荣耀黄金

2025-08-10 11:09:13

发布于：浙江

27阅读
0回复
0点赞

原题链接\mathbf{\color{SkyBlue}原题\color{Pink}链接\color{Black}}：1.A+B problem

前言\mathbf{\color{Goldenrod}前言}

众所周知，\mathsf{\color{Gold}众所周知，}A+B problem\mathsf{\color{Red}A+B~problem}是一道世纪难题，因为他的通过率：\mathsf{\color{Gold}是一道世纪难题，因为他的通过率：}

还没有这道\mathsf{\color{Silver}还没有这道}Moorio Kart−−Platinum\mathsf{\color{Black}Moorio~Kart--Platinum}高：\mathsf{\color{Silver}高：}

所以下面我将会给出几种解法\mathsf{\color{Teal}所以下面我将会给出几种解法}
注：本帖仅供娱乐

第一种：线段树\mathbf{\color{Goldenrod}第一种：线段树}

#include<bits/stdc++.h>
using namespace std;
int a[114514];
struct node{
    int l,r,val;
}tree[314159];
void build(int l,int r,int p){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    tree[p].val=tree[p*2].val+tree[p*2+1].val;
}               
void update(int l,int r,int p,int x,int y){
    if(l==r){
        tree[p].val+=y;
        return;
    }
    int mid=(l + r)>>1;
    if(x<=mid)update(l,mid,p*2,x,y);
    else update(mid+1,r,p*2+1,x,y);
    tree[p].val=tree[p*2].val+tree[p*2+1].val;
}
int query(int l,int r,int p,int x,int y){
    if(x<=l&&y>=r){ 
        return tree[p].val; 
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(x<=mid)ans+=query(l,mid,p*2,x,y);
    if(y>mid)ans+=query(mid+1,r,p*2+1,x,y);
    return ans;
}
int main(){
    build(1,2,1);
    for(int i=1;i<=2;i++){
        int x;
        cin>>x; 
        update(1,2,1,i,x);
    }
    cout<<query(1,2,1,1,2)<<"\n";
    return 0;
}

第二种：树状数组\mathbf{\color{Goldenrod}第二种：树状数组}

#include<bits/stdc++.h>
using namespace std;
int a[114514],f[114514];
int lowbit(int x){
	return x&-x;
} 
void add(int x,int k){
	while(x<=2){
		f[x]+=k;
		x+=lowbit(x);
	}
} 
void add(int l,int r,int k){
	add(l,k); 
	add(r+1,-k);
}
long long ask(int x){
	long long ans=0;
	while(x){
		ans+=f[x];
		x-=lowbit(x);
	}
	return ans; 
}

int main(){
	for(int i=1;i<=2;i++){
		cin>>a[i];
		add(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=2;i++){
        int x;
		cin>>x;
		add(1,1,x);
	}
    cout<<ask(1)+ask(2);
	return 0;
}

第三种：高精度\mathbf{\color{Goldenrod}第三种：高精度}

#include<bits/stdc++.h>
using namespace std;
int A[114514],B[114514],C[114514];
int main(){
	string a,b;
	cin>>a>>b;
	for(int i=a.size()-1,j=1;i>=0;i--,j++){
		A[j]=a[i]-'0';
	}
	for(int i=b.size()-1,j=1;i>=0;i--,j++){
		B[j]=b[i]-'0';
	}
	int len=max(a.size(),b.size());
	for(int i=1;i<=len;i++){
		C[i]+=A[i]+B[i];
		C[i+1]+=C[i]/10;
		C[i]=C[i]%10;
	}
	if(C[len+1]!=0){
		len++;
	}
	for(int i=len;i>0;i--){
		cout<<C[i];
	}
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 3

热门讨论