[竞赛入门||算法进阶]简单のa+b-题解(C/C++代码)，高精度算法，超级a+b!!!（另外附上LCT写法，值得一看！）

879 阅读 4 评论 2 点赞

# 这是本OJ第一个题目
代码也很简单（甚至不需要自己写，在线编译器默认就是这个）
```c
#include<stdio.h>
int main()
{
    int a,b;
    while(~scanf("%d%d", &a, &b))printf("%d\n",a+b);
    return 0;
}
```
但是！
# 我们仅仅满足于此吗！！！
3128738217382137+3871283721837213892173218等于**多少！！！**
这已经超出了int甚至long long int的数据范围，这可
咋整啊！！！
于是机智的人们想到了用数组模拟整数位，一个数组中的元素代码这一位的大小，而下标则代表这个数字的位置，废话不多说，贴代码！！！
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    char a1[1000],b1[1000];
    int a[1000],b[1000],c[1000];
    int main()
    {
        scanf("%s",a1);scanf("%s",b1);//scanf就爆0！
        if(a1[0]==48&&b1[0]==48)
        {
            cout<<"0"<<endl;
            return 0;
        }
        int lena=strlen(a1),lenb=strlen(b1);
        for(int i=0;i<lena;i++)
        {
            a[lena-i-1]=int(a1[i]-48);
        }
        for(int i=0;i<lenb;i++)
        {
            b[lenb-i-1]=int(b1[i]-48);//倒序输入便于进位
        }
        int m=max(lena,lenb);
        for(int i=0;i<m;i++)
        {
            c[i]+=a[i]+b[i];//不能直接赋值，要加上前面的进位
            while(c[i]>=10)
            {
                c[i+1]++;
                c[i]-=10;
            }
        }
        m++;
        while(c[m]==0)    m--; //删除前导0
        for(int i=m;i>=0;i--)
            cout<<c[i];
        cout<<endl;
        return 0;
}
```
就这样，只要数字不大于1000位，咱都能整！！！(超过1k位把数组长度扩大即可)。
算法之美就在于此，追寻nb写法与算法之道！！！
## 下面附上sb写法，切勿模仿
```cpp
#include<bits/stdc++.h>
using namespace std;
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;
}
int main()
{
    while(~scanf("%d%d",&a,&b))
    {
    	node *A=getnew(a);
        node *B=getnew(b);
        //连边 Link
            connect(A,B);
        //断边 Cut
            cut(A,B);
        //再连边orz Link again
            connect(A,B);
        printf("%d\n",query(A,B)); 
	}
    
    return 0;
}
```

0.0分

9 人评分

本文分类：题解列表
浏览次数：879 次浏览
发布日期：2019-06-12 00:23:13
本文链接：https://blog.dotcpp.com/a/60293

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

[竞赛入门||算法进阶]简单のa+b-题解(C/C++代码)，高精度算法，超级a+b!!!（另外附上LCT写法，值得一看！）

评论列表共有 4 条评论

发表评论取消回复

[竞赛入门||算法进阶]简单のa+b-题解(C/C++代码)，高精度算法，超级a+b!!!（另外附上LCT写法，值得一看！）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

评论列表共有 4 条评论

发表评论取消回复