这道题虽然被评黄，但个人感觉不止普及组难度，而且是一道很有价值的题目。题解区里全是 \(O(n^2logn)\) 的 STL 大法，我来发一篇 \(O(n^2)\) 哈希做法。目前 0ms 喜提最优解。
这道题是 codeforces gym 的题目，本质上就是模拟栈中集合插入，复制，相加，取交集，取并集的过程。注意，这些集合都是不可重集。 如果你直接把这些括号和逗号存下来肯定是不行的，因为它是一个一层套一层的结构，不好直接维护。况且经过复制，括号总数会指数级增长。
既然直接存储不行，我就想用哈希来表示每个集合里的元素。这样每个集合就是一个 vector，里面存储了每个元素对应的哈希值。比如集合 { { { } } , { { } , { } } } 的 vector 里存储 { { } } 和 { { } , { } } 这两个字符串的哈希。
下面考虑分别维护这五种操作。
-
对于 PUSH 操作，直接新建一个 vector，里面什么也不存推入栈中。
-
对于 DUP 操作，直接复制一遍栈顶的 vector 推入栈中。
-
对于 UNION 操作，我们需要把两个 vector 里的数全部放入新的 vector 内，并且去重。如果这两个 vector 无序，去重需要 \(O(nlogn)\) 的复杂度，是不能接受的。所以我们在维护 vector 里的哈希值时，不妨使其有序。 这样，在做 UNION 操作时，就可以归并排序去重了，复杂度 \(O(n)\) 。
-
对于 INTERSECT 操作，和 UNION 一样归并排序找到重复元素即可。
-
对于 Add 操作，这是最复杂的一个操作。记第一个 vector 为 \(v1\)，第二个 vector 为 \(v2\)。则我们要把 \(v1\) 这个整体作为一个元素，求出其哈希值并放入 \(v2\)。但注意：不能设计普通的按位乘法哈希。 至于为什么留给大家自己思考。（提示：括号总数巨大）
虽然普通哈希不行，但我们有一个很好的性质，就是 v1 内的哈希值是有序的，唯一确定的。于是我们可以把哈希设计成这样：设 v1 内的哈希值为 \(h1\)，\(h2\)和\(h3\)，则有：
\(H(v1)=((h1+\Delta)\times h2+\Delta)\times h3\%P\)
其中 \(\Delta\) 和 \(P\) 是自己设定的常数。注意计算哈希时还要在每个元素之间加一个逗号，左右两边加上大括号。然后把 \(H(v1)\) 用插入排序的方法移到 \(v2\) 相应位置。我这里使用了 vector 的 insert 函数，比插入排序快几十倍左右。
最后输出栈顶 vector 的大小即可。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#define f first
#define s second
#define gc getchar
#define pc putchar
#define pb push_back
#define sz(a) a.size()
#define st(a) a.begin()
#define ed(a) a.end()
#define all(a) st(a),ed(a)
#define las(a) *a.rbegin()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class Typ> Typ &Rd(Typ &x){
x=0; char ch=gc(),sgn=0;
for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';
for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);
return sgn&&(x=-x),x;
}
template<class Typ> void Wt(Typ x){
if(x<0) pc('-'),x=-x;
if(x>9) Wt(x/10);
pc(x%10^48);
}
const int N=2005;
const int Ad=1000099;
const int Md=998244353;
vector<int> Hs[N]; char op[10];
int cas,n,stk[N],top;
int main(){
for(Rd(cas);cas;cas--){
Rd(n),top=0;
for(int i=1;i<=n;i++){
Hs[i].clear(),scanf("%s",op+1);
if(op[1]=='P') stk[++top]=i;
else if(op[1]=='D'){
for(auto j:Hs[stk[top]]) Hs[i].pb(j);
stk[++top]=i;
}else if(op[1]=='U'){
int id1=stk[top--],id2=stk[top--],ps=0;
for(auto cur:Hs[id1]){
for(;ps<sz(Hs[id2])&&Hs[id2][ps]<cur;ps++)
Hs[i].pb(Hs[id2][ps]);
Hs[i].pb(cur);
if(ps<sz(Hs[id2])&&Hs[id2][ps]==cur) ps++;
}
for(;ps<sz(Hs[id2]);ps++)
Hs[i].pb(Hs[id2][ps]);
stk[++top]=i;
}else if(op[1]=='I'){
int id1=stk[top--],id2=stk[top--],ps=0;
stk[++top]=i;
for(auto cur:Hs[id1]){
while(ps<sz(Hs[id2])&&Hs[id2][ps]<cur) ps++;
if(ps<sz(Hs[id2])&&Hs[id2][ps]==cur) Hs[i].pb(cur);
}
}else{
int Hsh=1+Ad,id1=stk[top--],id2=stk[top];
for(auto cur:Hs[id1]){
if(Hsh!=1+Ad) Hsh=((ll)Hsh*2%Md+Ad)%Md;
Hsh=((ll)Hsh*cur%Md+Ad)%Md;
}
Hsh=((ll)Hsh*3%Md+Ad)%Md;
if(!count(all(Hs[id2]),Hsh))
Hs[id2].insert(lower_bound(all(Hs[id2]),Hsh),Hsh);
}
Wt(sz(Hs[stk[top]])),pc('\n');
}
puts("***");
}
return 0;
}
写在最后：
要真的在联赛出这道题，我说不定就不选这种方法了，虽然保险，但 STL 也有优势，就是简单好写好调试。（而且 CCF 的数据不用多虑）不管怎么说，看到题解区同情 p 党，我也算是 python 的一员，哈希法也算是给 p 党一个可行的尝试方法了，只要把 vector 换成 list 即可。
做黄题让我回想起初一的时光，一去不复返了。也许有一天 OI 会从我脑中淡漠，但那段回忆永远藏着我的心中。
标签：ch,int,题解,v1,vector,UVA12096,哈希,define From： https://www.cnblogs.com/Illumina/p/17398524.html