Reskyd

用户名：a756256994

访问量：15502

签　名：

无事勿扰

等　　级
排　　名	922
经　　验	3476
参赛次数	7
文章发表	5
年　　龄	18
在职情况	学生
学　　校
专　　业	计科

　　自我简介：

铁牌选手/数论只会骗子/数据结构只会暴力

TA的其他文章

用筛法求之N内的素数。 -题解(C++代码)，普通写法，筛法，欧拉筛法全讲解
浏览：1289

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

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

　　作者: Reskyd　　　　发表时间：2019-06-12 00:23:13 浏览：844　|　评论：3　

原题链接：[竞赛入门]简单的a+b

# 这是本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分

14 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

山山山山

这……………………

2022-03-30 17:50:13

jerry3128

我能理解你的想法：https://blog.dotcpp.com/a/63571

2019-12-06 17:15:29

不用编译

要是能讲解下第二个思路就好了~

2019-06-12 10:03:27

Reskyd

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

母牛的故事（C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-自由落体问题（C语言代码）

Minesweeper （C语言描述，蓝桥杯）

愚蠢的摄影师（C++代码）

时间转换（C语言代码）

Reskyd

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

母牛的故事 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

愚蠢的摄影师 （C++代码）

时间转换 （C语言代码）

母牛的故事（C语言代码）

　　评论区

C语言训练-自由落体问题（C语言代码）

愚蠢的摄影师（C++代码）

时间转换（C语言代码）