「题目描述」

这个问题是源于一个在棋盘上玩的，由Sid Sackson设计的名叫Can’t stop的游戏的。这个问题与Can’t stop有一定的相似之处，但是不需要玩过Can’t stop。

你在玩一个（非常大型的）棋盘游戏。在这个游戏里面，给出了一个长度为N的roll set的序列。每个roll set包括D个die roll，每个die roll是一个正整数。

你需要找到序列中总长度最大的极好的区间。区间即为连续的一段roll set。如果存在k个数使某个区间内的所有roll set都至少包含其中一个，那么，这个区间就被认为是极好的。

例如：d=2，k=3时，roll set如下：

Set 0: 10 20

Set 1: 50 60

Set 2: 70 30

Set 3: 40 40

Set 4: 30 30

Set 5: 20 40

从0到2的区间是极好的，因为从0到2中的每个roll set都包含了10,50或70 。从1到5的区间也是极好的，因为1到5的所有roll set都包含50,30或40。它包含了5个roll set，是总长度最大的极好的区间。

你的任务是输出总长度最大的极好的区间的第一个元素的下标和最后一个元素的下标。如果有多个长度一样的，输出第一个元素下标最小的。请注意下标从0开始。

「输入说明」

第一行包含一个整数T，表示数据组数。接下来T组数据。

每组数据的第一行是三个正整数N,D,k，描述如上。接下来一行，包含N*D个整数，前D个整数表示第一个roll set ，接下来D个表示第二个roll set，以此类推。

「输出说明」

对于每个case，输出一行，”Case #x: y z”，x表示case标号（从1开始），y和z是答案区间的第一个和最后一个元素的下标。

「样例输入」

4

8 1 2

1 2 3 2 4 5 4 6

4 3 2

1 2 3 4 5 6 7 8 9 10 11 12

6 2 3

10 20 50 60 70 30 40 40 30 30 20 40

10 1 3

2 4 3 1 4 5 3 1 1 2

「样例输出」

Case #1: 1 3

Case #2: 0 1

Case #3: 1 5

Case #4: 1 4

「数据范围」

• 对于45%的数据，N<=1000
• 对于50%的数据，k=2
• 前两部分数据共计70%
• 对于100%的数据，2<=k<=3

输入文件在4.8M以内

T=10.
1 ≤ D ≤ 4.
1 ≤ 每个die roll ≤ 105.
对于最多6个case, 1 ≤ N ≤ 105.

对于其他所有的case, 1 ≤ N ≤ 103.

题解

枚举起点暴力45分，加点优化可以跑到60分

考虑分治，分成俩半，考虑跨越中间的序列，中间位置枚举选了哪个数，然后向两边几种情况拓展一下

递归两边区间

复杂度\(O(Tnlogn*d^k*2^(k-1))\)

加点剪枝就能秒了

暴力

ac