简答题 适中
#24857

消息查找

消息查找

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 1e5 + 5; const int C = 2e3 + 5; const int oo = 1e9; int n, q; int r[N], mark[N], pos[N]; int p[C], cnt; int d[C][C]; int pre[N], suf[N]; int main() {     scanf("%d%d", &amp;n, &amp;q);     for (int i = 1; i &lt;= n; i++)     {         scanf("%d", &amp;r[i]);         if (r[i])             mark[i] = mark[r[i]] = 1;     }     for (int i = 1; i &lt;= n; i++)     {         if (mark[i])         {             p[++cnt] = i;             pos[i] = cnt;         }     }     for (int i = 1; i &lt;= cnt; i++)     {         for (int j = 1; j &lt;= i; j++)             d[i][j] = oo;         d[i][i] = 0;         for (int j = i; j &gt; 1; j--)         {             d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]);             if (r[p[j]])             {                 int k = pos[r[p[j]]];                 d[i][k] = min(d[i][k], d[i][j] + 1);             }         }     }     for (int i = 1; i &lt;= n; i++)     {         pre[i] = pre[i - 1];         if (mark[i])             pre[i] = i;     }     suf[n + 1] = n + 1;     for (int i = n; i; i--)     {         suf[i] = suf[i + 1];         if (mark[i])             suf[i] = i;     }     while (q--)     {         int x, y;         scanf("%d%d", &amp;x, &amp;y);         if (pre[x] &lt; suf[y])         {             printf("%d\n", x - y);         }         else         {             printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y);         }     }     return 0; }</pre>
这道题暂未补解析。