fsy's blog

燃峥嵘岁月，烈日终破云。

Codeforces878D Magic Breeding

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

简要题意

  • 一开始有 $k$ 种生物，每种生物有 $n$ 个属性 $a_{k,1}, a_{k,2}, \cdots, a_{k,n}$。现有以下 $3$ 种操作：
  • (1). 给定两个正整数 $x$，$y$。创建一个新生物，此生物的第 $i$ 项属性为 $\max(a_{x,i}, a_{y,i})$。
  • (2). 给定两个正整数 $x$，$y$。创建一个新生物，此生物的第 $i$ 项属性为 $\min(a_{x,i}, a_{y,i})$。
  • (3). 给定两个正整数 $x$，$y$。输出第 $x$ 个生物的第 $y$ 项属性。
  • 新生物的编号获得最小的未使用数字。
  • 操作数 $q \leq 10^5$，属性数 $n \leq 10^5$，$k \leq 12$。

题解

注意到 $k$ 很小，而且最终的答案只会在这 $k$ 个生物里面，考虑把 $k$ 作为切入点。

令 $f_{i,mask}$ 为 如果选择的生物的二进制压缩为 $mask$，则此新生物中，是否一定会存在一个属性大于等于 $i$ 号生物的对应属性？

初始化： 枚举 $mask$，注意到如果 $i$ 号生物被选，则 $f_{i, mask}$ 一定为 $1$，否则不确定，为 $0$。

操作 1（取 $\max$）： 注意到三个数 $a, b, c$，当且仅当 $c > a$ 且 $c > b$ 才有 $c > \max(a,b)$，故把 $x$，$y$ 的 $f$ 数组看成一个二进制数，则新生物 $\overline{f_{new,1} \cdots f_{new,n}}$ 对应的二进制数即为 $\overline{f_{x,1} \cdots f_{x,n}} ; \text{and} ; \overline{f_{y,1} \cdots f_{y,n}}$

操作 2 推导同理，此处不再赘述。

操作 3（求答案）： 先按照那一位原来的从小到大排序，之后考虑每次加进去一个数看看是否一定大于等于这个位置的值（即 $f_{…,…}=1$）。第一个合法的数即为答案。

可以使用 std::bitset 优化上述过程。注意到不同的 $mask$ 只有 $2^k$ 个，故总时间复杂度为 $\mathcal{O}(\frac{q2^k}{w})$，可以通过本题。

代码

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
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}

const int maxN = 4e5 + 20;
int n, k, q, c[12][maxN], f[12], tot, x, y, z;
std::bitset<4096> F[maxN];

int main() {
	read(n, k, q); tot = k;
    _rep(i, 0, k - 1) {
        _rep(j, 1, n) read(c[i][j]);
    }
    _rep(i, 0, k - 1) {
        _rep(mask, 0, (1 << k) - 1) if(mask & (1 << i)) F[i + 1][mask] = 1;
    }
    while(q--) {
        read(x, y, z); 
        if(x == 1) F[++tot] = F[y] & F[z];
        else if(x == 2) F[++tot] = F[y] | F[z];
        else {
            _rep(i, 0, k - 1) f[i] = i;
            std::sort(f, f + k, [](int i, int j) {
                return c[i][z] < c[j][z];
            });
            int mask = 0;
            _rep(i, 0, k - 1) {
                mask |= (1 << f[i]);
                if(F[y][mask]) {
                    writesp(c[f[i]][z], '\n');
                    break;
                }
            }
        }
    }
	return 0;
}