目錄
- 莫隊演算法：（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<<res<<endl;
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262998.html
標籤：其他
下一篇：[HNOI2003]激光炸彈