错题总结

T4(P1981 [NOIP 2013 普及组] 表达式求值)

思路：

我们先遍历整个字符串。

然后对于每个字符，分为两种情况：

是数字：

把他存进num之中。

是符号：

如果这个符号的上一个符号是加号，把这个num放入栈中。如果这个符号的上一个符号是乘号，把st.top()*num放入栈中。

这样就可以保证把所有的乘法先算了一遍，接着把栈求和即可。

AC code:

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int num=0;
char last='+';
stack<int>st;
signed main(){
	cin>>s;
	s+='+';
	for(int i=0;i<s.size();i++){
		if(s[i]>='0'&&s[i]<='9'){
			num=num*10+s[i]-'0';
			num%=10000;
		}
		else{
			if(last=='+'){
				st.push(num%10000);
			}
			else if(last=='*'){
				int t=st.top();
				st.pop();
				st.push((t*num)%10000);
			}
			num=0;
			last=s[i];
		}
	}
	int sum=0;
	while(st.size()){
		sum+=st.top();
		st.pop();
	}
	cout<<sum%10000;
	return 0;
}

T6(P5057 [CQOI2006] 简单题)

思路：

我们可以用树状数组+差分做这道题。

我们要用一个数组c来记录每个点的反转的次数。

每次区间[l,r]反转，我们可以让c[l]++,并让c[r+1]--；

对于每次查询，输出c[i]的前缀和并对2取模（因为反转偶数次等于没反转）。

AC code:

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m;
int c[N],a[N];
int lowbit(int x){
	return x & -x;
}
int get_sum(int x){
	int res=0;
	while(x){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
void modify(int x,int val){
	while(x<=n){
		c[x]+=val;
		x+=lowbit(x);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	while(m--){
		int t,l,r,x;
		cin>>t;
		if(t==1){
			cin>>l>>r;
			modify(l,1);
			modify(r+1,-1);
		}
		else{
			cin>>x;
			cout<<get_sum(x)%2<<endl;
		}
	}
	return 0;
}

8-10 综合测试总结

文章操作

错题总结

T4(P1981 [NOIP 2013 普及组] 表达式求值)

思路：

AC code:

T6(P5057 [CQOI2006] 简单题)

思路：

AC code:

相关推荐

评论

8-10 综合测试总结