AT_agc062_f.[AGC062F] Preserve Distinct

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 组牌堆，每组牌堆由写有 $1$ 到 $M$ 之间整数的卡片组成。第 $i$ 个牌堆有 $K_i$ 张卡片，从上到下第 $j$ 张卡片上写的整数为 $A_{i,j}$ 。

卡片上的整数最初满足以下约束：

对于每个整数 $x\ (1\leq x\leq M)$ ，写有 $x$ 的卡片恰好出现在 $N$ 个牌堆中的两个不同牌堆中，每个牌堆各有一张。
每个牌堆最上面一张卡片上的整数互不相同。

对于这 $N$ 个牌堆，可以进行如下操作：

选择一个仍有卡片的牌堆，丢弃最上面的一张卡片。但丢弃后，所有仍有卡片的牌堆的最上面一张卡片上的整数必须互不相同。

请你求出最多可以进行多少次操作。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $K_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K_1}$ $K_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K_2}$ $\vdots$ $K_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,K_N}$

输出格式

请输出答案。

输入输出样例

输入#1
```
2 4
4 1 2 3 4
4 3 2 1 4
```
输出#1
```
1
```
输入#2
```
4 6
2 6 4
3 2 5 3
4 3 1 5 6
3 4 1 2
```
输出#2
```
12
```
输入#3
```
3 3
2 1 2
2 2 3
2 3 1
```
输出#3
```
0
```

输入#4

12 40
4 35 39 11 21
7 31 29 16 15 30 32 34
4 21 27 38 40
11 17 28 26 23 33 22 3 36 8 1 20
1 30
4 40 38 24 6
8 8 36 9 10 5 7 20 4
10 5 10 9 3 22 33 23 26 28 17
4 15 16 29 31
11 19 13 12 18 25 2 39 35 7 14 37
3 4 1 14
13 24 27 11 2 25 18 12 13 19 32 37 6 34

输出#4

说明/提示

限制条件

$2 \leq N \leq M$
$2 \leq M \leq 2 \times 10^5$
$1 \leq K_i \leq M$
$1 \leq A_{i,j} \leq M$
对于每个整数 $x\ (1\leq x\leq M)$ ， $x=A_{i,j}$ 成立的 $i,j$ 组合恰好有 $2$ 个，且这两个 $i$ 互不相同。
$A_{i,1}\ (1\leq i\leq N)$ 互不相同。
输入的所有值均为整数。

样例解释 1

一开始对第 $1$ 个牌堆进行操作后，该牌堆的卡片从上到下依次为 $2,3,4$ 。此时如果再次对第 $1$ 个牌堆操作，则第 $1$ 个和第 $2$ 个牌堆的最上面一张卡片上的整数都会变成 $3$ ，因此不能再对第 $1$ 个牌堆操作。同理也不能对第 $2$ 个牌堆操作。因此如果一开始对第 $1$ 个牌堆操作，最多只能操作 $1$ 次。如果一开始对第 $2$ 个牌堆操作，最多也只能操作 $1$ 次，所以答案是 $1$ 。

样例解释 2

通过合理操作可以丢弃所有卡片。

样例解释 3

有时一次操作都无法进行。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页