TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P7299
  • 問題
  • P7299「APIO2020」粉刷墙壁
    制限 : 時間制限 : 20000 MS   メモリ制限 : - KB
    審判説明 : 1.5s,512M
    問題説明

    注意

    NKOJ暂不支持交互,请在提交时将paint.h粘贴到代码前面

    距离上一次 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}\) 种颜色,\(\ldots\),或第 \(B_{j, A_j -1}\) 种颜色。

    Pak Dengklek 可以给承包商公司提出一些要求。在单个要求中,Pak Dengklek 将给出两个参数 \(x\)\(y\),其中 $0 \le x \lt M, 0 \le y \le N - M$。承包商公司将会指派第 \(((x + l) \bmod M)\) 个承包商粉刷第 \((y + l)\) 段墙壁,其中 $0 \le l \lt 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] ... 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 的返回值。

    入力形式

    出力形式

    サンプル入力 1

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

    サンプル出力 1

    3

    サンプル入力 2

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

    サンプル出力 2

    -1

    ヒント

    样例解释 1

    \(N = 8, M = 3, K = 5, C = [3, 3, 1, 3, 4, 4, 2, 2], A = [3, 2, 2], B = [[0, 1, 2], [2, 3], [3, 4]]\)。Pak Dengklek 可以提出下列的要求。

    \(x = 1, y = 0.\) 这是一个有效的要求,第一个承包商可以粉刷第零段墙壁,第二个承包商可以粉刷第一段墙壁,第零个承包商可以粉刷第二段墙壁。
    \(x = 0, y = 2.\) 这是一个有效的要求,第零个承包商可以粉刷第二段墙壁,第一个承包商可以粉刷第三段墙壁,第二个承包商可以粉刷第四段墙壁。
    \(x = 2, y = 5.\) 这是一个有效的要求,第二个承包商可以粉刷第五段墙壁,第零个承包商可以粉刷第六段墙壁,第一个承包商可以粉刷第七段墙壁。

    容易看出 Pak Dengklek 不能用少于 $3$ 个的要求来达到预期,因此 minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]]) 应该返回 $3$。

    样例解释 2

    \(N = 5, M = 4, K = 4, C = [1, 0, 1, 2, 2]\)。由于第三个承包商只喜欢第 $3$ 种颜色但没有任何一段墙壁能被该颜色粉刷,Pak Dengklek 无法给出任何有效指令。因此 minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]]) 应该返回 \(-1\)

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

    • $1 \le N \le 100,000$
    • $1 \le M \le \min(N, 50,000)$
    • $1 \le K \le 100,000$
    • $0 \le C_i \lt K$
    • $1 \le A_j \le K$
    • $0 \le B_{j,0} \lt B_{j,1} \lt \ldots \lt B_{j,A_j-1} \lt K$
    • \(\sum f(k)^2 \le 400\,000\)
    子任务 附加限制 分值
    $1$ \(f(k)\le 1\) $12$
    $2$ \(N \le 500\), \(M \le \min(N, 200)\), \(\sum f(k)^2 \le 1000\) $15$
    $3$ \(N \le 500\), \(M \le \min(N, 200)\) $13$
    $4$ \(N \le 20\,000\), \(M \le \min(N, 2000)\) $23$
    $5$ 无附加限制 $37$

    paint.h

    #include <vector>
    
    int minimumInstructions(
        int N, int M, int K, std::vector<int> C,
        std::vector<int> A, std::vector<std::vector<int>> B);
    
    #include <cassert>
    #include <cstdio>
    
    #include <string>
    #include <vector>
    
    int main() {
      int N, M, K;
      assert(3 == scanf("%d %d %d", &N, &M, &K));
      
      std::vector<int> C(N);
      for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &C[i]));
      }
    
      std::vector<int> A(M);
      std::vector<std::vector<int>> B(M);
      for (int i = 0; i < M; ++i) {
        assert(1 == scanf("%d", &A[i]));
        B[i].resize(A[i]);
        for (int j = 0; j < A[i]; ++j) {
          assert(1 == scanf("%d", &B[i][j]));
        }
      }
    
      int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
      printf("%d\n", minimum_instructions);
    
      return 0;
    }
    

    ソース  APIO2020 T1