题目描述
Sam changed his school and on the first biology lesson he got a very interesting task about genes.
You are given $ n $ arrays, the $ i $ -th of them contains $ m $ different integers — $ a_{i,1}, a_{i,2},\ldots,a_{i,m} $ . Also you are given an array of integers $ w $ of length $ n $ .
Find the minimum value of $ w_i + w_j $ among all pairs of integers $ (i, j) $ ( $ 1 \le i, j \le n $ ), such that the numbers $ a_{i,1}, a_{i,2},\ldots,a_{i,m}, a_{j,1}, a_{j,2},\ldots,a_{j,m} $ are distinct.
输入格式
The first line contains two integers $ n $ , $ m $ ( $ 2 \leq n \leq 10^5 $ , $ 1 \le m \le 5 $ ).
The $ i $ -th of the next $ n $ lines starts with $ m $ distinct integers $ a_{i,1}, a_{i,2}, \ldots, a_{i,m} $ and then $ w_i $ follows ( $ 1\leq a_{i,j} \leq 10^9 $ , $ 1 \leq w_{i} \leq 10^9 $ ).
把所有数按照 \(w\) 排序之后，扫描 \(a_r\)，对 \(r\) 去查一个最小的 \(l\) 使得 \(l,r\) 符合条件。
\(r\) 是不断增大的，如果 \(l\) 也跟着变大，答案肯定不如之前算的。所以 \(l\) 是稳定变小的。
我们现在要快速判断 \([1,l]\) 这个区间里是否存在一个和 \(a_r\) 互不相同的数。
互不相同很难计算，考虑容斥，枚举一个集合，统计前 \(l\) 个里面这个集合的出现次数。统计这里可以 map+哈希 统计。然后容斥完判断一下就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5;
int n,m,a[N][M],w[N],id[N],lsh[N*M],k,ans=2.1e9,pw[N*M],p[N];
mt19937 gen(time(0));
vector<int>g[N*M];
unordered_map<int,int>mp;
int cmp(int x,int y)
{
return w[x]<w[y];
}
int ok(int x)
{
int ret=0;
for(int j=1;j<(1<<m);j++)
{
int ans=0,c=0;
for(int k=0;k<m;k++)
if(j>>k&1)
ans^=pw[a[x][k]],c^=1;
ret+=mp[ans];
}
return ret;
}
void ins(int x,int op)
{
for(int j=1;j<(1<<m);j++)
{
int ans=0,c=0;
for(int k=0;k<m;k++)
if(j>>k&1)
ans^=pw[a[x][k]],c^=1;
mp[ans]+=c? op:-op;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
scanf("%d",a[i]+j),lsh[++k]=a[i][j];
scanf("%d",w+i),id[i]=i;
}
sort(lsh+1,lsh+k+1);
k=unique(lsh+1,lsh+k+1)-lsh-1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
a[i][j]=lower_bound(lsh+1,lsh+k+1,a[i][j])-lsh,g[a[i][j]].push_back(i),pw[a[i][j]]=gen()/2;
}
sort(id+1,id+n+1,cmp);
p[0]=n;
for(int i=1;i<=n;i++)
ins(i,1);
for(int i=1;i<=n;i++)
{
p[i]=p[i-1];
if(ok(id[i])==p[i])
continue;
while(p[i])
{
ins(id[p[i]],-1);
if(ok(id[i])==p[i]-1)
{
ins(id[p[i]],1);
break;
}
else
--p[i];
}
if(p[i])
ans=min(ans,w[id[p[i]]]+w[id[i]]);
}
printf("%d",ans>=2100000000? -1:ans);
}