AdditionalFile4967.zip

P3587 [POI 2015 R2] 项链分割 Necklace partition

题目描述

长度为 $n$ 的一串项链，每颗珠子是 $k$ 种颜色之一。第 $i$ 颗与第 $i-1,i+1$ 颗珠子相邻，第 $n$ 颗与第 $1$ 颗也相邻。

切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。

求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

输入格式

第一行 $n,k$（$2\leq k\leq n\leq 10^6$）。颜色从 $1$ 到 $k$ 标号。

接下来 $n$ 个数，按顺序表示每颗珠子的颜色。（保证 $k$ 种颜色各出现至少一次）。

输出格式

一行两个整数：方案数量，和长度差的最小值。

输入输出样例 #1

输入 #1

9 5
2 5 3 2 2 4 1 1 3

输出 #1

4 3

说明/提示

【样例解释】

四种方法中较短的一条分别是 $(5),(4),(1,1),(4,1,1)$。相差最小值 $6-3=3$。

原题名称：Podział naszyjnika。

#4967. 「POI2015 R2」项链分割 Necklace partition

标签: 传统 | 时间限制: 6000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Podział naszyjnika

我们有一条由 $n$ 个珠子组成的项链，每颗珠子属于 $k$ 种类型之一。珠子编号为 $1$ 到 $n$，$i$ 号珠子与 $i+1$ 和 $i-1$ 号珠子相邻（若存在），且 $1$ 号和 $n$ 号珠子也相邻。我们希望用两刀将项链切成两个非空部分，确保每种类型的珠子只出现在其中一部分（即若某部分含类型 $j$ 的珠子，另一部分不得含类型 $j$）。请计算有多少种切割方式，以及两部分长度差的最小值。

输入格式

第一行包含两个整数 $n, k$ $(2 \leq k \leq n \leq 1000000)$，分别表示项链长度和珠子类型数。珠子类型编号为 $1$ 到 $k$。

第二行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$ $(1 \leq r_i \leq k)$，$r_i$ 表示 $i$ 号珠子的类型。保证每种类型至少出现一次。

输出格式

输出一行，包含两个整数，第一个表示可行的切割方式数（保证至少有一种方式），第二个表示两部分长度差的最小值。

样例

输入

9 5
2 5 3 2 2 4 1 1 3

输出

4 3

有四种可行分割：较短部分可包含珠子 $(5)$、$(4)$、$(1, 1)$ 或 $(4, 1, 1)$。最后一种情况下，长度差为 $6 - 3 = 3$，是最优解。

附加样例

1. $n=10$，短项链，仅两种可行分割；
2. $n=1000$，每颗珠子类型不同，所有分割均有效；
3. $n=1000000, k=n/2$，项链形式为 $1, \ldots, k, k, \ldots, 1$。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000$。