问题描述
p12096原题链接:UVaOJ 12096 - The SetStack Computer
相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-5
解法一:模拟栈 + 存储索引
这是一道栈操作的题目,特别点在于栈中的元素是集合,集合中的元素也可以是集合(即可以嵌套),这样表示起来就比较麻烦。因此我们的栈中可以存储某个集合的 ID 索引,每次需要进行操作时,先根据栈中存储的索引去找到对应缓存下来的集合,再利用 STL 中的集合操作做处理。需要处理的就是如何分配 ID 信息,这里用 map 来建立集合到 ID 的映射关系,如果存在同样的集合,就可以直接使用 id_cache 中的 ID,无需建立新的 key-value 对;如果是新出现的集合,就需要在 set_cache 缓存下来,并分配新的 ID. 这个思想其实很像我们存储数据的时候先存放的是指针,在用到的时候再去根据指针指向的内存地址取相应的数据,只不过这一题没有用指针,而是用 vector 数据结构来实现一样的效果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> #define TWO_SET(a, b) a.begin(), a.end(), b.begin(), b.end() #define INS(t) inserter(t, t.begin()) using namespace std; using Set = set<int>; vector<Set> set_cache; // map: int -> Set map<Set, int> id_cache; int get_set_id(const Set& set_element) { if (id_cache.find(set_element) != id_cache.end()) // Try finding set id return id_cache[set_element]; set_cache.push_back(set_element); // Cache the new set return id_cache[set_element] = set_cache.size() - 1; // Get and cache new id } int main() { int t, num_op; cin >> t; while (t--) { stack<int> sstack; set_cache.clear(), id_cache.clear(); cin >> num_op; while (num_op--) { string op; cin >> op; if (op == "PUSH") sstack.push(get_set_id(Set())); else if (op == "DUP") sstack.push(sstack.top()); else { Set a, b, tmp; a = set_cache[sstack.top()], sstack.pop(); b = set_cache[sstack.top()], sstack.pop(); if (op == "UNION") set_union(TWO_SET(a, b), INS(tmp)); if (op == "INTERSECT") set_intersection(TWO_SET(a, b), INS(tmp)); if (op == "ADD") tmp = b, tmp.insert(id_cache[a]); sstack.push(get_set_id(tmp)); } cout << set_cache[sstack.top()].size() << endl; } cout << "***" << endl; } return 0; } |
1 |
#TODO |