MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 12096 - The SetStack Computer
AOAPC II

UVaOJ 12096 - The SetStack Computer

Chai
2021-11-24 0:00:00在线评测阅读 418

问题描述

p12096

原题链接:UVaOJ 12096 - The SetStack Computer

相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-5

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

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

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz