P11230 [CSP-J 2024] 接龙

· · 题解

upd：有一些小错误。

upd：放了 Code。

思路：

容易发现是动态规划题，状态是 dp_{k, i, j} 表示在 k 轮第 i 个人是否可以出以第 j 张牌结尾的接龙序列，然后考虑状态转移方程：

dp_{k,i,j} = \bigvee [l \ne i \& a_{l,p} \in S_{i, j - k + 1,j}] dp_{k -1, l, p}

其中 S_{i, l, r} 表示 a_{i, l \cdots r} 这些数构成的集合。

然后考虑令：

s_{k, x} = \sum_{i = 1}^n \sum_{j = 1} ^{len_i} [a_{i, j} = x] dp_{k,i,j} \\ g_{k, i, x} = \sum_{j = 1} ^{len_i} [a_{i, j} = x] dp_{k,i,j}

则状态转移方程优化为：

dp_{k, i, j} = \bigvee [s_{k - 1, a_{l,p}} \ne g_{k - 1, i, a_{l,p}} ] (a_{l,p} \in S_{i, j - k + 1,j})

然后可以走指针优化一下，就可以实现 O(1) 转移了，时间复杂度为 O(q + nr)。

考场代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define mkp(x, y) make_pair(x, y)
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
using namespace std;
typedef long long ll;
const int N  = 2e5 + 10, M = 105;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x < 10){
        putchar('0' + x);
        return ;
    }
    write(x / 10);
    write(x % 10);
    return ;
}
int T, n, m, q, r, c, cnt, Max;
int len[N], h[N], f[N], s[N];
bool F[M][N];
vector<int> a[N], id[N], g[N];
vector<bool> dp[N];
void solve(){
    Max = 0;
    n = read(), m = read(), q = read();
    for(int i = 1; i <= n; ++i){
        cnt = 0;
        a[i].clear(), g[i].clear(), id[i].clear(), dp[i].clear();
        len[i] = read();
        for(int j = 0; j < len[i]; ++j){
            a[i].push_back(read());
            h[++cnt] = a[i][j];
            Max = max(Max, a[i][j]);
        }
        sort(h + 1, h + cnt + 1);
        cnt = unique(h + 1, h + cnt + 1) - (h + 1);
        for(int j = 0; j < len[i]; ++j)
          id[i].push_back(lower_bound(h + 1, h + cnt + 1, a[i][j]) - (h + 1));
        dp[i].resize(len[i]); 
        g[i].resize(len[i]); 
    }
    for(int i = 1; i <= Max; ++i){
        s[i] = 0;
        for(int j = 1; j <= 100; ++j)
          F[j][i] = 0;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < len[i]; ++j){
            if(j - m >= 0)
              --f[a[i][j - m]];
            if(j && f[1]){
                F[1][a[i][j]] = dp[i][j] = 1;
                ++s[a[i][j]];
                ++g[i][id[i][j]];
            }
            ++f[a[i][j]];
        }
        for(int j = 0; j < len[i]; ++j)
          f[a[i][j]] = 0;
    }
    for(int k = 2; k < M; ++k){
        for(int i = 1; i <= n; ++i){
            int sum = 0;
            for(int j = 0; j < len[i]; ++j){
                dp[i][j] = 0;
                if(j - m >= 0){
                    --f[a[i][j - m]];
                    if(!f[a[i][j - m]]){
                        if(s[a[i][j - m]] != g[i][id[i][j - m]])
                          --sum;    
                    }
                }
                dp[i][j] = (sum >= 1);
                if(!f[a[i][j]]){
                    if(s[a[i][j]] != g[i][id[i][j]])
                      ++sum;
                }
                ++f[a[i][j]];
            }
            for(int j = 0; j < len[i]; ++j)
              f[a[i][j]] = 0;
        }
        for(int i = 0; i < N; ++i)
          s[i] = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j < len[i]; ++j)
              g[i][j] = 0;
            for(int j = 0; j < len[i]; ++j){
                if(dp[i][j]){
                    F[k][a[i][j]] = 1;
                    ++s[a[i][j]];
                    ++g[i][id[i][j]];
                }
            }
        }
    }
    while(q--){
        r = read(), c = read();
        if(F[r][c])
          puts("1");
        else
          puts("0");
    }
}
int main(){
//  fin("chain.in"), fout("chain.out");
    T = read();
    while(T--)
      solve();
    return 0;
}