LuoguP1557 Kruscal的加法 题解
题目Link
就是这道题，做了我整整一天！
看到题目，首先想到的就是：就这？就这一道大水题也能是绿？然后十分钟写完代码，提交……
果不其然，绿题不是白绿的，看了一眼数据和讨论，又得写高精了……
先附上非高精代码：
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
LL now;
LL tim;
char s[10000];
int k;
LL ans=0;
int main()
{
cin>>s;
for(int i=0;i<strlen(s);i)
{
k=1;
if(s[i]=='+')
{
k=1;
if(s[i+1]=='+')
{
tim=0;
while(s[i]=='+')
i++,tim++;i--;
}
i++;
}
if(s[i]=='-')
{
k=0;
if(s[i+1]=='-')
{
tim=0;
while(s[i]=='-')
i++,tim++;i--;
}
i++;
}
if(s[i]=='('){
i++;
tim=0;
while(s[i]>='0'&&s[i]<='9'){
tim=tim*10+s[i]-'0';
i++;
}
i++;
}
now=0;
while(s[i]>='0'&&s[i]<='9'){
now=now*10+s[i]-'0';
i++;
}
if(tim==0) tim=1;
if(k==1){
ans+=tim*now;
}
else{
ans-=tim*now;
}
tim=0;
}
printf("%lld\n",ans);
return 0;
}
从这份代码可以看出，对于输入字符串是以 ++a 或 +(n)a 的类型为一个板块输入并进行运算, tim 存入 +/- 的个数或者括号内的数字，代表乘数， now 代表 +/- 或括号后的数字，即代表被乘数，之后将 tim 与 now 相乘加入 ans 即可。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
char s[20005];
int now[20005];
int t=0;
int tim;
int timm[20005];
int tt=0;
int k;
int ans[20005];
int c[20005];
int nb=0;
void w1(int m)// 加法运算
{
for(int i=1;i<=max(m,ans[0]);i++)
{
ans[i]=ans[i]+c[i];
ans[i+1]+=ans[i]/10;
ans[i]=ans[i]%10;
}ans[0]=max(m,ans[0]);
if(ans[max(m,ans[0])+1]) ans[0]++;
}
void w2(int m)// 减法运算
{
if(ans[0]<m||ans[0]==m&&ans[ans[0]]<c[m]||ans[0]==m&&ans[ans[0]]==c[m]&&ans[ans[0]-1]<c[m-1]||ans[0]==m&&ans[ans[0]]==c[m]&&ans[ans[0]-1]==c[m-1]&&ans[ans[0]-2]<c[m-2]) //暴力地判断减数和被减数的大小，下同；
{
ans[10000]=1;
for(int i=1;i<=max(m,ans[0]);i++)
{
c[i]-=ans[i];
if(c[i]<0){
c[i]+=10;
c[i+1]--;
}
}
ans[0]=max(m,ans[0]);
for(int i=1;i<=ans[0];i++){
ans[i]=c[i];
}
}
else
for(int i=1;i<=max(m,ans[0]);i++)
{
ans[i]-=c[i];
if(ans[i]<0){
ans[i]+=10;
ans[i+1]--;
}
}
}
void work1() // +++a的情况
{
memset(c,0,sizeof(c));
int m=t;
for(int i=1;i<=m;i++)
{
c[i]+=now[i]*tim;
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
}
m++;
while(c[m]!=0)
{
c[m+1]=c[m]/10;
c[m]=c[m]%10;
m++;
}m--;
while(c[m]==0) m--;
if(k==1)
{
if(ans[10000]==1){
int flag=0;
if(ans[0]<m||ans[0]==m&&ans[ans[0]]<c[m]||ans[0]==m&&ans[ans[0]]==c[m]&&ans[ans[0]-1]<c[m-1]||ans[0]==m&&ans[ans[0]]==c[m]&&ans[ans[0]-1]==c[m-1]&&ans[ans[0]-2]<c[m-2])
flag=1;
w2(m);
if(flag==1) ans[10000]=0;
}
else
w1(m);
}
if(k==0)
{
if(ans[10000]==1){
w1(m);
}
else
w2(m);
}
while(ans[ans[0]]==0) ans[0]--;
}
void work2() // +(n)a 的情况
{
memset(c,0,sizeof(c));
for(int i=1;i<=t;i++)
for(int j=1;j<=tt;j++)
{
c[i+j-1]+=now[i]*timm[j];
}
for(int i=1;i<=t+tt;i++)
{
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
}
int m=t+tt+1;
while(c[m]!=0)
{
c[m+1]=c[m]/10;
c[m]=c[m]%10;
m++;
}m--;
while(c[m]==0) m--;
if(k==1)
{
if(ans[10000]==1){
int flag=0;
if(ans[0]<m||ans[0]==m&&ans[ans[0]]<c[m]||ans[0]==m&&ans[ans[0]]==c[m]&&ans[ans[0]-1]<c[m-1]||ans[0]==m&&ans[ans[0]]==c[m]&&ans[ans[0]-1]==c[m-1]&&ans[ans[0]-2]<c[m-2])
flag=1;
w2(m);
if(flag==1) ans[10000]=0;
}
else{
w1(m);
}
}
if(k==0)
{
if(ans[10000]==1){
w1(m);
}
else
w2(m);
}
while(ans[ans[0]]==0) ans[0]--;
}
int main()
{
cin>>s;
for(int i=0;i<strlen(s);i)
{
k=1;
tim=0;
if(s[i]=='+') //输入加号及个数
{
k=1;
if(s[i+1]=='+')
{
tim=0;
while(s[i]=='+')
i++,tim++;i--;
}
i++;
}
if(s[i]=='-') //输入减号及个数
{
k=0;
if(s[i+1]=='-')
{
tim=0;
while(s[i]=='-')
i++,tim++;i--; //由于n<=2000，故在这种情况时，tim<=2000,直接用int存即可；
}
i++;
}
tt=0;
if(s[i]=='('){ //输入乘数
i++;
while(s[i]>='0'&&s[i]<='9'){
i++;
}i--;
while(s[i]>='0'&&s[i]<='9'){
timm[++tt]=s[i]-'0';
i--;
}i++;
while(s[i]>='0'&&s[i]<='9'){
i++;
}
i++;
}
while(s[i]>='0'&&s[i]<='9'){ //输入被乘数
i++;
}i--;
t=0;
while(s[i]>='0'&&s[i]<='9'){
now[++t]=s[i]-'0';
i--;
}i++;
while(s[i]>='0'&&s[i]<='9'){
i++;
}
if(tim==0&&tt==0) tim++;
if(tim){ //根据不同输入类型，进行不同运算
work1();
}
else{
work2();
}
}
while(ans[ans[0]]==0) ans[0]--;//ans[0]代表答案长度
if(ans[0]<1) ans[0]=1; //答案等于0时，ans[0]会减为0，进行特判；
if(ans[0]==1&&ans[1]==0){ //答案等于0时，不能输出-0，直接进行特判；
printf("0\n");
return 0;
}
if(ans[10000]==1) printf("-");
for(int i=ans[0];i>=1;i--)
printf("%d",ans[i]);
printf("\n");
return 0;
}
再来看这份AC代码，输入与上面非高精代码相同，把运算换成高精，但多了亿点点细节。
- 首先，要把数字作为一个数组输入，为了保证数组顺序，先让
i跑到下一个非数字字符，再从后往前跑，把数字存入，然后再让i跑回去准备下一次的读取； - 其次，高精运算涉及到负数，用
ans[10000]来存储当前得数的正负，0代表正，1代表负，在进行加减运算时，通过判断当前得数的正负，巧妙地把加减运算互相转化； - 最后，要注意输出时，要把得数前多余的
0删掉，同时不存在-0，要进行特判；
希望管理通过QwQ
