Skip to content

14080: 【原4080】切项链

题目

题目描述

author: BowenTan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4080 时间限制：5s

Description

tbw有一条项链，他想把他切开（他真的是有猫饼）。

他还要你来切。

长度为n(n≤10^6)的一串项链，每颗珠子是k(k≤10^6)种颜色之一。 第i颗与第i−1,i+1颗珠子相邻，第n颗与第1颗也相邻。 现在你切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。 求方案数量（保证至少存在一种），以及切成的两段长度之差（当然是指绝对值）的最小值。

input format

本题包含多组输入数据，数据开始首先输入数据组数T(T<=6)

每组数据包含两个数n,k(k<=n)，意义如题目描述。

output format

对于每一组输入，分别输出方案数和长度之差的最小值。

sample input

1
9 5
2 5 3 2 2 4 1 1 3

sample output

4 3

sample explanation

4种方案分别是 2 |5| 3 2 2 4 1 1 3 2 5 3 2 2 |4| 1 1 3 2 5 3 2 2 4 |1 1| 3 2 5 3 2 2 |4 1 1| 3 最后一种方案长度差是|6-3|=3

limits

  • 对于30%的数据，k<=n<=1000
  • 对于100%的数据，2<=k<=n<=10^6

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！