原題及翻譯

Background from Wikipedia: “Set theory is a branch of mathematics created principally by the German mathematician Georg Cantor at the end of the 19th century.
來自維基百科的背景：“集合論是一個數學分支，主要由19世紀末的德國數學家喬治坎特創立。
Initially controversial, set theory has come to play the role of a foundational theory in modern mathematics, in the sense of a theory invoked to justify assumptions made in mathematics concerning the existence of mathematical objects (such as numbers or functions) and their properties.
最初有爭議的是，集合論在現代數學中起到了基礎理論的作用，從某種意義上說，集合論被用來證明數學中關于數學對象（如數字或函數）的存在及其性質的假設是合理的。
Formal versions of set theory also have a foundational role to play as specifying a theoretical ideal of mathematical rigor in proofs.”
集理論的正式版本也有一個基礎性的作用，作為在證明中指定數學嚴謹的理論理想。”
Given this importance of sets, being the basis of mathematics, a set of eccentric theorist set off to construct a supercomputer operating on sets instead of numbers.
鑒于集合的重要性，作為數學的基礎，一組古怪的理論家著手建造一臺以集合而不是數字為基礎的超級計算機。
The initial SetStack Alpha is under construction, and they need you to simulate it in order to verify the operation of the prototype.
初始的setstack alpha正在構建中，他們需要您模擬它以驗證原型的操作。
The computer operates on a single stack of sets, which is initially empty.
計算機在最初為空的一組集合上運行。
After each operation, the cardinality of the topmost set on the stack is output.
在每次操作之后，將輸出堆棧上最頂層集的基數。
The cardinality of a set S is denoted |S| and is the number of elements in S.
集合s的基數用|s|表示，是s中元素的數目。
The instruction set of the SetStack Alpha is PUSH, DUP, UNION, INTERSECT,and ADD.
setstack alpha的指令集是push、dup、union、intersect和add。
? PUSH will push the empty set {} on the stack.
?push將推動堆棧上的空集合。
? DUP will duplicate the topmost set (pop the stack, and then push that set on the stack twice).
?DUP將復制最上面的集合（彈出堆棧，然后將該集合推到堆棧上兩次）。
? UNION will pop the stack twice and then push the union of the two sets on the stack.
?UNION將彈出堆棧兩次，然后推動堆棧上兩組的聯合。
? INTERSECT will pop the stack twice and then push the intersection of the two sets on the stack.
?Intersect將彈出堆棧兩次，然后推動堆棧上兩個集合的交叉點。
? ADD will pop the stack twice, add the first set to the second one, and then push the resulting set on the stack.
?ADD將彈出堆棧兩次，將第一組添加到第二組，然后將結果集推送到堆棧上。
For illustration purposes, assume that the topmost element of the stack is
A = {{}, {{}}}
and that the next one is
B = {{}, {{{}}}}
為了便于說明，假設堆棧的最上面的元素是
A = {{}, {{}}}
下一個是
B = {{}, {{{}}}}
For these sets, we have |A| = 2 and |B| = 2. Then:
對于這些集合，我們有a=2和b=2。然后：
? UNION would result in the set {{}, {{}}, {{{}}}}. The output is 3.
?UNION將導致集合{{}, {{}}, {{{}}}}。輸出為3。
? INTERSECT would result in the set {{}}. The output is 1.
?INTERSECT將導致集合 {{}}。輸出為1。
? ADD would result in the set {{}, {{{}}}, {{},{{}}}}. The output is 3.
?添加將導致集合 {{}, {{{}}}, {{},{{}}}}。輸出為3。

Input

An integer 0 ≤ T ≤ 5 on the first line gives the cardinality of the set of test cases.
第一行的整數0≤t≤5給出了一組測試用例的基數。
The first line of each test case contains the number of operations 0 ≤ N ≤ 2000.
每個測試用例的第一行包含操作數0≤n≤2000。
Then follow N lines each containing one of the five commands.
然后N行有五個命令。
It is guaranteed that the SetStack computer can execute all the commands in the sequence without ever popping an empty stack.
它保證了setstack計算機可以按順序執行所有命令，而不會彈出空堆棧。

Output

For each operation specified in the input, there will be one line of output consisting of a single integer.
對于輸入中指定的每個操作，將有一行輸出，由單個整數組成。
This integer is the cardinality of the topmost element of the stack after the corresponding command has executed.
這個整數是執行相應命令后堆棧最頂層元素的基數。
After each test case there will be a line with ‘***’ (three asterisks).
每個測試用例之后都會有一行帶有“***”（三個星號）。

Sample Input

2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

Sample Output

分析

本題的集合并不是簡單的整數集合或者字符集合，而是集合的集合。為了方便起見，此處為每個不同的集合分配一個唯一的ID，則每個集合都可以表示成所包含元素的ID的集合，這樣就可以用STL的set來表示了，而整個棧則是一個stack。

代碼

#include<iostream> #include<stack> #include<set> #include<map> #include<vector> #include<string> #include <algorithm>#define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) /* 定義兩個宏，分別表示“所有的內容”以及“插入迭代器”，具體作用可以從代碼中推斷出來， */using namespace std;typedef set<int> Set; map<Set,int> IDcache; //把集合映射成ID vector<Set> Setcache; //根據ID取集合//查找給定集合x的ID。如果找不到，分配一個新ID。 int ID(Set x) {if(IDcache.count(x)) return IDcache[x];Setcache.push_back(x); //添加新集合return IDcache[x]=Setcache.size()-1; }/* 對任意集合s(類型是上面定義的Set)，IDcache[s]就是它的ID， 而Setcache[IDcache[s]]就是s本身。 *///主程序int main() {int T;cin >> T;while (T--) {stack<int> s;//題目中的棧int n;cin >> n;for (int i = 0; i < n; i++) {string op;cin >> op;if (op[0] == 'P') s.push(ID(Set()));else if (op[0] == 'D') s.push(s.top());else {Set x1 = Setcache[s.top()]; s.pop();Set x2 = Setcache[s.top()]; s.pop();Set x;if (op[0] == 'U') set_union(ALL(x1), ALL(x2), INS(x));if (op[0] == 'I') set_intersection(ALL(x1), ALL(x2), INS(x));if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }s.push(ID(x));}cout << Setcache[s.top()].size() << endl;}cout << "***" << endl;}return 0; }

總結

以上是生活随笔為你收集整理的The SetStack Computer的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。