UOJ Logo Universal Online Judge

UOJ

#555. 【APIO2020】粉刷墙壁

统计

由于某些原因本题仅支持 C++ 各版本语言的提交。

距离上一次 Pak Dengklek 在他的家中粉刷墙壁已经过了一段时间,所以他想重新粉刷一次。他家的墙壁由 N 段组成,它们从 $0$ 到 $N −1$ 编号. 本题中我们假设存在 $K$ 种不同的颜色,颜色用从 $0$ 到 $K −1$ 的整数表示(例如, 红色用 $0$ 表示, 蓝色用 $1$ 表示, 以此类推)。Pak Dengklek 希望用第 $C[i]$ 种颜色来粉刷第 $i$ 段的墙壁。

为了粉刷墙壁, Pak Dengklek 雇用了一家有 $M$ 个承包商的承包商公司,承包商从 $0$ 到 $M −1$ 编号。对 Pak Dengklek 来说不幸的是,承包商只愿意粉刷他们自己喜欢的 颜色。具体来说,第 $j$ 个承包商喜欢 $A[j]$ 种颜色,并且只想用下列颜色来粉刷墙壁:第 $B[j][0]$ 种颜色,第 $B[j][1]$ 种颜色,$\cdots$,或第 $B[j][A[j]−1]$ 种颜色。

Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中,Pak Dengklek 将 给出两个参数 $x$ 和 $y$, 其中 $0 \le x < M$ , $0 \le y \le N − M$。承包商公司将会指派第 $((x + l)\ \bmod M)$ 个承包商粉刷第 $(y + l)$ 段墙壁,其中 $0 \le l < M$。如果存在一个 $l$ 使 得第 $((x + l)\ \bmod M)$ 个承包商不喜欢第 $C[y + l]$ 种颜色,那么该要求将无效。

Pak Dengklek 需要为每个要求付费,因此他想知道为了使墙壁中每个段都能用自己预期的颜色粉刷,他至少要提出多少个要求,或是确认他的预期无法达到。每一段墙 壁可以被粉刷多次,但必须保证每次粉刷的颜色都是 Pak Dengklek 所预期的。

实现细节

你必须引用 paint.h 头文件。

你必须实现 minimumInstructions 函数:

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B)
  • $N$:一个整数表示墙壁的段数。

  • $M$:一个整数表示承包商的数量。

  • $K$:一个整数表示颜色的种数。

  • $C$:一个长度为 $N$ 的整数序列,表示每段墙壁预期的颜色。

  • $A$:一个长度为 $M$ 的整数序列,表示承包商喜欢的颜色数。

  • $B$:一个长度为 $M$ 的每个元素为序列的序列,表示承包商喜欢的具体颜色。

该函数将被评测库恰好调用一次。

该函数必须返回一个整数,表示 Pak Dengklek 为了让墙壁按预期粉刷所需要提出的最小要求数;若预期无法达到则返回 $-1$。

样例评测库

按照如下格式读入数据。

$N\ M\ K$

$C[0]\ C[1]\ \cdots \ C[N-1]$

$A[0]\ B[0][0]\ B[0][1]\ \cdots \ B[0][A[0]-1]$

$A[1]\ B[1][0]\ B[1][1]\ \cdots \ B[1][A[1]-1]$

$\cdots$

$\cdots$

$A[M-1]\ B[M-1][0]\ B[M-1][1]\ \cdots \ B[M-1][A[M-1]-1]$

样例评测库将输出函数 minimumInstructions 的返回值。

样例一

input

8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

output

3

限制与约定

对于 $0 \le k < K$,令 $f(k)$ 表示喜欢第 $k$ 种颜色的承包商数量。

对于所有测试数据:

  • $1 \le N \le 100000.$
  • $1 \le M \le \min(N,50000)$
  • $1 \le K \le 100000.$
  • $0 \le C[i] < K$.
  • $1 \le A[j] \le K$
  • $0 \le B[j][0] < B[j][1] < ... < B[j][A[j]−1] < K$.
  • $\sum f(k)^2 \le 400000$.
子任务 附加限制 分值 依赖的数据包
1 $f(k) \le 1$ 12 1, 2, 3, 4
2 $N \le 500,M \le \min(N,200),\sum f(k)^2 \le 1000$ 15 1, 5
3 $N \le 500,M \le \min(N,200)$ 13 1, 2, 5, 6
4 $N \le 20000,M \le \min(N,2000)$ 23 1, 2, 3, 5, 6, 7
5 37 1, 2, 3, 4, 5, 6, 7, 8

实际测试中,前 8 个 subtask 为数据包,后 5 个 subtask 为 5 个子任务。

时间限制:$2 \texttt{s}$

空间限制:$512 \texttt{MB}$

 下载

样例及测评库下载