- 这个OJ一直在做，一些专题题目都很好，从易至难，阶梯上升，很适合像我这样的蒟蒻 =7=
- 这篇是关于其中一个专题训练的题解思路及代码 http://120.78.128.11/Contest.jsp?cid=486
- 所有题面我就不贴了，各位自行去看，链接在上一行 =7=
一、求众数（Map标记+Set）
- 其实数组维护也可以做，但既然是STL训练，就用STL的东西了
- 用map标记数据和出现的次数，然后转入结构体存入map中
- 为什么不直接用set<map<T,T> >的形式 是因为map只能对关键字排序，而我们需要排次数，所以存入set中先转存入结构体
- 然后没啥坑点，结构体自己构造一个排序就行了，如何构造请看另一篇博文
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 int sum,x; 46 bool operator <(const node &b)const{ 47 if(sum == b.sum) 48 return x < b.x; 49 else 50 return sum > b.sum; 51 } 52 }; 53 54 map<int,int >q; 55 set<node>p; 56 set<node>::iterator it; 57 58 int main(){ 59 ios_base::sync_with_stdio(false); 60 cout.tie(0); 61 cin.tie(0); 62 int n,t,x,d,e; 63 while(~scanf("%d",&n)){ 64 q.clear(); 65 p.clear(); 66 while(n--){ 67 scanf("%d",&t); 68 if(t == 1){ 69 scanf("%d",&x); 70 q[x]++; 71 p.insert((node){q[x],x}); 72 } 73 else{ 74 if(!p.empty()){ 75 e = p.begin()->sum; 76 int flag = 0; 77 for(it = p.begin(); it != p.end(); it++){ 78 if(it->sum == e){ 79 if(flag++) 80 printf(" "); 81 printf("%d",it->x); 82 } 83 else 84 break; 85 } 86 puts(""); 87 } 88 } 89 90 } 91 } 92 }
二、营业额统计（Set）
- 这个题用Set中的lower_bound函数直接找就行了 =7=
- 没啥讲的 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 set<int>q; 45 46 int main(){ 47 ios_base::sync_with_stdio(false); 48 cout.tie(0); 49 cin.tie(0); 50 int n; 51 while(~scanf("%d",&n)){ 52 q.clear(); 53 int x; 54 ll sum = 0; 55 while(n--){ 56 scanf("%d",&x); 57 if(q.empty()){ 58 sum += x; 59 q.insert(x); 60 } 61 else{ 62 set<int>::iterator l = --q.lower_bound(x); 63 set<int>::iterator r = q.lower_bound(x); 64 int temp = min(abs(*l - x),abs(*r - x)); 65 sum += temp; 66 q.insert(x); 67 } 68 } 69 printf("%lld\n",sum); 70 } 71 72 return 0; 73 }
三、宠物收养所（Set）
- 和上一题类似，Set::Lower_bound直接搞就行了
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 set<int>q; 45 46 int main(){ 47 ios_base::sync_with_stdio(false); 48 cout.tie(0); 49 cin.tie(0); 50 int n; 51 while(~scanf("%d",&n)){ 52 q.clear(); 53 int t,x; 54 ll sum = 0; 55 while(n--){ 56 scanf("%d%d",&t,&x); 57 if(t == 0){ 58 q.insert(x); 59 } 60 else{ 61 if(q.empty()){ 62 continue; 63 } 64 set<int>::iterator l = --q.lower_bound(x); 65 set<int>::iterator r = q.lower_bound(x); 66 if(r == q.begin()){ 67 sum += abs(*r - x); 68 q.erase(r); 69 } 70 else{ 71 int ll = abs(*l - x); 72 int rr = abs(*r - x); 73 if(ll == rr){ 74 sum += ll; 75 q.erase(l); 76 } 77 else if(ll < rr){ 78 sum += ll; 79 q.erase(l); 80 } 81 else if(ll > rr){ 82 sum += rr; 83 q.erase(r); 84 } 85 } 86 } 87 } 88 printf("%lld\n",sum); 89 } 90 91 return 0; 92 }
四、第二集 你说，你的女朋友就是你的电脑（Stack）
- 无力吐槽标题以及题面 =7=
- Stack模拟一下就行
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 char s[2000010]; 45 46 int main(){ 47 ios_base::sync_with_stdio(false); 48 cout.tie(0); 49 cin.tie(0); 50 while(~scanf("%s",s)){ 51 stack<char>q; 52 char ch; 53 int flag = 1; 54 int len = strlen(s); 55 for(int i = 0; s[i] != '\0'; i++){ 56 ch = s[i]; 57 if(ch == '(' || ch == '{' || ch == '[' || ch == '<'){ 58 q.push(ch); 59 } 60 else{ 61 char tp; 62 if(s[i] == '}') 63 tp = '{'; 64 else if(s[i] == '>') 65 tp = '<'; 66 else if(s[i] == ']') 67 tp = '['; 68 else if(s[i] == ')') 69 tp = '('; 70 if(!q.empty()){ 71 if(q.top() == tp) 72 q.pop(); 73 } 74 else{ 75 flag = 0; 76 break; 77 } 78 } 79 } 80 if(flag){ 81 if(q.empty()) 82 puts("YES"); 83 else 84 puts("NO"); 85 } 86 else{ 87 puts("NO"); 88 } 89 } 90 91 return 0; 92 }
五、Jokes（Map+Queue维护）
- 用一个队列存记得的笑话，然后 map标记一下就行了
- 不过注意的是她能记m天包括当前天，所以存以前的笑话应该是m-1天（开始没注意 =7=）
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 int main(){ 45 ios_base::sync_with_stdio(false); 46 cout.tie(0); 47 cin.tie(0); 48 int n,m; 49 while(~scanf("%d%d",&n,&m)){ 50 int tot = 0,flag = 0; 51 map<int,int>q; 52 queue<int>vis; 53 if(n <= m){ 54 flag = 1; 55 } 56 for(int i = 0; i < n; i++){ 57 int temp; 58 scanf("%d",&temp); 59 if(q[temp] == 0) 60 q[temp] = 1,tot++; 61 if(vis.size() == m-1){ 62 q[vis.front()] = 0; 63 vis.pop(); 64 } 65 vis.push(temp); 66 } 67 printf("%d",tot); 68 } 69 70 return 0; 71 }
六、Log大侠（线段树+离线）
- 据说好像是某年蓝桥杯的题 然后暴力能水60%数据 =7=
- 离线加线段树 不过建树的时候把1标记为2 输出时候减去标记数量 不然1会影响更新操作
- 至于线段树不会离线不懂得话 =7= 后面慢慢讲 这里只讲题解思路
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 const int maxn = 100010; 45 int num[100010]; 46 ll tree[maxn<<2]; 47 int n,m; 48 int l,r; 49 int cnt; 50 51 void build(int x,int l, int r){ 52 if (l == r){ 53 cin >> tree[x]; 54 if (tree[x] == 1){ 55 cnt++; 56 tree[x] = 2; 57 } 58 return; 59 } 60 61 int mid = (l+r)/2; 62 build((x<<1),l,mid); 63 build((x<<1)+1,mid+1,r); 64 tree[x] = tree[(x<<1)]+tree[(x<<1)+1]; 65 } 66 67 void update(int x,int l,int r,int L,int R){ 68 if (tree[x] == (r-l+1)<<1){ 69 return ; 70 } 71 if (l == r){ 72 tree[x] = num[tree[x]]; 73 return; 74 } 75 76 int mid = (l+r)/2; 77 if (R <= mid) 78 update((x<<1),l,mid,L,R); 79 else if (L > mid) 80 update((x<<1)+1,mid+1,r,L,R); 81 else{ 82 update((x<<1),l,mid,L,mid); 83 update((x<<1)+1,mid+1,r,mid+1,R); 84 } 85 tree[x] = tree[(x<<1)]+tree[(x<<1)+1]; 86 } 87 88 int main(){ 89 ios_base::sync_with_stdio(false); 90 cout.tie(0); 91 cin.tie(0); 92 for(int i = 1; i <= maxn; i++) 93 num[i] = (int)(log2(i) + 1); 94 cin >> n >> m; 95 96 build(1,1,n); 97 while(m--){ 98 cin >> l >> r; 99 update(1,1,n,l,r); 100 cout << tree[1] - cnt << endl; 101 } 102 return 0; 103 }
七、哈利什么什么什么的
- 这题没做
- 题目太长了 写了一下 WA了 后面再想吧 =7=
八、LRU算法实现（Map维护+Set）
- 这题没做出来
- 我的思路是两个map标记数据 和 是否存在（因为数据可能为0），然后Set记录是否最近走过，提交上去无情wa了两发
- 我看了大佬的代码，基本都是用三个Map标记。溜了溜了
- 这里就贴一下大佬的AC代码吧：
1 /** 2 rid: 195317 3 user: sandychn 4 time: 2018-07-21 10:40:16 5 result: Accepted 6 */ 7 8 #include <bits/stdc++.h> 9 using namespace std; 10 typedef long long ll; 11 12 struct LRU { 13 map <int, ll> key_value; 14 map <int, int> time_key; 15 map <int, int> key_time; 16 LRU() { 17 clear(); 18 } 19 ~LRU() { 20 } 21 void clear() { 22 key_value.clear(); 23 time_key.clear(); 24 key_time.clear(); 25 } 26 void insert(int time, int key, ll value) { 27 key_value[key] = value; 28 time_key[time] = key; 29 key_time[key] = time; 30 } 31 ll get(int key) { 32 auto it = key_value.find(key); 33 if(it == key_value.end()) 34 return -1; 35 return it->second; 36 } 37 void remove(int key) { 38 auto it_key_time = key_time.find(key); 39 if(it_key_time == key_time.end()) 40 return; 41 int time = it_key_time->second; 42 key_time.erase(it_key_time); 43 key_value.erase(key); 44 time_key.erase(time); 45 } 46 void visit(int key, int time) { 47 auto it_key_time = key_time.find(key); 48 if(it_key_time == key_time.end()) 49 return; 50 int old_time = it_key_time->second; 51 key_time[key] = time; 52 time_key.erase(old_time); 53 time_key[time] = key; 54 } 55 void pop() { 56 if(time_key.empty()) 57 return; 58 int key = time_key.begin()->second; 59 // printf("Element %d has been erased.\n", key); 60 key_time.erase(key); 61 key_value.erase(key); 62 time_key.erase(time_key.begin()); 63 } 64 }; 65 LRU lru; 66 int main() { 67 // freopen("../in.txt", "r", stdin); 68 int n, time, k; 69 ll v; 70 char opt[10]; 71 while(scanf("%d", &n) != EOF) { 72 lru.clear(); 73 for(time = 1; time <= n; ++time) { 74 scanf("%s", opt); 75 if(opt[0] == 'i') { 76 scanf("%d %lld", &k, &v); 77 lru.insert(time, k, v); 78 } else if(opt[0] == 'p') { 79 lru.pop(); 80 } else { 81 scanf("%d", &k); 82 if(opt[0] == 'g') 83 printf("%lld\n", lru.get(k)); 84 else if(opt[0] == 'v') 85 lru.visit(k, time); 86 else if(opt[0] == 'r') 87 lru.remove(k); 88 } 89 } 90 } 91 return 0; 92 }
九、Registration system（Map）
- 进去一看英文题 不想做 ，
- 看了下样例觉得不难，等下做了再写
- 做完回来了map模拟就好 直接看代码吧 =7=
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 int main(){ 45 ios_base::sync_with_stdio(false); 46 cout.tie(0); 47 cin.tie(0); 48 int n; 49 cin>>n; 50 map<string,int>q; 51 while(n--){ 52 string s; 53 cin>>s; 54 if(q[s] == 0){ 55 q[s]++; 56 cout << "OK" << endl; 57 } 58 else{ 59 cout << s << q[s] << endl; 60 q[s]++; 61 } 62 } 63 64 return 0; 65 }
十、统计难题（Map）
- 我是直接用map把输入的每个字符串的前缀全部记录
- 然后直接输出就行
- 如果是每次都去匹配的话应该会TLE
- 值得注意的是这个题的输入格式，中间仅仅换了一行（各位还没见过这种格式输入可以自己先想想）
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 map<string,int>cot; 45 46 int main(){ 47 ios_base::sync_with_stdio(false); 48 cout.tie(0); 49 cin.tie(0); 50 51 char temp[20]; 52 string s; 53 while(1){ 54 getline(cin,s); 55 if(!s[0]) 56 break; 57 MMT(temp); 58 for(int i = 0; i < s.size(); i++){ 59 temp[i] = s[i]; 60 cot[temp]++; 61 } 62 } 63 while(cin>>s){ 64 printf("%d\n",cot[s]); 65 } 66 67 return 0; 68 }
十一、看病要排队（Priority_Queue）
- 又是排队又是STL 肯定就是优先队列啦
- 三个优先队列分别记录三个医生的病人，然后模拟即可
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 int id; 46 int cnt; 47 node(int id,int cnt):id(id),cnt(cnt){} 48 friend operator < (node a,node b){ 49 if(a.cnt == b.cnt){ 50 return a.id > b.id; 51 } 52 return a.cnt < b.cnt; 53 } 54 }; 55 56 int main(){ 57 ios_base::sync_with_stdio(false); 58 cout.tie(0); 59 cin.tie(0); 60 int n; 61 while(cin>>n){ 62 priority_queue<node>j,k,l; 63 int tot = 1; 64 for(int i = 1; i <= n; i++){ 65 string s; 66 int a,b; 67 cin>>s; 68 if(s[0] == 'I'){ 69 cin>>a>>b; 70 node tp(tot++,b); 71 if(a == 1){ 72 j.push(tp); 73 } 74 else if(a == 2){ 75 k.push(tp); 76 } 77 else if(a == 3){ 78 l.push(tp); 79 } 80 } 81 else if(s[0] == 'O'){ 82 cin>>a; 83 if(a == 1){ 84 if(j.empty()){ 85 cout<<"EMPTY"<<endl; 86 } 87 else{ 88 node tp = j.top(); 89 j.pop(); 90 cout<<tp.id<<endl; 91 } 92 } 93 else if(a == 2){ 94 if(k.empty()){ 95 cout<<"EMPTY"<<endl; 96 } 97 else{ 98 node tp = k.top(); 99 k.pop(); 100 cout<<tp.id<<endl; 101 } 102 } 103 else if(a == 3){ 104 if(l.empty()){ 105 cout<<"EMPTY"<<endl; 106 } 107 else{ 108 node tp = l.top(); 109 l.pop(); 110 cout<<tp.id<<endl; 111 } 112 } 113 114 } 115 } 116 } 117 return 0; 118 }
十二、Stone（Priority_Queue）
- 同第九题，英文题，现在不想做，等下再做
- 做完回来了，优先队列模拟就行了
- 自己写个排序按照位置排序，注意位置相同时候，得优先能抛最远的
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 struct node{ 45 int pos,num; 46 bool operator < (const node b)const{ 47 if(pos != b.pos) 48 return b.pos < pos; 49 return b.num < num; 50 } 51 }; 52 53 int main(){ 54 ios_base::sync_with_stdio(false); 55 cout.tie(0); 56 cin.tie(0); 57 int t,n; 58 node tp; 59 cin>>t; 60 while(t--){ 61 cin>>n; 62 priority_queue<node>q; 63 for(int i = 0; i < n; i++){ 64 cin>>tp.pos>>tp.num; 65 q.push(tp); 66 } 67 int flag = 1; 68 while(!q.empty()){ 69 tp = q.top(); 70 q.pop(); 71 if(flag){ 72 flag = 0; 73 tp.pos += tp.num; 74 q.push(tp); 75 } 76 else 77 flag = 1; 78 } 79 cout << tp.pos << endl;; 80 } 81 return 0; 82 }
十三、离散化（Set+Vector）
- 字符串离散化，数据处理的基础题吧
- 因为C++有字符串类型，直接用string就行了，因为它内置了比较函数
- 然后我用的是Set去重，转入Vector中找位置就行了，（注意Set有无序性！）
- 其实也可以在Vector中利用unique去重，都行啦。
- 代码：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 set<string>s; 45 vector<string>p; 46 char a[10005][40]; 47 48 int main(){ 49 ios_base::sync_with_stdio(false); 50 cout.tie(0); 51 cin.tie(0); 52 int n; 53 while(~scanf("%d",&n)){ 54 s.clear(); 55 p.clear(); 56 for(int i = 0; i < n; i++){ 57 scanf("%s",&a[i]); 58 s.insert(a[i]); 59 } 60 p.assign(s.begin(),s.end()); 61 for(int i = 0; i < n; i++){ 62 printf("%d\n",lower_bound(p.begin(),p.end(),a[i]) - p.begin() + 1); 63 } 64 } 65 return 0; 66 }
大部分都是一些基础题，我猜他们开这个专题也是为了让大家熟悉STL中的东西。
还是很值得一做的。毕竟多做题总是有好处。
我做的时候有些题目TLE了，所以也不是说直接上去写个什么什么就AC了，还是很值得一做的，还有这个OJ有些题目会提交失败，各位可以搜题然后去原OJ提交。
别问我为啥做这个OJ，很多都有做，还有就是，这个OJ界面做的很好有木有，题目也很好啦。
