STL习题+高精加思维导图_编号c9045375-TreeMind树图

查看详情

STL习题+高精加

树图思维导图提供 STL习题+高精加在线思维导图免费制作，点击“编辑”按钮，可对 STL习题+高精加进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3b65cc57efab27cd5c0f1855d0e405a6

STL习题+高精加 slt

举报/反馈

思维导图大纲

STL习题+高精加思维导图模板大纲

作业

P3613 【深基15.例2】寄包柜

这一题如果不是空间太大，其实可以用数组写，现在我们只能用STL的容器来写

map+pair

#include<bits/stdc++.h> using namespace std; map<pair<int,int>,int> ma; int main(){ int n,m,w,x,y,z; cin>>n>>m; while(m--){ scanf("%d",&w); if(w==1){ scanf("%d%d%d",&x,&y,&z); ma[{x,y}]=z; } else{ scanf("%d%d",&x,&y); printf("%d\n",ma[{x,y}]); } } return 0; }

map嵌套

#include<bits/stdc++.h> using namespace std; map<int,map<int,int> > ma; int main(){ int n,m,w,x,y,z; cin>>n>>m; while(m--){ scanf("%d",&w); if(w==1){ scanf("%d%d%d",&x,&y,&z); ma[x][y]=z; } else{ scanf("%d%d",&x,&y); printf("%d\n",ma[x][y]); } } return 0; }

这里要注意，map嵌套只能是map< ,map< , > >,不能是map<map< , >, >。第一种相当于键-值-值，而第二种是键-键-值，而map中不能出现相同的键

vector+resize

resize可以理解为重新开辟空间，利用这个特性，我们就可以质地硬需要的大小从而避免爆掉

#include<bits/stdc++.h> using namespace std; int main(){ int n,m,w,x,y,z; cin>>n>>m; vector<vector<int> > v(n); while(m--){ scanf("%d",&w); if(w==1){ scanf("%d%d%d",&x,&y,&z); if(v[x].size()<y+1) v[x].resize(y+1); v[x][y]=z; } else{ scanf("%d%d",&x,&y); printf("%d\n",v[x][y]); } } return 0; }

P2234 [HNOI2002]营业额统计

set的lower_bound函数可以很好的应对我们这一题，如果是第一个数，直接插入到set里。之后，每次输入一个新的数x后，通过lowerbound操作找到set中大于等于x的第一个数的位置now。若now这个位置上的数等于x，显然最小波动值为0，同时也不需要再插入一个x放到set里了。否则，说明这个数大于x，通过set的特性可以很轻松的找到这个数的前驱，也就是小于x的第一个数的位置last, 将last和now这两个位置上的数分别减去x，对绝对值取个min就好了。此时要将x插入到set中以便后续数据对比。

#include<bits/stdc++.h> using namespace std; set<int> s; int cnt; int main(){ int n,x; cin>>n; cin>>x; s.insert(x); cnt+=x; s.insert(-1e9); s.insert(1e9); for(int i=1;i<n;i++){ cin>>x; if(x>*(--s.end())) cnt+=abs(*(--s.end())-x); else{ if(*(s.lower_bound(x))!=x){ int minn=min(abs(*(--s.lower_bound(x))-x),abs(*(s.lower_bound(x))-x)); cnt+=minn; } } s.insert(x); } cout<<cnt; return 0; }

本课

高精度可以处理那些数据超过long long范围的数的计算操作

本课讲的高精加，就是用vector来操作的，先用字符串输入进数，然后存入vector。方法:两个数的和+进位

#include<bits/stdc++.h> using namespace std; vector<int> add(vector<int> &A,vector<int> &B){ vector<int> C; int t=0;//t表示进位，刚开始e for(int i=0;i<max(A.size(),B.size());i++){ if(i<A.size()) t+=A[i]; if(i<B.size()) t+=B[i]; C.push_back(t%10); t/=10;//t进位 } if(t) C.push_back(t); while(C.size()>1 && C.back()==0) C.pop_back(); return C; } int main(){ string a,b; cin>>a>>b;//1234 5678 vector<int> A,B,C; for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//A=[4.3.2.1] for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0'); C=add(A,B); for(int i=C.size()-1;i>=0;i--){ printf("%d",C[i]); } return 0; }