刷题记录:牛客NC16539&&牛客NC21181(表达式求值的一些事)

首先是牛客NC16539

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。
输入:
1+1234567890*1
输出:
7891

首先这道题是NOIP普及组的一道题,思维复杂度也不大,一看题目就有了一种比较显然的做法:因为只有乘号和加号,因此这个表达式肯定符合这么的一种形式即数字+符号为组的重复序列,因此我们只要记录乘号的组数,那么乘法的运算就是当前组数的数字*下一组数的数字,然后将前面的数字清空(因为可能有连乘的存在,后面的数字要保留),最后累加一下就解决了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
char c[1000005];
ll a[1000005];int sum=0;
int main() {
	sum++;
	while(c[sum]!='\n') {
		sum++;
		cin>>a[sum];
		a[sum]%=10000;
		c[sum]=getchar();
	}
	for(int i=sum;i>=1;i--) {
		if(c[i]=='*') {
			a[i]*=a[i+1];
			a[i]%=10000;
			a[i+1]=0;
		}
	}
	ll ans=0;
	for(int i=1;i<=sum;i++) {
		ans+=a[i];
		ans%=10000;
	}
	cout<<ans<<endl;
	return 0;
}

是不是觉得很好,但是当我在做下一道进阶题的时候,运用这种思想却发生了奇怪的事情

看这道进阶题

第一行，一个整数T (1≤T≤100000)，表示案例的个数。
接下来的T行，每行一个字符串（长度小于等于100），字符串仅由0-9、+、-、*、/、^、!字符组成，数字表示一个数值，范围为[0,9]，且数字不存在前导零，其他符号表示一种运算规则，规则的描述如下：
+：数字1 +数字2 =两个数字之和，+号的优先级为1
-：数字1 -数字2 =两个数字之差，-号的优先级为1
*：数字1 *数字2 =两个数字之积，*号的优先级为2
/：数字1 /数字2 =两个数字之商（舍去小数），/号的优先级为2
^：数字1 ^数字2 =数字1的数字2次方，^号的优先级为3
!：数字1 ! =数字1的阶乘，!号的优先级为4
按照优先级从高到低的顺序依次计算，同级运算时，从左到右依次计算。
输入保证对于每个字符串，满足上述条件，一行输入，以换行符结束。保证式子的表达式语义正确。特别的，一切数值计算均受限于模65536的数域，即每一步运算都要对65536取模，取模的规则同C语言规范。同时，任意数的0次方等于1。

思路:
我运用了之前的经验然后搞出了下面这个代码:具体思路就是先读一遍,因为阶乘的形式不符合数字+符号+数字的格式,所以我先把阶乘计算好直接使用数字代替了,保证它符合之前只有乘号和加号的形式,然后再枚举一遍,计算^的值,这样的话就只剩下乘法除法和加减法了,基本上就等同于之前的那道题了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
char c[100000];ll a[100000];
ll aa[100000];char cc[100000];
ll mod=65536;ll f[65536];
ll power(ll x,ll y){
	if(y==0)return 1;
    ll sum=1;
    while(y){
    	if(y&1){
        	sum=sum*x%mod;
        }
        x=x*x%mod;
        y=y>>1;
    }
    return sum;
}
int main() {
	int T;
	cin>>T;
	f[0]=1;
	for(int i=1;i<mod;i++) f[i]=f[i-1]*i%mod;
	while(T--) {
		memset(c,'\0',sizeof(0));
		memset(cc,'\0',sizeof(0));
		memset(a,0,sizeof(a));
		memset(aa,0,sizeof(aa));
		ll sum=0;ll sum2=0;
		while(c[sum]!='\n') {
			sum++;
			scanf("%d",&a[sum]);
			a[sum]%=mod;
			c[sum]=getchar();
			while(c[sum]=='!') {
				a[sum]=f[a[sum]];
				a[sum]%=mod;
				c[sum]=getchar();
			}
		}
		ll n=1;
		while(n<=sum) {
			sum2++;
			aa[sum2]=a[n];
			aa[sum2]%=mod;
			cc[sum2]=c[n];
			while(cc[sum2]=='^') {
				aa[sum2]=power(aa[sum2],a[n+1]);
				aa[sum2]%=mod;
				n++;
				cc[sum2]=c[n];
			}
			n++;
		}
		bool flag=false; 
		for(int i=1;i<=sum2;i++) {
			if(cc[i]=='-') {
				aa[i+1]=-aa[i+1];
			}
			if(cc[i]=='*') {
				aa[i+1]*=aa[i];
				aa[i]=0;
				aa[i+1]%=mod;
			}else if(cc[i]=='/') {
				if(aa[i+1]==0) {
					cout<<"ArithmeticException"<<endl;
					flag=true;
					break;
				}else {
					aa[i+1]=aa[i]/aa[i+1];
					aa[i+1]%=mod;
					aa[i]=0;
				}
			}
		}
		if(flag==false) {
			ll ans=0;
			for(int i=1;i<=sum2;i++) {
				ans+=aa[i];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

然而交上去发现竟然T了一个点,得了66.66分,一看题解发现是用分治写的,唉没想到啊,还是分治大法NB啊,然后我就采用了分治方法冲了一下
分治的代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
const int mod=65536;
int f[mod];
int power(int x,int y){
	if(y==0)return 1;
    ll sum=1;
    while(y){
    	if(y&1){
        	sum=sum*x%mod;
        }
        x=x*x%mod;
        y=y>>1;
    }
    return sum;
}
string a;
int toNum(int l,int r) {
	int sum=0;
	for(int i=l;i<=r;i++) {
		sum=sum*10+a[i]-'0';
	}
	return sum;
}
int flag=0;
int calc(int l,int r) {
	int pos1=-1,pos2=-1,pos3=-1,pos4=-1;
	for(int i=l;i<=r;i++) {
		if(a[i]=='+'||a[i]=='-') pos1=i;
		else if(a[i]=='*'||a[i]=='/') pos2=i;
		else if(a[i]=='^') pos3=i;
		else if(a[i]=='!') pos4=i;
	}
	if(pos1==-1&&pos2==-1&&pos3==-1&&pos4==-1) return toNum(l,r);
	else if(pos1!=-1) {
		if(a[pos1]=='+') return (calc(l,pos1-1)+calc(pos1+1,r))%mod;
		else return (calc(l,pos1-1)-calc(pos1+1,r))%mod;
	}
	else if(pos2!=-1) {
		if(a[pos2]=='*') return (calc(l,pos2-1)*calc(pos2+1,r))%mod;
		else {
			if(calc(pos2+1,r)==0) flag=1;
			else return (calc(l,pos2-1)/calc(pos2+1,r))%mod;
		}
	}
	else if(pos3!=-1) {
		return power(calc(l,pos3-1),calc(pos3+1,r));
	}
	else if(pos4!=-1) {
		int aa=calc(l,pos4-1);
		return f[aa];
	}
	return 0;
}
int main() {
	int T;cin>>T;
	f[0]=1;
	for(int i=1;i<mod;i++) f[i]=f[i-1]*i%mod;
	while(T--) {
		cin>>a;flag=0;
		int ans=calc(0,a.size()-1);
		if(flag==0) cout<<ans<<endl;
		else cout<<"ArithmeticException"<<endl;
	}
	return 0;
}

然后最奇怪的地方出现了,当我用分块的方法去做之前的那道题的时候(也就是只有加法和乘法的那道题),发现竟然又T掉了两个点,我直接???,代码如下方

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
const int mod=10000;
string a;
ll toNum(ll l,ll r) {
	int sum=0;
	for(int i=l;i<=r;i++) {
		sum=sum*10+a[i]-'0';
	}
	return sum;
}
int flag=0;
ll calc(ll l,ll r) {
	int pos1=-1,pos2=-1;
	for(int i=l;i<=r;i++) {
		if(a[i]=='+') pos1=i;
		else if(a[i]=='*') pos2=i;
	}
	if(pos1==-1&&pos2==-1) return toNum(l,r);
	else if(pos1!=-1) {
		if(a[pos1]=='+') return (calc(l,pos1-1)+calc(pos1+1,r))%mod;
	}
	else if(pos2!=-1) {
		if(a[pos2]=='*') return (calc(l,pos2-1)*calc(pos2+1,r))%mod;
	}
	return 0;
}
int main() {
	f[0]=1;
	cin>>a;flag=0;
	ll ans=calc(0,a.size()-1)%mod;
	if(flag==0) cout<<ans<<endl;
	else cout<<"ArithmeticException"<<endl;
	return 0;
}

在思考了很久并且在某古上求助的帮助下,我明白了问题的所在性,这个问题在于之前的那道分治算法并不是完美的,他每次都是只枚举到符号的最后一位,如果遇到数据比较卡的情况,比如1+1+1+1+...+1,就会被卡到n^2的情况,这个时候就要怪之前的数据没有卡这种情况了,这时候我们就需要rand函数来随性性优化我们的查找算法(类似于一种快速排序的方法)

关于rand函数
一般的 rand()%(b-a+1)+a ; 就表示 a~b 之间的一个随机整数。(两边都是闭区间)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <time.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
const int mod=10000;
string a;int jia[100000],cheng[100000];
ll toNum(ll l,ll r) {
	int sum=0;
	for(int i=l;i<=r;i++) {
		sum=sum*10+a[i]-'0';
	}
	return sum;
}
int flag=0;
ll calc(ll l,ll r) {
	srand((int)time(0));
	int num1=0,num2=0;
	for(int i=l;i<=r;i++) {
		if(a[i]=='+'){
			num1++;jia[num1]=i;
		}
		else if(a[i]=='*') {
			num2++;cheng[num2]=i;
		}
	}
	if(num1==0&&num2==0) return toNum(l,r);
	else if(num1!=0) {
		int rnd=jia[rand()%(num1-1+1)+1];
//		cout<<"jia"<<" "<<rnd<<endl;
		return (calc(l,rnd-1)+calc(rnd+1,r))%mod;
	}
	else if(num2!=0) {
		int rnd=cheng[rand()%(num2-1+1)+1];
//		cout<<"cheng"<<" "<<rnd<<endl;
		return (calc(l,rnd-1)*calc(rnd+1,r))%mod;
	}
	return 0;
}
int main() {
	cin>>a;int jN=0,cN=0;
	flag=0;
	ll ans=calc(0,a.size()-1)%mod;
	if(flag==0) cout<<ans<<endl;
	else cout<<"ArithmeticException"<<endl;
	return 0;
}

然后我们就会发现成功的AC啦!!