#P14967. [2026年重庆省队集训]简单题

    ID: 14183 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>图论组合数学CF2300数学二分图网络流

[2026年重庆省队集训]简单题

题目描述

给定一个 2×n2\times n 的整数矩阵 aa 和正整数 mm,满足 1≤∣ai,j∣≤m1\leq \lvert a_{i,j}\rvert \leq m。

有一个值域为 [1,m][1,m] 的排列 pp,令大小为 2×n2\times n 的正整数矩阵 bb 为:

$b_{i,j} = \begin{cases} a_{i,j}&a_{i,j}>0\\p_{-a_{i,j}}&a_{i,j}<0\end{cases}.$

定义矩阵 bb 的四连通块为,选择矩阵 bb 的若干元素,使得这些元素是四连通的,并且所有元素的值相等。

你需要选择一个值域为 [1,m][1,m] 的排列 pp,求出矩阵 bb 的极大四连通块数的最小值。

输入格式

第一行为二个正整数 n,mn,m,代表矩阵大小及试题约定中的mm

接下来两行每行 nn 个整数,表示矩阵 aa。

输出格式

输出一行一个正整数表示矩阵 bb 的极大四连通块数的最小值。

样例输入 1

5 3
1 2 1 2 1
-1 -2 -3 -3 -3

样例输出 1

5

样例输入 2

15 3
1 -1 1 -1 -1 -2 2 -1 3 3 3 -3 -2 -2 1
2 -1 1 1 -1 -2 -1 2 -2 3 3 -2 -2 -2 3

样例输出 3

9

样例解释

对于第一个样例:

选择 p=[3,2,1]p=[3,2,1],矩阵 bb 为:

1 2 1 2 1
3 2 1 1 1

其总共有 55 个极大四连通块,标记如下:

A B C D C
E B C C C

可以证明矩阵 bb 的极大四连通块数的最小值为 55。

数据范围

对于所有数据,

  • 1≤n≤1051\leq n\leq 10^5,
  • 1≤m≤3001\leq m\leq 300,
  • ∀1≤i≤2,1≤j≤n\forall 1\leq i\leq 2,1\leq j\leq n,1≤∣ai,j∣≤m1\leq\lvert a_{i,j}\rvert\leq m。
子任务编号 n≤n\leq m≤m\leq 特殊性质 分数 子任务依赖
11 1010 55 - 55 -
22 10510^5 1010 11
33 300300 1515 A 1515 -
44 10510^5 1010 33
55 300300 - 2020 1,31,3
66 10510^5 1010 2,4,52,4,5
77 300300 A 2020 44
88 - 1010 6,76,7
  • 特殊性质 A:∀1≤i≤n\forall1\leq i\leq n,a1,i=a2,ia_{1,i}=a_{2,i}。