Codeforces Round 773 Div.1 D. Two Arrays

发表于 分类于 本文字数： 3.5k 阅读时长 ≈ 3 分钟

本章内容

本章为Codeforces Round #773 Div.1 D. Two Arrays的题解。

题目内容

给定 \(n\) 个长度为 \(m\) 的数组 \(a_1,a_2,...,a_n\)。第 \(i\) 个数组有一个附加权值 \(j\)。
定义 \(val(i,j)=w_i+w_j\)，对于所有的满足数组 \(a_i,a_j\) 内的数字两两不同的 \(i,j\)，求 \(val(i,j)\) 的最小值。如果不存在两个数组满足它们内的数字两两不同，输出 -1。
\(n≤10^5,\quad m≤5,\quad 1≤a_｛i,j｝,\enspace w_i≤10^9\)。

解题思路

常规想法

我们很容易想到，通过枚举\(i\)，\(j\)来计算，用一个\(map\)来存储第\(i\)行的数，然后判断第\(j\)行的数与其是否有重复，没有重复则计算\(w_i+w_j\)，但是由于题目数据范围\(n\leq 10^5\)，所以\(O(n^2)\)的时间复杂度太高，会超时。

本题解法

因此，我们需要考虑一个能够很方便判断两行数是否有交集的方法，观察数据范围\(m\leq 5\)，可以考虑\(2^m\)的构造方法。

关于判断序列｛a｝和｛b｝有无相同元素的判断方法：记一个计数器\(cnt\)，对于每一个｛b｝的子集，首先判断它在｛a｝是否出现，如果出现，则分为两种情况。如果该子集的元素个数是奇数，就将\(cnt\)加上它在｛a｝中的出现次数，如果元素个数是偶数，则将\(cnt\)减去它在｛a｝中的出现个数。如果最后\(cnt=1\)则说明至少有一个元素相同，否则它们就没有相同元素。

对于上述的方法，不只适用于单独判断｛a｝和｛b｝序列，也适用于判断｛a｝和多个序列是否有相同元素，可以想象成｛a｝与多个序列的每个序列一个个判断，如果与一个序列有相同的，则 \(cnt\)++，如果最后 \(cnt\) 等于多个序列的个数，则说明全都有相同元素。

对于 n 行序列，首先我们按 \(w_i\) 从小到大将其排序，设有左端点 \(l\) 序列和右端点 \(r\) 序列，对于左端点 \(l\) ，我们希望找到符合条件的最小 \(r\)。如果我们从左到右依次枚举 \(l\)，然后找到与 \(l\) 序列没有相同元素的最小 \(r\) 序列，这为当前的一组解。如果要找到比\((l, r)\)更优的解，则只有可能从 \((l,r)\) 的区间内再继续寻找，因为 \(l\) 是枚举的，接下来的 \(l\) 只会比当前的大，而为了达到总和 \(w_i+w_j\) 更小的目的，\(r\) 只能往左移动。所以相当于双指针，\(l\) 从左往右，\(r\) 从右往左，直至两者相遇。

时间复杂度为\(O(n \log(n2^m))\)

流程

  1. 首先，将所有的序列的所有子集放进\(map\)
  2. 设置双指针，左端为 \(l=0\)，右端为 \(r=n-1\)
  3. 从左到右枚举 \(l\)，在 \(map\) 中判断 \((l, r]\) 区间内是否存在符合要求的序列，如果个数小于 \(r-l\) ，则说明存在这样的序列，逐渐将 \(r\) 向左移动，找到满足要求的最小 \(r\)，移动过程中不在 \((l, r]\) 区间的序列子集要从 \(map\) 中删除
  4. 判断ans和当前的dat[l].w + dat[r].w大小，重复步骤3、4

代码

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
#include <bits/stdc++.h>

typedef unsigned long long ULL; 

using namespace std;

const int MAXN = (int)1e5+20;
const ULL base = 11451419198101ull;

struct Data {
    int a[6];
    ULL b[35];
    int w;
}dat[MAXN];

unordered_map <ULL, int> num;
int n, m;

bool cmp(const Data &x, const Data &y)  {
    return x.w < y.w;
}

void init()  {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)  {
	for (int j = 0; j < m; j++)  
	    scanf("%d", &dat[i].a[j]);
	scanf("%d", &dat[i].w);
	sort(dat[i].a, dat[i].a+m);
	for (int k = 1; k < (1<<m); k++)
	    for (int j = 0; j < m; j++)
		if ((k >> j) & 1)
		    dat[i].b[k] = dat[i].b[k] * base + dat[i].a[j];
    }
    sort(dat, dat+n, cmp);
}

void modify(int id, int o)  {
    for (int i = 1; i < (1<<m); i++)
	num[dat[id].b[i]] += o;
}

int query(int id)  {
    int cnt = 0;
    for (int i = 1; i < (1<<m); i++)
	if (__builtin_parity(i))
	    cnt += num[dat[id].b[i]];
	else cnt -= num[dat[id].b[i]];
    return cnt;
}

void work()  {
    int ans = -1;
    int l = 0, r = n-1, flag = 0;
    for (int i = 0; i < n; i++)  modify(i, 1);
    l = -1;
    while (l < r)  {
	l++;
	flag = 0;
	modify(l, -1);
	while (query(l) < r-l)  {
	    modify(r--, -1);
	    flag = 1;
	}
	if ( !flag )  continue;
	modify(++r, 1);
	if (ans != -1) ans = min(ans, dat[l].w + dat[r].w);
	else ans = dat[l].w + dat[r].w;
    }
    printf("%d\n", ans);
}

int main()  {
    freopen("in.txt", "r", stdin);
    init();
    work();
    return 0;
}

附

  • __builtin_popcount(unsigned int n) 该函数时判断n的二进制中有多少个1
1
2
int n = 15; //二进制为1111
cout<<__builtin_popcount(n)<<endl;//输出4
  • __builtin_parity(unsigned int n) 该函数是判断n的二进制中1的个数的奇偶性
1
2
3
4
int n = 15;//二进制为1111
int m = 7;//111
cout<<__builtin_parity(n)<<endl;//偶数个，输出0
cout<<__builtin_parity(m)<<endl;//奇数个，输出1
  • __builtin_ffs(unsigned int n) 该函数判断n的二进制末尾最后一个1的位置，从1开始
1
2
3
4
int n = 1;//1
int m = 8;//1000
cout<<__builtin_ffs(n)<<endl;//输出1
cout<<__builtin_ffs(m)<<endl;//输出4
  • __builtin_ctz(unsigned int n) 该函数判断n的二进制末尾后面0的个数，当n为0时，和n的类型有关
1
2
3
4
int n = 1;//1
int m = 8;//1000
cout<<__builtin_ctzll(n)<<endl;//输出0
cout<<__builtin_ctz(m)<<endl;//输出3
  • __builtin_clz (unsigned int x) 返回前导的0的个数