loj#P3345. 「APIO2020」粉刷墙壁

「APIO2020」粉刷墙壁

题目描述

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 11 (Clang)
  • C++ 11 (NOI)
  • C++ 17
  • C++ 17 (Clang)

距离上一次 Pak Dengklek 在他的家中粉刷墙壁已经过了一段时间,所以他想重新粉刷一次。 他家的墙壁由 NN 段组成, 它们从 00N1N - 1 编号。本题中我们假设存在 KK 种不同的颜色,颜色用从 00K1K - 1 的整数表示(例如, 红色用 00 表示, 蓝色用 11 表示,以此类推)。Pak Dengklek 希望用第 CiC_i 种颜色来粉刷第 ii 段的墙壁。

为了粉刷墙壁, Pak Dengklek 雇用了一家有 MM 个承包商的承包商公司,承包商从 00M1M - 1 编号。对 Pak Dengklek 来说不幸的是,承包商只愿意粉刷他们自己喜欢的颜色。具体来说,第 jj 个承包商喜欢 AjA_j 种颜色,并且只想用下列颜色来粉刷墙壁:第 Bj,0B_{j,0} 种颜色,第 Bj,1B_{j,1} 种颜色,\ldots,或第 Bj,Aj1B_{j, A_j -1} 种颜色。

Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中,Pak Dengklek 将给出两个参数 xxyy,其中 0x<M,0yNM0 \le x \lt M, 0 \le y \le N - M。承包商公司将会指派第 ((x+l)modM)((x + l) \bmod M) 个承包商粉刷第 (y+l)(y + l) 段墙壁,其中 0l<M0 \le l \lt M。如果存在一个 ll 使得第 ((x+l)modM)((x + l) \bmod M) 个承包商不喜欢第 Cy+lC_{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)

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

  • NN:一个整数表示墙壁的段数。
  • MM:一个整数表示承包商的数量。
  • KK:一个整数表示颜色的种数。
  • CC:一个长度为 NN 的整数序列,表示每段墙壁预期的颜色。
  • AA:一个长度为 MM 的整数序列,表示承包商喜欢的颜色数。
  • BB:一个长度为 MM 的每个元素为序列的序列,表示承包商喜欢的具体颜色。

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

样例评测库

样例评测库将读入以下格式的数据:

N M K
C[0] C[1] ... C[N-1]
A[0] B[0][0] B[0][1] ... B[0][A[0]-1]
A[1] B[1][0] B[1][1] ... B[1][A[1]-1]
.
.
.
A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1]

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

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

数据范围与提示

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

  • 1N1000001 \le N \le 100\,000
  • 1Mmin(N,50000)1 \le M \le \min(N, 50\,000)
  • 1K1000001 \le K \le 100\,000
  • 0Ci<K0 \le C_i \lt K
  • 1AjK1 \le A_j \le K
  • $0 \le B_{j,0} \lt B_{j,1} \lt \ldots \lt B_{j,A_j-1} \lt K$
  • f(k)2400000\sum f(k)^2 \le 400\,000
子任务 附加限制 分值
11 f(k)1f(k)\le 1 1212
22 N500N \le 500, Mmin(N,200)M \le \min(N, 200), f(k)21000\sum f(k)^2 \le 1000 1515
33 N500N \le 500, Mmin(N,200)M \le \min(N, 200) 1313
44 N20000N \le 20\,000, Mmin(N,2000)M \le \min(N, 2000) 2323
55 无附加限制 3737