题库 信息学奥赛题库 题目列表 接龙(chain)【题目描述】在玩惯了成语接龙之后,小&nb...
问答题

接龙(chain)

【题目描述】

在玩惯了成语接龙之后,小 和他的朋友们发明了一个新的接龙规则。

总共有 个人参与这个接龙游戏,第 个人会获得一个整数序列 S作为他的词库。 一次游戏分为若干轮,每一轮规则如下:

• 个人中的某个人 带着他的词库 S进行接龙。若这不是游戏的第一轮,那么 这一轮进行接龙的人不能与上一轮相同,但可以与上上轮或更往前的轮相同。

• 接龙的人选择一个长度在 [2, k的 S的连续子序列 作为这一轮的, 其中 是给定的常数。若这是游戏的第一轮,那么 需要以元素 开头,否则 需要以上一轮的接龙序列的最后一个元素开头。

– 序列 是序列 的连续子序列当且仅当可以通过删除 的开头和结尾的 若干元素(可以不删除)得到 A

为了强调合作,小 给了 个参与游戏的人 个任务,第 个任务需要这 个人 进行一次游戏,在这次游戏里进行恰好 r轮接龙,且最后一轮的接龙序列的最后一个 元素恰好为 cj。为了保证任务的可行性,小 请来你判断这 个任务是否可以完成的, 即是否存在一个可能的游戏过程满足任务条件。

【输入格式】

从文件 chain.in 中读入数据。
....
输入的第一行包含一个正整数 T,表示数据组数。
接下来包含 
组数据,每组数据的格式如下:
第一行包含三个整数 
n, k, q,分别表示参与游戏的人数、接龙序列长度上限以及任

务个数。
接下来 
行:

i行包含(l+1)个整数li,Si,1,Si,2,··· ,Si,li,其中第一个整数l表示序列S的 长度,接下来 l个整数描述序列 Si

接下来 行:
第 
行包含两个整数 r, c,描述一个任务。

【输出格式】

输出到文件 chain.out 中。 对于每个任务:输出一行包含一个整数,若任务可以完成输出 1,否则输出 0

【样例 1 输入】

1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6 
1 1
7 7

【样例 1 输出】

1
0
1
0
1
0
0

【样例 解释】

在下文中,我们使用 {Ai{A1, A2· · · , Ar表示一轮游戏中所有的接龙序列, {pi{p1, p2· · · , pr表示对应的接龙的人的编号。由于所有字符均为一位数字,为了 方便我们直接使用数字字符串表示序列。

  • 对于第一组询问,p= 1A= 12 是一个满足条件的游戏过程。

  • 对于第二组询问,可以证明任务不可完成。注意 p= 1A= 1234 不是合法的

    游戏过程,因为此时 |A1= 4 > k

  • 对于第三组询问,{pi{21}{Ai{12234是一个满足条件的游戏过程。

  • 对于第四组询问,可以证明任务不可完成。注意 {pi{211}{Ai{122334}

    不是一个合法的游戏过程,因为尽管所有的接龙序列长度均不超过 k,但第二轮 和第三轮由同一个人接龙,不符合要求。

  • 对于第五组询问,{pi{123123}{Ai{1225511225516是一个 满足条件的游戏过程。

  • 对于第六组询问,可以证明任务不可完成。注意每个接龙序列的长度必须大于等 于 2,因此 A= 1 不是一个合法的游戏过程。

  • 对于第七组询问,所有人的词库均不存在字符 7,因此任务显然不可完成。 

    【样例 2

    见选手目录下的 chain/chain2.in 与 chain/chain2.ans。 该样例满足测试点 的特殊性质。

    【样例 3
    见选手目录下的 chain/chain3.in 与 chain/chain3.ans

    该样例满足测试点 的特殊性质。 

    【样例 4

    见选手目录下的 chain/chain4.in 与 chain/chain4.ans

    该样例满足特殊性质 A,其中前两组测试数据满足 ≤ 1000≤ 10、单组测试数 据内所有词库的长度和 ≤ 2000≤ 1000

    【样例 5

    见选手目录下的 chain/chain5.in 与 chain/chain5.ans

    该样例满足特殊性质 B,其中前两组测试数据满足 ≤ 1000≤ 10、单组测试数 据内所有词库的长度和 ≤ 2000≤ 1000

    【样例 6

    见选手目录下的 chain/chain6.in 与 chain/chain6.ans

    该样例满足特殊性质 C,其中前两组测试数据满足 ≤ 1000≤ 10、单组测试数 据内所有词库的长度和 ≤ 2000≤ 1000

    【数据范围】

    对于所有测试数据,保证:
    • ≤ ≤ 5;
    • 1n1052k2×1051q105• 1l2×1051Si,j 2×105;

        • 1r1021c2×105;

        • 设 ∑ 所有 l的和,则 ∑ ≤ × 105

特殊性质 A:保证 = 2 × 105
特殊性质 
B:保证 ≤ 5
特殊性质 
C:保证在单组测试数据中,任意一个字符在词库中出现次数之和均不超过 5

题目信息
完善程序 2024年 复赛
-
正确率
0
评论
71
点击