8-10 综合测试总结

· · 个人记录

错题总结

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

思路：

我们先遍历整个字符串。

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

  1. 是数字：

    把他存进num之中。

  2. 是符号：

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

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

AC code:

#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:

#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;
}