题解 P1557 【Kruscal的加法】
吹雪吹雪吹
2018-03-07 20:21:07
## ~~最小生成树~~Kruscal的加法
本蒟蒻写得很粗鲁，请dalao见谅。
AC须准备：
可以不考虑负数的高精度（加法，乘法，减法），我喜欢叫它Int
Int ans1,ans_1; ans1记录+x，ans_1记录-x
接下来：
把数字按照不同表示方法拿下来，累加到ans1或ans_1
比较ans1与ans_1的大小，处理后输出。
具体请参考代码：
```cpp
//我喜欢把某一部分的注释写在那一部分下面
#include<cstdio>
#include<cstring>
#include<algorithm>
#define TT 10000
using namespace std;
char s[2005];
class Int
{
public:
int a[505],len;
Int()
{
memset(a,0,sizeof(a));
len=0;
}
Int(int x)
{
memset(a,0,sizeof(a));
len=0;
while(x)
{
a[++len]=x%TT;
x/=TT;
}
}
Int operator +(Int b)
{
Int c;
c.len=max(len,b.len);
for(int i=1;i<=c.len;++i)
{
c.a[i]+=a[i]+b.a[i];
c.a[i+1]=c.a[i]/TT;
c.a[i]%=TT;
}
if(c.a[c.len+1])
c.len++;
return c;
}
//高精度加法不解释
Int operator *(Int b)
{
Int c;
c.len=len+b.len;
for(int i=1;i<=len;++i)
{
for(int j=1;j<=b.len;++j)
{
c.a[i+j-1]+=a[i]*b.a[j];
c.a[i+j]+=c.a[i+j-1]/TT;
c.a[i+j-1]%=TT;
}
}
while(!c.a[c.len])
c.len--;
return c;
}
//高精度乘法不解释
Int operator -(const Int b)
{
Int c;
c.len=max(len,b.len);
for (int i=1;i<=c.len;i++)
{
c.a[i]+=a[i]-b.a[i]+TT;
c.a[i+1]+=c.a[i]/TT-1;
c.a[i]%=TT;
}
while (c.len>1&&!c.a[c.len]) c.len--;
return c;
}
//高精度减法不解释
bool operator <(Int b)const
{
if(b.len>len)
return true;
else if(len>b.len)
return false;
for(int i=len;i>0;--i)
{
if(b.a[i]>a[i])
return true;
if(b.a[i]<a[i])
return false;
}
return false;
}
//小于不解释
void write()
{
printf("%d",a[len]);
for(int i=len-1;i>=1;--i)
printf("%04d",a[i]);
printf("\n");
}
//输出
}ans1,ans_1;
//ans1记录+x，ans_1记录-x
void ToInt64(int &i)
{
Int ret=0,cs=0,p=10;
int f=1;
if(s[i]=='-')
f=-1;
if(s[i+1]=='(')
{
//如果按+(2)33表达
i+=2;
while(s[i]>='0'&&s[i]<='9')
{
Int res=(int)s[i]-'0';
cs=cs*p+res,++i;
}
//拿下括号内数字
i++;
while(s[i]>='0'&&s[i]<='9')
{
Int res=(int)s[i]-'0';
ret=ret*p+res,++i;
}
//取走要加上的数字
Int c=ret*cs;
//这次运算的结果
if(f==-1)
ans_1=ans_1+c;
else
ans1=ans1+c;
}
else if(s[i+1]>='0'&&s[i+1]<='9')
{
//如果直接按照+233表达
//这段里面有个防抄袭用的"错误"
i++;
while(s[i]>='0'&&s[i]<='9')
{
Int res=(int)s[i]-'0';
ret=ret*p+res,++i;
}
//取走数字
int c=ret;
if(f==-1)
ans_1=ans_1+c;
else
ans1=ans1+c;
}
else
{
//如果是+++233的形式
i++,cs=1;
Int res=1;
while(s[i]=='-'||s[i]=='+')
{
cs=cs+res,++i;
}
//数一下符号个数
while(s[i]>='0'&&s[i]<='9')
{
Int res=(int)s[i]-'0';
ret=ret*p+res,++i;
}
//拿走数字
Int c=ret*cs;
if(f==-1)
ans_1=ans_1+c;
else
ans1=ans1+c;
}
//话说+233与+++233是可以并到一起的，这里是我写的过于粗鲁了
}
int main()
{
//不要在luogu配文件！自行遮蔽
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
//不要在luogu配文件！自行遮蔽
scanf("%s",s+1);
int i=1;
while(s[i])
ToInt64(i);
if(!(ans1<ans_1)&&!(ans_1<ans1))
{
printf("0");
}
//如果Σx>0=Σx<0，输出0
else if(ans1<ans_1)
{
ans_1=ans_1-ans1;
printf("-");
ans_1.write();
}
//如果减数大于被减数，输出一个负号以及ans_1-ans1
else
{
ans1=ans1-ans_1;
ans1.write();
}
//被减数大于减数，直接输出ans1-ans_1
return 0;
}
```