题目描述
no
样例
1+3*3*3+5*0+1+12345*2
4719
tip:计算答案:24719
算法1
(暴力枚举/字符串) $O(n^2)$
这道题难度竟然是中等,我觉得这道题这么简单还中等,根本用不上栈,只需要把字符串用加号分割最后再把每一个加号分割后的表达式乘好,在加起来即可,但有几点坑:
1.爆int 开longlong
2.需要每次模运算再相乘或相加,因为只要最后4位,%10000即可
3.string类型的数组存把加号拆开的表达式,定义时要在函数外定义,否则爆内存
4.注意处理加号结束的表达式和乘号结束的表达式
注意做完后测我的一组数据/*
*/
答案4092
时间复杂度
n^2
参考文献
no
C++ 代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cctype>
#include<cfloat>
#include<climits>
#include<iomanip>
#include<sstream>
#include<fstream>
#include<cstdlib>
#include<stack>
#include<queue>
#include<deque>
using namespace std;
string a;
string b[100020];
string c="";
long long h=0,ji=1;
int main(){
//freopen("bdsqz.in","r",stdin);
//freopen("bdsqz.out","w",stdout);
cin>>a;
long long lena=a.size(),t=0,total=0;
for(long long i=0;i<lena;i++){
if(a[i]=='+'){
b[t]=c;
//cout<<"1测试1: "<<b[t]<<endl;
t++;
c="";
}else {
c+=a[i];
}
}
if(c!=""){
b[t]=c;
//cout<<"2测试1: "<<b[t]<<endl;
t++;
c="";
}//处理加号结束表达式,也要存入数组
for(long long i=0;i<t;i++){
ji=1;
for(long long j=0;j<b[i].length();j++){
//cout<<1<<endl;
if(b[i].at(j)>='0'&&b[i].at(j)<='9'){
h=h*10+b[i].at(j)-48;
//cout<<"1ok"<<endl;
}else if(b[i].at(j)=='*'){
ji=h*ji%10000;//%运算
//cout<<"1数2: "<<h<<" "<<ji<<endl;
h=0;
}
}
ji=h*ji%10000;h=0;//处理×号结束表达式,继续相乘
//cout<<"2数2: "<<h<<" "<<ji<<endl;
total+=ji;
total=total%10000;
}
cout<<total%10000<<endl;
return 0;
}
/*
476+6214*15657*13691+478*25971*1235+22033*12697+4897*21257*9185*15590*8639*14526+11365+14865+24307*7606*10891+30841*14867+14601*17206*8466+26796+22950+4540*9953+23295*32461+1126*1923+126+16531+2291+23462+23636*2146+2325+14222*27098+6519+14067*23442+20770*26978+10661+13468*27504*18570+18875+11437+6076+23206+3510*19287*24370+24389*1676+9792+27058*19015*15401+8614+16977+11361*23017*213*27605+27549*11039*18099*17725*19415*26514*26165+15927+18242*20474+17127*23463+14049+6791*360+3111+19214*12122+10219*19585*21495+13578*3767*7223+23068+27937+8360*16892+1746+24732*27564
*/
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
没备注啊,看的吃力
2019写的,那是我是pj选手,没水平,所以没有加备注