题目名称 4052. [CSP 2024 J]接龙
输入输出 chain.in/out
难度等级 ★★
时间限制 2000 ms (2 s)
内存限制 512 MiB
测试数据 20
题目来源 Gravatarsyzhaoss 于2024-10-27加入
开放分组 全部用户
提交状态
分类标签
NOIP/CSP 动态规划 线性DP
分享题解
通过:2, 提交:11, 通过率:18.18%
GravatarAeeE5x 100 10.230 s 93.60 MiB C++
Gravatarsyzhaoss 100 12.840 s 91.14 MiB C++
Gravatar2_16鸡扒拌面 60 26.014 s 39.10 MiB C++
Gravatar1nclude 15 50.429 s 6.52 MiB C++
Gravatar1nclude 15 51.005 s 6.81 MiB C++
GravatarLixj 10 8.462 s 25.23 MiB C++
GravatarAlbert 0 0.062 s 3.34 MiB C++
Gravatar2_16鸡扒拌面 0 2.014 s 3.62 MiB C++
Gravatarxxz 0 30.791 s 135.46 MiB C++
Gravatarxxz 0 30.900 s 134.88 MiB C++
关于 接龙 的近10条评论(全部评论)
考试的时候写不出来 死了
GravatarAlbert
2024-11-03 07:58 2楼
VIP

#include<bits/stdc++.h>
using namespace std;
string a[55];
int ans=52;
int main() {
freopen("poker.in","r",stdin);
freopen("poker.out","w",stdout);
int n;
cin>>n;
ans-=n;
for(int i=1; i<=n; i++)cin>>a[i];
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
if(a[i]==a[j]&&i!=j) {
ans++;
break;
}
}
}
cout<<ans;
return 0;
}
Gravatarbaory
2024-10-29 21:32 1楼

4052. [CSP 2024 J]接龙

★★   输入文件:chain.in   输出文件:chain.out   简单对比
时间限制:2 s   内存限制:512 MiB

【题目描述】

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

总共有 $n$ 个人参与这个接龙游戏,第 $i$ 个人会获得一个整数序列 $S_i$ 作为他的词库。

一次游戏分为若干轮,每一轮规则如下:

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

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

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

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

【输入格式】

本题有多组测试数据。

输入的第一行包含一个正整数 $T$,表示数据组数。

接下来包含 $T$ 组数据,每组数据的格式如下:

第一行包含三个整数 $n, k, q$,分别表示参与游戏的人数、接龙序列长度上限以及任务个数。

接下来 $n$ 行:

第 $i$ 行包含 $(l_i + 1)$ 个整数 $l_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i}$,其中第一个整数 $l_i$ 表示序列 $S_i$ 的长度,接下来 $l_i$ 个整数描述序列 $S_i$。

接下来 $q$ 行:

第 $j$ 行包含两个整数 $r_j, c_j$,描述一个任务。

【输出格式】

对于每个任务:输出一行包含一个整数,若任务可以完成输出 $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

【样例1说明】

在下文中,我们使用 $\{A_i\} = \{A_1, A_2, \dots , A_r\}$ 表示一轮游戏中所有的接龙序列,$\{p_i\} = \{p_1, p_2, \dots , p_r\}$ 表示对应的接龙的人的编号。由于所有字符均为一位数字,为了方便我们直接使用数字字符串表示序列。

对于第一组询问,$p_1 = 1$、$A_1 = 12$ 是一个满足条件的游戏过程。

对于第二组询问,可以证明任务不可完成。注意 $p_1 = 1$、$A_1 = 1234$ 不是合法的游戏过程,因为此时 $|A_1| = 4 > k$。

对于第三组询问,$\{p_i\} = \{2, 1\}$、$\{A_i\} = \{12, 234\}$ 是一个满足条件的游戏过程。

对于第四组询问,可以证明任务不可完成。注意 $\{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\}$ 不是一个合法的游戏过程,因为尽管所有的接龙序列长度均不超过 $k$,但第二轮和第三轮由同一个人接龙,不符合要求。

对于第五组询问,$\{p_i\} = \{1, 2, 3, 1, 2, 3\}$、$\{A_i\} = \{12, 25, 51, 12, 25, 516\}$ 是一个满足条件的游戏过程。

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

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

【样例 2】

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

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

【样例 3】

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

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

【样例 4】

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

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

【样例 5】

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

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

【样例 6】

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

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

样例下载

【数据规模与约定】

对于所有测试数据,保证:

$1 \leq T \leq 5$;

$1 \leq n \leq 10^5$,$2 \leq k \leq 2 \times 10^5$,$1 \leq q \leq 10^5$;

$1 \leq l_i \leq 2 \times 10^5$,$1 \leq S_{i,j} \leq 2 \times 10^5$;

$1 \leq r_j \leq 10^2$,$1 \leq c_j \leq 2 \times 10^5$;

设 $\sum l$ 为单组测试数据内所有 $l_i$ 的和,则 $\sum l\leq 2\times 10^5$。

特殊性质 A:保证 $k = 2 \times 10^5$。

特殊性质 B:保证 $k ≤ 5$。

特殊性质 C:保证在单组测试数据中,任意一个字符在词库中出现次数之和均不超过 $5$。