1204 字
6 分钟
【洛谷】题解 - P1797 【克鲁斯的加减法_NOI导刊2010提高(05)】

这题是@laybxc这位神犇推荐给我写的。从开始写到AC前后时间跨度一个星期,这是我第一次认认真真写高精,100+的总提交次数应该有15次是我提交的,因为实在太毒瘤了,感谢@laybxc提供的高精度模板让我找出了原本我写的代码中的错误,今天终于AC了,所以发一篇题解庆祝一下。


这道题本质是道模拟题(第一次看的时候还是黄题,现在居然蓝了),主要做法就是遍历字符串并找出每一项的值,然后加起来,用int可以过60分,long long和int128也都只能过60分,显然剩下40分必须用高精了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//因为我太弱了,不会写高精度类,只会用struct
//而且写高精度算法的经验比较少,所以高精写的比较丑
struct BigInt	
{
    int ch;
    int x[300];
};
inline void clear(BigInt& x);		//初始化BigInt
inline BigInt read();				//读入BigInt(好像这题并没有用)
inline int Compare(BigInt a, BigInt b);//比较函数
inline BigInt Plus(BigInt a, BigInt b);//高精加
inline BigInt Minus(BigInt a, BigInt b);//高精减
inline BigInt Multi(BigInt a, BigInt b);//高精乘
inline BigInt Int_to_BigInt(int x);//把int转换成BigInt
inline void clear(BigInt& x)
{
    memset(x.x, 0, sizeof(x.x));
    x.ch = 1;
}
inline BigInt read()
{
    BigInt x;
    clear(x);
    char ch = getchar();
    while(!isdigit(ch) && ch != '-')
        ch = getchar();
    if(ch == '-')
    {
        x.ch = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x.x[++x.x[0]] = ch - '0';
        ch = getchar();
    }
    for(int i=1; i<=x.x[0]/2; i++)
    {
        swap(x.x[i], x.x[x.x[0]-i+1]);
    }
    return x;
}
inline BigInt Int_to_BigInt(int x)
{
    BigInt c;
    clear(c);
    if(x < 0)
    {
        c.ch = -1;
        x = -x;
    }
    if(x == 0) c.x[0]++;
    while(x)
    {
        c.x[++c.x[0]] = x % 10;
        x /= 10;
    }
    return c;
}
inline int Compare(BigInt a, BigInt b)
{
    if(a.x[0] > b.x[0]) return 1;
    if(a.x[0] < b.x[0]) return -1;
    for(int i=a.x[0]; i; i--)
    {
        if(a.x[i] > b.x[i]) return 1;
        if(a.x[i] < b.x[i]) return -1;
    }
    return 0;
}
inline BigInt Plus(BigInt a, BigInt b)
{
    BigInt c;
    clear(c);
    if(a.ch == 1 && b.ch == -1)
    {
        b.ch = 1;
        return Minus(a, b);
    }
    if(a.ch == -1 && b.ch == 1)
    {
        a.ch = 1;
        return Minus(b, a);
    }
    if(a.ch == -1 && b.ch == -1)
    {
        c.ch = -1;
    }
    int k = a.x[0] > b.x[0] ? a.x[0] : b.x[0], g = 0;
    for(int i=1; i<=k; i++)
    {
        c.x[i] = a.x[i] + b.x[i] + g;
        g = c.x[i] / 10;
        c.x[i] %= 10;
    }
    if(g) c.x[++k] = g;
    c.x[0] = k;
    return c;
}
inline BigInt Minus(BigInt a, BigInt b)
{
    BigInt c;
    clear(c);
    if(a.ch == -1 && b.ch == -1)
    {
        a.ch = 1;
        b.ch = 1;
        return Minus(b, a);
    }
    if(a.ch == -1 && b.ch == 1)
    {
        a.ch = 1;
        c = Plus(a, b);
        c.ch = -1;
        return c;
    }
    if(a.ch == 1 && b.ch == -1)
    {
        b.ch = 1;
        return Plus(a, b);
    }
    int flag = Compare(a, b);
    if(flag == 0)
    {
        c.x[0] = 1;
        return c;		
    }
    if(flag == 1)
    {
        int k = a.x[0];
        for(int i=1; i<=k; i++)
        {
            if(a.x[i] < b.x[i])
            {
                a.x[i+1]--;
                a.x[i] += 10;
            }
            c.x[i] = a.x[i] - b.x[i];
        }
        while(c.x[k] == 0) k--;
        c.x[0] = k;
        return c;
    }
    else
    {
        int k = b.x[0];
        c.ch = -1;
        for(int i=1; i<=k; i++)
        {
            if(b.x[i] < a.x[i])
            {
                b.x[i+1]--;
                b.x[i] += 10;
            }
            c.x[i] = b.x[i] - a.x[i];
        }
        while(c.x[k] == 0) k--;
        c.x[0] = k;
        return c;
    }
}
inline BigInt Multi(BigInt a, BigInt b)
{
    BigInt c;
    clear(c);
    c.ch = a.ch * b.ch;
    int ka = a.x[0], kb = b.x[0], k = ka + kb + 1;
    for(int i=1; i<=ka; i++)
    {
        for(int j=1; j<=kb; j++)
        {
            c.x[i+j-1] += a.x[i] * b.x[j];
            c.x[i+j] += c.x[i+j-1] / 10;
            c.x[i+j-1] %= 10;
        }
    }
    while(!c.x[k]) k--;
    c.x[0] = k;
    return c;
}
inline void print(BigInt x)//打印高精度数
{
    if(x.x[0] == 0) printf("0");
    if(x.ch == -1) printf("-");
    for(int i=1; i<=x.x[0]; i++)
        printf("%d", x.x[x.x[0]-i+1]);
}
const int maxn = 205;
int top, len;
int b[maxn];
BigInt ansx, ans[maxn], tmp;
char a[maxn];
int main()
{
    clear(ansx);
    ansx.x[0] = 1;
    scanf("%s", a+1);
    len = strlen(a+1);
    for(int i=1; i<=len; i++)
    {
        if(i == 1 && (a[i] >= '0' && a[i] <= '9'))
        {	//如果第一个字符属于第一个数,则直接存起来
            int l, r;
            for(l=1; l<=len; l++)
            {
                if(a[l] < '0' || a[l] > '9')
                {
                    r = l-1;
                    break;
                }
            }
            ++top;
            clear(ans[top]);
            ans[top] = Plus(ans[top], Int_to_BigInt(a[1] - '0'));
            for(int j=2; j<=r; j++)
            {
            	clear(tmp);
            	ans[top] = Multi(ans[top], Int_to_BigInt(10));
                ans[top] = Plus(ans[top], Int_to_BigInt(a[j]-'0'));
            }
            continue;
        }
        if(a[i] == '+' || a[i] == '-')
        {	//遇到'+'号或'-'号就处理这一项的值
            char character;
            character = a[i];
            int m, k, l;
            BigInt ax, bx, numc;
            clear(ax);
            clear(bx);
            clear(numc);
            for(int j=i; j<=len; j++)
            {	//找出'+'号或'-'号的个数
                if(a[j] != character)
                {
                    m = j - 1;
                    break;
                } 
                numc = Plus(numc, Int_to_BigInt(1));
            }
            if(a[m+1] == '(')
            {	//处理括号内的数的值
                for(int j=m+2; j<=len; j++)
                {
                    if(a[j] == ')')
                    {
                        k = j-1;
                        break;
                    }
                }
                ax = Plus(ax, Int_to_BigInt(a[m+2] - '0'));
                for(int j=m+3; j<=k; j++)
                {
                	ax = Multi(ax, Int_to_BigInt(10));
                    ax = Plus(ax, Int_to_BigInt(a[j] - '0'));
                }				
            }
            else
            {
                k = m - 1;
                ax = Plus(Int_to_BigInt(0), Int_to_BigInt(1));
                //如果并没有括号则 ax = 1;
            }
            for(int j=k+2; j<=len; j++)
            {	//处理此项剩余部分的值
                if(j == len) l = j;
                if(a[j] < '0' || a[j] > '9')
                {
                    l = j-1;
                    break;
                }
            }
            bx = Plus(bx, Int_to_BigInt(a[k+2] - '0'));
            for(int j=k+3; j<=l; j++)
            {
            	bx = Multi(bx, Int_to_BigInt(10));
                bx = Plus(bx, Int_to_BigInt(a[j] - '0'));
            }
            ++top;
            clear(ans[top]);
            ans[top] = Plus(Int_to_BigInt(0), Int_to_BigInt(1));
            ans[top] = Multi(ans[top], ax);
            ans[top] = Multi(ans[top], bx);
            ans[top] = Multi(ans[top], numc);
            //把符号个数,括号内的数,后的数的值乘起来
            i = l;
            if(character == '-')//如果是'-'号则项取相反数
            	ans[top] = Multi(ans[top], Int_to_BigInt(-1));
        }
    }
    for(int i=1; i<=top; i++) //把每一项的数加起来作为答案输出
    	ansx = Plus(ansx, ans[i]);
    print(ansx);
    return 0;
}
【洛谷】题解 - P1797 【克鲁斯的加减法_NOI导刊2010提高(05)】
https://blog.vonbrank.com/posts/luogu-solution-p1797/
作者
Von Brank
发布于
2018-10-11
许可协议
CC BY-NC-SA 4.0