考虑根号分治。设 (m=\sum k_i)，则把 (k>\sqrt m) 的称为大集合，(k\leq \sqrt m) 的称为小集合。
对于小集合与小集合：
暴力枚举每个集合的每一对 ((x,y))，开一个哈希表维护有没有其他的集合也存在这个数对。由于集合大小不超过 (\sqrt m)，复杂度可以证明最大是 (O(m\sqrt m))。
对于大集合和其他集合：
枚举大集合的所有数放到哈希表里，暴力扫其他每个集合，判断是否相似。由于大集合的个数最多 (O(\sqrt m))，所以这部分复杂度是 (O(m\sqrt m)) 的，然后就做完了。
点击查看代码
#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#include
#define mp std::make_pair
#define fi first
#define se second
typedef std::pair pii;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res< a[N];
int ms[1][N];
std::vector vis[N];
/*struct HashTable//map int to T
{
#define T int//int can be replaced by the class you want
#define T_0 0//0 can be replaced by the zero item of T
inline void swap(int *&x,int *&y){ int *t=x;x=y;y=t; }
inline void swap(bool *&x,bool *&y){ bool *t=x;x=y;y=t; }
inline unsigned long long xor64(){ static unsigned long long x=19260817; return x^=x<>17,x^=x<m) resize((size*2+1)*2+1); int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return -p; used[p]=1,a[p]=x,b[p]=y,size++; return p; }
inline int find(int x){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return p; return -1; }
inline int erase(int p){ return find(p)==-1?-1:used[find(p)]=0; }
inline int& operator [] (int x){ return b[abs(insert(x,T_0))]; }
#undef T
#undef T_0
}ms[N];*/
int main(){
int T=rd();while(T--){
n=rd();m=0;int cntt=0;
for(int i=1;iy) std::swap(x,y);
vis[x].push_back(mp(y,p));
}
}
}
for(int i=1;i=2){game_over=1;ansx=p,ansy=q;break;}
}
if(game_over) break;
}
if(game_over) break;
for(int j=1;j=2){game_over=1;ansx=p,ansy=q;break;}
}
if(game_over) break;
}
if(game_over) break;
}
if(game_over){printf("%d %d\n",ansx,ansy);continue;}
puts("-1");
}
return 0;
}
//M
Original: https://www.cnblogs.com/winterfrost/p/cf1468m-solution.html
Author: cunzai_zsy0531
Title: CF1468M Similar Sets 题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604310/
转载文章受原作者版权保护。转载请注明原作者出处！