[CSP-J 2024] 接龙
原题链接：34464.[CSP-J 2024] 接龙
2025-08-10 10:36:15
发布于：浙江
81阅读
0回复
0点赞
70pts
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5;
/*
状态：设dp[i][j]为第i轮，以j结尾的可能性
初始状态：dp[i][j]=0
状态：dp[i][j]=-1(指不存在以j结尾) ,dp[i][j]=0(存在以j结尾同事有行满足),dp[i][j]=x(存在j结尾，但只有x行)
a[x][y]表示x个字符的第y个
枚举r轮，每一轮再去枚举是否可以以数a[x][y]为结尾
状态转移方程：：dp[i][j]=
if(dp[i-1][j]!=-1){
//说明上一轮以j为结尾的数是存在的，但仅存在剩余不足2个--->dp[i][j]=-1;
//否则可选择是否继承
//如果只有一种且在同一行--->-1
//如果有多种或不在一行--->{0(存在多个),x(只有一个)}
}else {
dp[i][j]=-1;
}
*/
int dp[101][N+1];
void solve(){
int n,k,q;
cin>>n>>k>>q;//输入行数、每行最多往前看的列数和查询次数
vector<vector<int> >a(n+1); //二维数组，a[i]存储数第i行的数字
vector<int>sz(n+1);//sz[i]表示第i行的数字个数
for(int i=1;i<=n;i++){
cin>>sz[i];//输入第i行的数字个数
a[i].resize(sz[i]+1);//调整a[i]的大小
for(int j=1;j<=sz[i];j++){
cin>>a[i][j];//输入第i行的第j个数字
}
}
/*
dp[i][j]=-1表示不能以j为结尾完成接龙
dp[i][j]=0表示当前以i为结尾的接龙有多行符合的情况
dp[i][j]=x 表示当前以j为结尾的接龙有唯一情况，且当前行为x
*/
int R=100;//定义最大轮数为100
dp[0][1]=0;//初始化第0轮，以1为结尾的情况为0(初始状态)
for(int r=1;r<=R;r++){//遍历每一轮
for(int i=1;i<=n;i++){//遍历每一行
for(int j=2;j<=sz[i];j++){//遍历每一行的数字(从第2个开始)
int now=a[i][j];//当前数字
if(dp[r][now]==0)continue;//如过当前数字在本轮已经被标记为多行符合，则跳过
//遍历当前数字前面的k-1个数字(最多往前看k-1个)
for(int f=max(1ll,j-k+1);f<j;f++){
int pre=a[i][f];//前一个数字
//如果前一个数字在上一轮不可用，或者上一轮的行数与当前行相同
if(dp[r-1][pre]==-1||dp[r-1][pre]==i)continue;
//如果当前数字在本轮还没有被处理，则跳过
if(dp[r][now]==-1)dp[r][now]=i;
else if(dp[r][now]!=i)dp[r][now]=0;
}
}
}
}
while(q--){
int r,c;
cin>>r>>c;
if(dp[r][c]>=0){
cout<<1<<"\n";
}else{
cout<<0<<"\n";
}
}
return;
}
signed main(){
freopen("chain.in","r",stdin);
freopen("chain.out","w",stdout);
int T=1;
cin>>T;
while(T--){
memset(dp,-1,sizeof dp);
solve();
}
fclose(stdin);
fclose(stdout);
return 0;
}
100pts
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
int dp[101][N + 1]; // 动态规划数组, dp[round][C] 表示在第 round 轮时, 以数字 c 结尾的接龙情况
int n, k, q;
void solve(){
cin >> n >> k >> q; // 输入行数、每行最多往前看的列数和查询次数
vector<vector<int>> a(n + 1); // 二维数组, a[i] 存储第 i 行的数字
vector<int> sz(n + 1); // sz[i] 表示第 i 行的数字个数
for (int i = 1; i <= n; i++) {
cin >> sz[i]; // 输入第 i 行的数字个数
a[i].resize(sz[i] + 1); // 调整 a[i] 的大小
for (int j = 1; j <= sz[i]; j++) {
cin >> a[i][j]; // 输入第 i 行的第 j 个数字
}
}
// dp[i][j] = -1 表示不能以 j 结尾完成接龙
// dp[i][j] = 0 表示当前以 j 结尾的接龙有多行符合的情况
// dp[i][j] = x 表示当前以 j 结尾的接龙有唯一情况, 且当前行是 x
int R = 100; // 定义最大轮数为 100
dp[0][1] = 0; // 初始化第 0 轮, 以 1 结尾的情况为 0 (初始状态)
for (int round = 1; round <= R; round++) { // 遍历每一轮
for (int i = 1; i <= n; i++) { // 遍历每一行
int l = 0, pre = -1; // l 表示当前行的起始位置, pre 表示前一个有效状态的行号
for (int j = 1; j <= sz[i]; j++) { // 遍历每一行的每个数字
int val = a[i][j]; // 当前数字
// 如果前一个有效状态不是当前行, 并且当前数字在允许的范围内
if (!(pre == -1 || pre == i)) {
if (l + k - 1 >= j) {
// 如果当前数字在本轮还没有被处理, 则标记为当前行
if (dp[round][val] == -1) {
dp[round][val] = i;
}
// 如果当前数字在本轮已经被其他行处理过, 则标记为多行符合
else if (dp[round][val] != i) {
dp[round][val] = 0;
}
}
}
// 获取上一轮当前数字的状态
int now = dp[round - 1][a[i][j]];
// 如果上一轮的状态有效, 并且不是当前行或者多行符合的情况
if (now != -1 && (now == 0 || now != i)) {
pre = now; // 更新前一个有效状态的行号
l = j; // 更新当前行的起始位置
}
}
}
}
// 处理每个查询
while (q--) {
int r, c;
cin >> r >> c; // 输入查询的轮数和数字
// 如果 dp[r][c] >= 0，说明存在符合条件的情况，输出 1，否则输出 0
if (dp[r][c] >= 0) {
cout << 1 << endl;
}
else {
cout << 0 << endl;
}
}
}
int main(){
freopen("chain.in","r",stdin);
freopen("chain.out","w",stdout);
int t;
cin >> t;
while(t--){
memset(dp,-1,sizeof dp);
solve();
}
fclose(stdin);
fclose(stdout);
return 0;
}
有帮助，赞一个