Fork me on GitHub

Uoj#45.【清华集训2014】虫逢

Uoj#45. 【清华集训2014】虫逢

题意:

  • 给一个$M$元集的$2\times N$个大小为$L$的子集,每个子集有恰好另一个子集和它的交是$L/2$。
  • 求每个子集对应的另一个子集。
  • 数据随机,$N=M=L^2\le 16900$。

题解:

  • 首先考虑给每个元素一个哈希值。
  • 设每个集合的哈希值为其元素哈希值的最小值,那么两个集合$U,V$哈希值相同的概率为$\frac{|U\cap V|}{|U\cup V|}$。
  • 同源子集的概率就是$\frac{1}{3}$,不同源子集的概率就大约是$\frac{1}{L}$。(相当于生日攻击)
  • 这样还不够优秀,我们使用双哈希,这样概率就是$\frac{1}{9}$和$\frac{1}{n}$。
  • 然后我们进行多次这样的过程,每次将$N$缩小缩小$\frac{1}{9}$。
  • 复杂度$O(NL)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
typedef pair<int,int> pii;
const int N=16909<<1;
const int M=139;
int n,m,l,a[N][M],cnt,Ans[N],num,h[2][N],pos[N],vis[N];
pii H[N];
char str[20000009];
struct hash_map
{
#define mod 10000007
int first[mod],number;
int next[mod],v[mod],val[mod];
void init()
{
memset(first,0,sizeof(first));
number=0;
}
int &operator [](int x)
{
for (int i=first[x%mod];i;i=next[i])
if (v[i]==x) return val[i];
next[++number]=first[x%mod];
first[x%mod]=number;
v[number]=x;
return val[number];
}
int count(int x)
{
for (int i=first[x%mod];i;i=next[i])
if (v[i]==x) return 1;
return 0;
}
#undef mod
}mp;
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
int get(int x)
{
return mp.count(x)?mp[x]:mp[x]=++cnt;
}
bool cmp(int x,int y)
{
return H[x]<H[y];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data1.in","r",stdin);
#endif
srand((int)time(0)+(unsigned long long)new char);
mp.init();
n=read(),m=read(),l=read();
scanf("%s",str+1);
for (int i=1;i<=2*n;i++)
{
for (int j=1;j<=l;j++)
{
int now=0;
for (int k=1;k<=4;k++)
now=now*128+str[(i-1)*l*4+(j-1)*4+k];
a[i][j]=get(now);
}
}
for (int i=1;i<=cnt;i++)
h[0][i]=h[1][i]=i;
while (num<n)
{
random_shuffle(h[0]+1,h[0]+cnt+1);
random_shuffle(h[1]+1,h[1]+cnt+1);
int Cnt=0;
for (int i=1;i<=2*n;i++)
{
if (Ans[i]) continue;
pos[++Cnt]=i;
H[i]=make_pair(2147483647,2147483647);
for (int j=1;j<=l;j++)
{
H[i].first=min(H[i].first,h[0][a[i][j]]);
H[i].second=min(H[i].second,h[1][a[i][j]]);
}
}
sort(pos+1,pos+Cnt+1,cmp);
for (int i=1,j;i<=Cnt;i=j)
{
j=i;
while (H[pos[i]]==H[pos[j]]&&j<=Cnt) j++;
for (int k=i;k<j-1;k++)
if (!Ans[pos[k]])
for (int p=k+1;p<j;p++)
{
if (Ans[pos[k]]||Ans[pos[p]]) continue;
int similar=0;
for (int q=1;q<=l;q++) vis[a[pos[k]][q]]=1;
for (int q=1;q<=l;q++)
if (vis[a[pos[p]][q]]) similar++;
for (int q=1;q<=l;q++) vis[a[pos[k]][q]]=0;
if (similar==l/2)
{
Ans[pos[k]]=pos[p],Ans[pos[p]]=pos[k];
num++;
break;
}
}
}
}
for (int i=1;i<=2*n;i++) printf("%d\n",Ans[i]);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#45.【清华集训2014】虫逢

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj45/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。