CCCCGPLTL2005:集合相似度计算的双指针算法优化

两个集合A,B的相似度定义为n(A∩B)/n(A∪B),n()表示集合大小.
给出n(50)个集合,每个集合给出一个大小M(1e4),然后是M个数(1e9)
给出k(2000)次查询,每次查询两个集合的相似度.

做这道题之前,stl了解一下;
bool includes()判断一个集合是否为一个集合的子集
set_difference() 返回两个集合的差集合
set_intersection() 返回两个集合的交集
set_symmetric_difference() 返回两个集合的对称差集合
set_union() 返回两个集合的并集
参数均为4个iterator

好了,此题跟set关系不大.
理论上来说2000*1e4是会超时的,但是手写了一个获得交集的方法就过了,pat评测果然6(也许)
注意消除重复的值

获得交集大小使用的是双指针扫描.并集大小由容斥原理可得.

/* LittleFall : Hello! */
#include
#define ll long long
using namespace std;
inline int read();
inline void write(int x);
const int M &＃61; 100016;
vector save[64];
int main(void)
{
#ifdef _LITTLEFALL_
freopen("in.txt", "r", stdin);
#endif
//std::cin.sync_with_stdio(false);
int n &＃61; read();
for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
{
int m &＃61; read();
for(int j &＃61; 0; j save[i].push_back(read());
sort(save[i].begin(), save[i].end());
save[i].erase(unique(save[i].begin(), save[i].end()), save[i].end());
}
int k &＃61; read();
while(k--)
{
int ta &＃61; read(), tb &＃61; read();
int ln &＃61; 0, lu &＃61; save[ta].size() &＃43; save[tb].size(); //并数,交数
for(int i &＃61; 0, j &＃61; 0;
i <(int)save[ta].size() && j <(int)save[tb].size();
i&＃43;&＃43;, j&＃43;&＃43;)
{
if(save[ta][i] j--; //i&＃43;&＃43;
else if(save[ta][i] > save[tb][j])
i--; //j&＃43;&＃43;
else
ln&＃43;&＃43;;
}
printf("%.2f%%\n", 100.0 * ln / (lu-ln));
}
return 0;
}
inline int read()
{
int x &＃61; 0, f &＃61; 1;
char ch &＃61; getchar();
while(ch <&＃39;0&＃39; || ch > &＃39;9&＃39;)
{
if(ch &＃61;&＃61; &＃39;-&＃39;)f &＃61; -1;
ch &＃61; getchar();
}
while(ch >&＃61; &＃39;0&＃39; && ch <&＃61; &＃39;9&＃39;)
{
x &＃61; x * 10 &＃43; ch - &＃39;0&＃39;;
ch &＃61; getchar();
}
return x * f;
}
inline void write(int x)
{
if(x <0) putchar(&＃39;-&＃39;), x &＃61; -x;
if(x > 9) write(x / 10);
putchar(x % 10 &＃43; &＃39;0&＃39;);
}