[loj 2395]「JOISC 2017 Day 2」火车旅行

题目链接

https://loj.ac/problem/2395

题解

一道非常棒的题。

Subtask 2

我们考虑建立图论模型,套最短路算法来做。

对于每个点,分别考虑这个点左边和右边的所有点,向它能到达的左边/右边的第一个点分别连一条边。

为啥是第一个点呢?目的是为了减少重复的边(\(a \to b \to c\) 这条路径只用连 \(a \to b\) 和 \(b \to c\) 的边,不用连 \(a \to c\) 的边了)。

这样连边后的图最多有 \(O(N)\) 条边,在新图上跑最短路即可。

时间复杂度 \(O(QN \log N)\),期望得分:20 pts。

Subtask 4

我们接下来从区间的角度来考虑这道题。

我们之前已经求出,在花费为 \(1\) 时,从 \(i\) 号节点出发,最左可以到达 \(l_i\) 号节点,最右可以到达 \(r_i\) 号节点。

那么在花费为 \(k\) 的时候,从 \(i\) 号节点最左和最右可以到达的点怎么求呢?

容易发现这个可以倍增来算。

现在我们把这些区间展开成一棵树:如果区间 \(a\) 完全包含了区间 \(b\),且区间 \(a\) 代表了从 \(i\) 出发跳 \(k\) 次覆盖的区间,区间 \(b\) 代表了从 \(i\) 出发跳 \(k-1\) 次覆盖的区间,那么我们将 \(b\) 挂在 \(a\) 下面。

现在来转化问题:我们现在让 \([A,A]\) 和 \([B,B]\) 两个点向上跳,直到它们的父节点相同为止(也就是说这两个区间紧挨着,别忘了起点和终点不算入答案)。这时候我们跳的次数就是答案。

时间复杂度 \(O(Q \log N)\),期望得分:100 pts。

#include <iostream>
#include <stack>
using namespace std;
int l[100005],f[100005][25],g[100005][25];
stack<int> s;
int main()
{
 ios::sync_with_stdio(false);
 int n,k,q;
 cin>>n>>k>>q;
 for(int i=1;i<=n;i++)
  cin>>l[i];
 for(int i=1;i<=n;i++)
 {
  while(!s.empty()&&l[s.top()]<l[i])
   s.pop();
  if(!s.empty())f[i][0]=s.top();
  else f[i][0]=i;
  s.push(i);
 }
 while(!s.empty())
  s.pop();
 for(int i=n;i;i--)
 {
  while(!s.empty()&&l[s.top()]<l[i])
   s.pop();
  if(!s.empty())g[i][0]=s.top();
  else g[i][0]=i;
  s.push(i);
 }
 for(int k=1;k<=17;k++)
  for(int i=1;i<=n;i++)
  {
   f[i][k]=min(f[f[i][k-1]][k-1],f[g[i][k-1]][k-1]);
   g[i][k]=max(g[f[i][k-1]][k-1],g[g[i][k-1]][k-1]);
  }
 while(q--)
 {
  int a,b,l,r;
  cin>>a>>b;
  if(a>b)swap(a,b);
  int ans=0;
  l=r=a;
  for(int k=17;k>=0;k--)
  {
   int u=min(f[l][k],f[r][k]),v=max(g[l][k],g[r][k]);
   if(v<b)
   {
    l=u,r=v;
    ans+=(1<<k);
   }
  }
  a=r;
  l=r=b;
  for(int k=17;k>=0;k--)
  {
   int u=min(f[l][k],f[r][k]),v=max(g[l][k],g[r][k]);
   if(u>a)
   {
    l=u,r=v;
    ans+=(1<<k);
   }
  }
  cout<<ans<<endl;
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据