社区讨论

警示后人,如果你用了链式前向星

P11230[CSP-J 2024] 接龙参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhizw89o
此快照首次捕获于
2025/11/03 18:26
4 个月前
此快照最后确认于
2025/11/03 18:26
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,k,q,dp[110][N];
// int head[N];
// struct edge{
//     int to,nxt;
// }g[N<<1];
// int tot;
// void add(int u,int v){
//     g[++tot].to=v;
//     g[tot].nxt=head[u];
//     head[u]=tot;
// }
vector<int>g[N];
void slove(){
    memset(dp,-1,sizeof(dp));
    scanf("%d%d%d",&n,&k,&q);
   // tot=0;
    for(int i=1;i<=n;i++){
        int l;scanf("%d",&l);
        //head[i]=0;
        g[i].clear();
        while(l--){
            int v;scanf("%d",&v);
            g[i].push_back(v);
        }
    }
    dp[0][1]=0;
    for(int r=1;r<=100;r++){
        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int u:g[i]){
                //int u=g[now].to;
                //cout<<u<<' ';
                if(cnt>0){
                    if(dp[r][u]==-1)dp[r][u]=i;
                    else if(dp[r][u]!=i)dp[r][u]=0;
                    cnt--;
                }
                //cout<<cnt<<endl;
                if(dp[r-1][u]!=-1&&dp[r-1][u]!=i)cnt=k-1;
            }
            //cout<<endl;
        }
    }
    while(q--){
        int r,c;scanf("%d%d",&r,&c);
        printf("%d\n",(dp[r][c]==-1)?0:1);
    }
}
int main() 
{
    int t;scanf("%d",&t);
    while(t--)slove();
    return 0;
}
若你采用了链式前向星,你的枚举会从后往前枚举,导致错误,然后你的dp就挂了。

回复

1 条回复,欢迎继续交流。

正在加载回复...