简答题 偏难
#22131

T4 接龙

T4 接龙

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int N = 1e5 + 5, R = 105; vector&lt;int&gt; s[N]; int n, k, q; vector&lt;vector&lt;int&gt; &gt; Solve(int mx) {     vector&lt;vector&lt;int&gt; &gt; dp(R, vector&lt;int&gt;(mx + 5, -1));     dp[0][1] = -2;     for (int r = 1; r &lt;= 100; r++) {         for (int i = 1; i &lt;= n; i++) {             int lst = -1;             for (int j = 0; j &lt; s[i].size(); j++) {                 int tmp = s[i][j];                 if (lst != -1 &amp;&amp; j - lst + 1 &lt;= k) {                     if (dp[r][tmp] == -1)                         dp[r][tmp] = i;                     else if (dp[r][tmp] != i)                         dp[r][tmp] = -2;                 }                 if (dp[r - 1][tmp] != -1 &amp;&amp; dp[r - 1][tmp] != i)                     lst = j;             }         }     }     return dp; } int main() {     int t;     cin &gt;&gt; t;     while (t--) {         int mx = -1;         cin &gt;&gt; n &gt;&gt; k &gt;&gt; q;         for (int i = 1; i &lt;= n; i++) {             int l;             cin &gt;&gt; l;             s[i].clear();             s[i].resize(l);             for (int j = 0; j &lt; l; j++) {                 cin &gt;&gt; s[i][j];                 mx = max(mx, s[i][j]);             }         }                  vector&lt;vector&lt;int&gt; &gt; dp = Solve(mx);         while (q--) {             int r, c;             cin &gt;&gt; r &gt;&gt; c;             cout &lt;&lt; (dp[r][c] != -1 ? 1 : 0) &lt;&lt; endl;         }     }     return 0; }</pre>
解析

解题思路

本文的解题思想为dp。

dp[r][x]:接龙 r 轮、以 x 结尾的状态:

dp[r][x] = -1:不可实现。

dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。

dp[r][x] = -2:可以通过多个词库实现。

代码解析

完整的求解部分:

vector<vector<int> > Solve(int mx) {
    vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
    dp[0][1] = -2;
    for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
                int tmp = s[i][j];
                if (lst != -1 && j - lst + 1 <= k) {
                    if (dp[r][tmp] == -1)
                        dp[r][tmp] = i;
                    else if (dp[r][tmp] != i)
                        dp[r][tmp] = -2;
                }

                if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
                    lst = j;
            }
        }
    }
    return dp;
}

逐行分析

mx:所有词库中的最大值,用于构建dp的第二个维度。

dp的大小为R(最大轮数) * mx(所有词库中的最大值)。

vector<vector<int> > Solve(int mx) {
	vector<vector<int> > dp(R, vector<int>(mx + 5, -1));

dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。

dp[0][1] = -2;

r:轮数。

i:尝试让第 i 个人接龙。

j:第 i 个人词库中第 j 个词语。

lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。

for (int r = 1; r <= 100; r++) {
        for (int i = 1; i <= n; i++) {
            int lst = -1;
            for (int j = 0; j < s[i].size(); j++) {
            }
        }
    }

获取当前人员 i 的词库中第 j 个词语。

如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:

那么选择子序列[lst, j]开始接龙。

更新当前状态。

如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。

int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
    if (dp[r][tmp] == -1)
        dp[r][tmp] = i; // 首次发现路径则记录序列i
    else if (dp[r][tmp] != i)
        dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}

if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
    lst = j;