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了,可以的话,请您参考添加页面,与大家一起分享你的题解!