UVaOJ 12096 – The SetStack Computer

问题描述

p12096

原题链接：UVaOJ 12096 - The SetStack Computer

解法一：模拟栈 + 存储索引

这是一道栈操作的题目，特别点在于栈中的元素是集合，集合中的元素也可以是集合（即可以嵌套），这样表示起来就比较麻烦。因此我们的栈中可以存储某个集合的 ID 索引，每次需要进行操作时，先根据栈中存储的索引去找到对应缓存下来的集合，再利用 STL 中的集合操作做处理。需要处理的就是如何分配 ID 信息，这里用 map 来建立集合到 ID 的映射关系，如果存在同样的集合，就可以直接使用 id_cache 中的 ID，无需建立新的 key-value 对；如果是新出现的集合，就需要在 set_cache 缓存下来，并分配新的 ID. 这个思想其实很像我们存储数据的时候先存放的是指针，在用到的时候再去根据指针指向的内存地址取相应的数据，只不过这一题没有用指针，而是用 vector 数据结构来实现一样的效果。

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ