感觉这场F比E简单多了= =
题意
给出一个\(n \times m\)的数组 \((1 \leq n \leq 10^5,1 \leq m \leq 5)\). 数组的每一行元素均互不相同, 且每一行有一个权值\(w\) \((1 \leq w \leq 10^9)\).
你需要找出不同的两行, 使得这两行在不存在重复元素的同时权值最小. 输出权值, 无解输出-1.
题解
暴力做需要\(O(n^2m)\).
将行按权值排序, 把每一个元素对应的行用bitset存下来, 0代表非法1代表合法. 再在枚举每行的时候找到第一个不冲突的行更新答案就可以做到\(O(\frac{n^2m}{w})\), 其中\(w = 32\)或\(64\). 但是这样需要\(O(\frac{n^2m}{8})\)的空间, 会MLE.
考虑分块. 设块大小为\(B\), 将每个元素按出现次数分类:
- 出现次数大于\(B\), 这部分元素用bitset存下来, 在枚举每行时使用按位与来更新, 时间复杂度\(O(\frac{n^2m}{Bw})\), 空间复杂度\(O(\frac{n^2m}{8B})\).
- 出现次数小于\(B\), 这部分元素在枚举每行时直接更新, 时间复杂度\(O(B^2)\), 空间复杂度\(O(n)\).
(感觉复杂度算的很不对劲啊- - 反正能过)
然后B选一个差不多的大小比如\(\sqrt{nm}\)就能过了.
代码
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define ALL(x) (x).begin(),(x).end()
#define PRINT(___) for(auto ____:(___)){cout << ____ << " ";}cout << endl;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll Pow(ll x,ll d,ll p){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2,p);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
const int maxn = 1e5+10;
const int maxm = maxn*2;
const int p = 1e9+7;
int raw[maxn],mp[maxn * 5];
const int maxb = 708;
const int maxc = 100006;
bitset<maxc>b[maxb + 10];
vector<int>ban[maxn * 5];
struct Node{
vector<int>r;
int w;
Node(vector<int> r = {},int w = 0):r(r),w(w){}
bool operator < (const Node & x)const{
return w < x.w;
}
}node[maxn];
int cnt[maxn * 5];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed,ios::floatfield);
cout.precision(12);
int n,m;
cin >> n >> m;
map<int,int>hsh;
for(int i = 1;i <= n;i++){
vector<int>r(m);
int w;
for(int j = 0;j < m;j++){
cin >> r[j];
hsh[r[j]]++;
}
cin >> w;
node[i] = Node(r,w);
}
int tmp = 1;
for(auto & it:hsh){
cnt[tmp] = it.second;
it.second = tmp++;
}
sort(node+1,node+n+1);
int ans = 2e9 + 10,idx = 1;
for(int i = 1;i <= n;i++){
for(int j = 0;j < m;j++){
int & v = node[i].r[j];
v = hsh[v];
if(cnt[v] > maxb){
if(!mp[v]){
b[idx].set();
mp[v] = idx++;
}
b[mp[v]].reset(i);
}
else ban[v].push_back(i);
}
}
for(int i = 1;i <= n;i++){
bitset<maxc>vai;
vai.set();
vai.reset(0);
for(int j = 0;j < m;j++){
int v = node[i].r[j];
if(cnt[v] > maxb){
vai &= b[mp[v]];
}
else{
for(int x:ban[v])vai.reset(x);
}
}
int x = vai._Find_first();
if(x <= n)ans = min(ans,node[i].w + node[x].w);
}
if(ans == 2e9+10)ans = -1;
cout << ans;
return 0;
}
|