duck可不必了解我

目录

  • 莫队算法:(orz)
    • 表达式求值(stack)

莫队算法:(orz)

  • 分块 sqrt(n)块(优化询问)
  • 离线询问排序
  • Add、Sub函数
    求区间和之乱打的板子:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int n,m,siz,res=0;
int a[N],ans[N];
struct node {
     
	int r,l,id;
} q[N];
bool cmp(node a,node b) {
     
	int t1 = a.l/siz;
	int t2 = b.l/siz;
	if(t1==t2) return a.r<b.r;
	return t1<t2;
}
//根据题意:
/*void add(int pos) {
	res+=a[pos];
}
void sub(int pos) {
	res-=a[pos];
}*/
int main() {
     
	cin>>n>>m;
	siz = sqrt(n);
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=m; i++) {
     
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int r=0,l=1;
	for(int i=1; i<=m; i++) {
     
		while(q[i].l>l) res-=a[l++];
		while(q[i].l<l) res+=a[--l];
		while(q[i].r>r) res+=a[++r];
		while(q[i].r<r) res-=a[r--];
		//cout<
		ans[q[i].id] = res;
	}
	for(int i=1; i<=m; i++)
		cout<<ans[i]<<" ";
	return 0;
}

表达式求值(stack)

给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。

输入
输入仅有一行,为需要你计算的表达式,表达式中只包含数字、加法运算符“+”和乘法运算符“*”,且没有括号,所有参与运算的数字均为 0 到 231-1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。
输出
输出只有一行,包含一个整数, 表示这个表达式的值。 注意: 当答案长度多于 4 位时,请只输出最后 4 位,前导 0 不输出。

样例输入
1+1000000003*1
样例输出
4

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const int mod = 10000;
stack<int> q;//先进后出
int main() {
     
	int n,x;
	char ch;
	scanf("%d",&n);
	n %=mod;
	q.push(n);
	while(cin>>ch>>x) {
     
		if(ch=='*') {
     
			n = q.top();
			q.pop();
			q.push(n*x%mod);
		} else	q.push(x);

	}
	int ans=0;
	while(!q.empty()) {
     
		ans+=q.top();
		q.pop();
	}
	printf("%d",ans%mod);
	return 0;
}

ooooo

你可能感兴趣的