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