12096 - The SetStack Computer （UVA）

题目链接如下：

Online Judge

这道题我一开始的思路大方向其实是对的，但细节怎么实现set到int的哈希没能想清楚（没想到这都能用map）。用set<string>的做法来做，测试数据小的话答案是对的，但大数据时间超时。

其实就是把所有set一一映射到int, 所以stack里每个元素就是int. 

按照刘汝佳思路写的代码如下（按理每个case里stack应该先清空，但因为题目保证了没有无效操作+只需要最上面set的元素个数，不清空也没问题）：

#include <cstdio>
#include <set>
#include <stack>
#include <map>
#include <vector>
// #define debugint T, N, a, b;
std::map<std::set<int>, int> mp;
char op[10];
std::stack<int> s;
std::set<int> empty;
std::vector<std::set<int>> vec;void _push(std::set<int> st){if(!mp.count(st)){vec.push_back(st);mp[st] = vec.size() - 1;}s.push(mp[st]);
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifscanf("%d", &T);while(T--){scanf("%d", &N);vec.clear();mp.clear();while(N--){scanf("%s", op);if(op[0] == 'P'){_push(empty);} else{a = s.top();s.pop();if(op[0] == 'D'){s.push(a);s.push(a);} else{b = s.top();s.pop();std::set<int> tmp;if(op[0] == 'A'){tmp = vec[b];tmp.insert(a);} else{if(op[0] == 'U'){tmp = vec[a];for(auto it = vec[b].begin(); it != vec[b].end(); ++it){tmp.insert(*it);}} else if(op[0] == 'I'){for(auto it = vec[a].begin(); it != vec[a].end(); ++it){if(vec[b].find(*it) != vec[b].end()){tmp.insert(*it);}}}}_push(tmp);}}printf("%d\n", vec[s.top()].size());}printf("***\n");}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}

原先的代码如下（超时）：

#include <cstdio>
#include <set>
#include <stack>
#include <string>
// #define debugint T, N;
char op[10];
std::stack<std::set<std::string>> s, empStack;
std::set<std::string> a, b, empty;std::string toString(std::set<std::string> st){std::string str = "{";for(auto it = st.begin(); it != st.end(); ++it){str += (it == st.begin() ? "" : ",");str += *it;}return str + "}";
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifscanf("%d", &T);while(T--){scanf("%d", &N);s.swap(empStack);while(N--){scanf("%s", op);if(op[0] == 'P'){s.push(empty);} else{a = s.top();s.pop();if(op[0] == 'D'){s.push(a);s.push(a);} else{b = s.top();s.pop();if(op[0] == 'A'){b.insert(toString(a));s.push(b);} else{if(op[0] == 'U'){for(auto it = a.begin(); it != a.end(); ++it){b.insert(*it);}s.push(b);} else if(op[0] == 'I'){std::set<std::string> intersect;for(auto it = a.begin(); it != a.end(); ++it){if(b.find(*it) != b.end()){intersect.insert(*it);}}s.push(intersect);}}}}printf("%d\n", s.top().size());}printf("***\n");}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}