【Codeforces】CF 2003 D2

Turtle and a MEX Problem (Hard Version)

#图论 #贪心 #数学

题目描述

The two versions are different problems. In this version of the problem, you can’t choose the same integer twice or more. You can make hacks only if both versions are solved. One day, Turtle was playing with $n$ sequences. Let the length of the $i$-th sequence be $l_i$. Then the $i$-th sequence was $a_{i,1},a_{i,2},\dots ,a_{i,l_i}$. Piggy gave Turtle a problem to solve when Turtle was playing. The statement of the problem was: - There was a non-negative integer $x$ at first. Turtle would perform an arbitrary number (possibly zero) of operations on the integer. - In each operation, Turtle could choose an integer $i$ such that $1\le i\le n$ and $i$ wasn’t chosen before, and set $x$ to ${\text{mex}}^{†}(x,a_{i,1},a_{i,2},\dots ,a_{i,l_i})$. - Turtle was asked to find the answer, which was the maximum value of $x$ after performing an arbitrary number of operations. Turtle solved the above problem without difficulty. He defined $f(k)$ as the answer to the above problem when the initial value of $x$ was $k$. Then Piggy gave Turtle a non-negative integer $m$ and asked Turtle to find the value of $\sum _{i=0}^{m}f(i)$ (i.e., the value of $f(0)+f(1)+\dots +f(m)$). Unfortunately, he couldn’t solve this problem. Please help him! ${}^{†}\text{mex}(c_1,c_2,\dots ,c_k)$ is defined as the smallest non-negative integer $x$ which does not occur in the sequence $c$. For example, $\text{mex}(2,2,0,3)$ is $1$, $\text{mex}(1,2)$ is $0$.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n,m$ ($1\le n\le 2\cdot 10^5,0\le m\le 10^9$).

Each of the following $n$ lines contains several integers. The first integer $l_i$ ($1\le l_i\le 2\cdot 10^5$) represents the length of the $i$-th sequence, and the following $l_i$ integers $a_{i,1},a_{i,2},\dots ,a_{i,l_i}$ ($0\le a_{i,j}\le 10^9$) represent the elements of the $i$-th sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ and the sum of $\sum l_i$ over all test cases does not exceed $2\cdot 10^5$.

输出格式

For each test case, output a single integer — the value of $\sum _{i=0}^{m}f(i)$.

样例 #1

样例输入 #1

6
3 4
2 0 2
3 2 3 3
4 7 0 1 5
3 4
5 0 2 0 4 11
1 1
5 1 3 0 3 3
2 50
2 1 2
2 1 2
1 1
7 1 2 4 1 4 9 5
4 114514
2 2 2
5 7 3 6 0 3
3 0 1 1
5 0 9 2 1 5
5 1919810
1 2
2 324003 0
3 1416324 2 1460728
4 1312631 2 0 1415195
5 1223554 192248 2 1492515 725556

样例输出 #1

16
18
1281
4
6556785365
1842836177961

解法

解题思路

首先，我们定义一个数列的$mex$为$mex1$，填充上这个$mex$出现的新的$mex$称为$mex2$，那么，对于比所有数列中最大的$mex2$还要大的数，一定无法变成另外一个数，因此，对于这一部分，我们直接通过等差数列来求和即可。

而对于小于这一部分的数呢，就$3$种情况：

$1.$这个数不等于这个数列的$mex1$，因此这个数可以变成$mex1$。

$2.$这个数是一个数列的$mex1$，因此这个数可以成为这个数列的$mex2$

$3.$这个数是一个数列的$mex1$或$mex2$，并且这个$mex1/mex2$可以成为另一个数列的$mex1$，因此它也可以成为另一个数列的$mex2$

综上，我们可以预处理出所有数列的$mex1$和$mex2$，然后让$mex1$向$mex2$连边。

由于题目中保证$\sum l_i$ 不超过$2\ast 10^5$，因此这个图最大也只有$4\ast 10^5$条边。

我们遍历一遍图，预处理出每个点最远能够到达的大小，然后再枚举累加$f(i)$即可，多余部分就使用等差数列来求即可。

代码

void solve() {
int n, m;
std::cin >> n >> m;
 
std::vector<std::vector<int>>a(n + 1);
for (int i = 1; i <= n; ++i) {
int l;
std::cin >> l;
for (int j = 1; j <= l; ++j) {
int x;
std::cin >> x;
a[i].push_back(x);
}
 
std::sort(a[i].begin(), a[i].end());
a[i].erase(std::unique(a[i].begin(), a[i].end()), a[i].end());
}
 
std::vector<std::array<int, 2>>b(n + 1);
auto get_mex = [&](int k) {
int t1 = -1, t2 = -1;
int x = 0;
for (int i = 0; i < a[k].size(); ++i) {
if (a[k][i] != i + x && t1 == -1) {
t1 = i;
x++;
if (i < a[k].size() && a[k][i] != i + 1) {
t2 = t1 + 1;
break;
}
}
else if (a[k][i] != i + x && t2 == -1) {
t2 = i + x;
break;
}
}
if (t1 == -1) {
t1 = a[k].size();
t2 = t1 + 1;
}
else if (t2 == -1) t2 = a[k].size() + 1;
 
b[k] = { t1,t2 };
};
 
int maxx = 0;
for (int i = 1; i <= n; ++i) {
get_mex(i);
maxx = std::max(maxx, b[i][1]);
}
 
std::vector<std::vector<int>>e(maxx + 1);
 
std::vector<int>d(maxx + 1);
for (int i = 1; i <= n; ++i) {
auto [m1, m2] = b[i];
 
d[m1]++;
e[m1].emplace_back(m2);
}
 
std::vector<int>to(maxx + 1);
for (int u = maxx; u >= 0; --u) {
to[u] = u;
for (auto &v : e[u]) {
to[u] = std::max(to[u], to[v]);
}
}
 
int mx = 0;
for (int i = 0; i <= maxx; i++) {
if (d[i] > 1) mx = std::max(mx, to[i]);
 
else if (d[i] == 1)mx = std::max(mx, i);
}
 
int res = 0;
for (int i = 0; i <= std::min(maxx, m); i++) {
res += std::max(to[i], mx);
}
 
if (m > maxx) res += (m + maxx + 1) * (m - maxx) >> 1;
 
std::cout << res << "\n";
}
 
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
 
int t = 1;
std::cin >> t;
 
while (t--) {
solve();
}
};

原文地址：https://blog.csdn.net/Antonio915/article/details/142721045

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！