NVIDIA RTX wallpaper
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/