首页 > 其他分享 >题解 QOJ5034【>.<】/ BC2401D【可爱路径】

题解 QOJ5034【>.<】/ BC2401D【可爱路径】

时间:2024-09-25 19:45:55浏览次数:6  
标签:rt ch int 题解 BC2401D seg QOJ5034 id dis

必可赛前公益众筹赛 第一试 D

https://qoj.ac/problem/5034, 2022-2023 集训队互测 Round 6 (Nov 12, 2022)

题目描述

这原本是一道简单的最短路问题,但是由于种种地域文化,宗教信仰以及政治因素,原来一些或许可以行走的路径不能通行了。我们定义禁止路径为连续的经过一些特定的点的路径。一条可爱路径指从 \(1\) 到 \(n\) 的不经过任何禁止路径的路径。给定了一张 \(n\) 个点 \(m\) 条边的有向带权图和 \(k\) 条禁止路径,现在小 Z 想让你求出最短的可爱路径,若不存在输出 \(−1\)。为什么叫做可爱路径呢,因为这道题原来很可爱。\(n, m, k, \sum p\leq 2\times 10^5\)(\(\sum p\) 是禁止路径的长度和)。

solution

因为这个禁止路径的限制像一个匹配,我们直接建 AC 自动机。字符集太大,直接上可持久化线段树计算 Fail 指针以及维护 Trie 图,只需要观察正常 AC 自动机的建法,将其扩展一下即可。现在可以在 AC 自动机上跑 Dijkstra 算法,每次枚举这个状态对应图上的点的出边进行转移(根节点除外,但可以将根节点的 \(n\) 个儿子全部建出来以避免分讨)。因为一个图上的点的出边很可能被枚举多次,所以复杂度 \(O(nm\log m)\)。

为了优化这个算法,观察到有一些边是被重复枚举的。因为 Dijkstra 的性质,每个点取出时的 \(dis\) 不降,所以每条边只有第一次松弛是有效的,只要每条边不被重复枚举我们就赢了。又观察到这些边可以认为是存在可持久化线段树上的,对于每一个状态,其 Trie 图上的儿子,如果有对应图上的边,就可以松弛。而 Trie 图是存在于可持久化线段树中的,每个儿子是可持久化线段树中的一片叶子,而全局叶子的数量不超过 \(O(n+\sum p)\)。我们在可持久化线段树上 dfs,保证每一个线段树节点被访问不超过一次即可。注意对于根节点的 \(n\) 个儿子需要特判,因为根节点对应图上节点不固定,这时候需要另外写东西。维护 \(n\) 个 set,第 \(i\) 个 set 维护图上 \(i\) 节点的出边。每次如果 dfs 到根节点的 \(n\) 个儿子建出的线段树,则将当前状态所在节点的 set 拿出来,暴力找出 set 中在 \([l, r]\) 区间内的出边,转移并删除之。复杂度 \(O(n\log n)\)(认为 \(n, m, \sum p\) 同阶)。

code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
using pqueue = priority_queue<T, vector<T>, greater<T>>;
namespace seg {/*{{{*/
  constexpr int N = 200010 << 5;
  int ch[N][2], val[N], tot, tot0;
  int mdf(int x, int v, int q, int l, int r) {
    int p = ++tot;
    ch[p][0] = ch[q][0], ch[p][1] = ch[q][1], val[p] = val[q];
    if (l == r) return val[p] = v, p;
    int mid = (l + r) >> 1;
    if (x <= mid) ch[p][0] = mdf(x, v, ch[q][0], l, mid);
    else ch[p][1] = mdf(x, v, ch[q][1], mid + 1, r);
    return p;
  }
  int qry(int x, int p, int l, int r) {
    if (!p) return 0;
    if (l == r) return val[p];
    int mid = (l + r) >> 1;
    if (x <= mid) return qry(x, ch[p][0], l, mid);
    else return qry(x, ch[p][1], mid + 1, r);
  }
};/*}}}*/
int n, m, k, tot, rt[400010], fail[400010], upc[400010];
bool ban[400010], vis[400010];
LL dis[400010];
map<int, int> ch[400010], g[200010], g0[200010];
void build() {/*{{{*/
  queue<int> q;
  fail[0] = 0;
  for (auto&& e : ch[0]) {
    int v = e.second, r = e.first;
    rt[0] = seg::mdf(r, v, rt[0], 1, n);
    fail[v] = 0;
    q.push(v);
  }
  seg::tot0 = seg::tot;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    ban[u] |= ban[fail[u]];
    rt[u] = rt[fail[u]];
    for (auto&& e : ch[u]) {
      int v = e.second, r = e.first;
      rt[u] = seg::mdf(r, v, rt[u], 1, n);
      fail[v] = seg::qry(r, rt[fail[u]], 1, n);
      q.push(v);
    }
  }
}/*}}}*/
pqueue<pair<LL, int>> q;
void solve(int u, LL pred, int p, int l, int r) {
  using seg::val;
  if (!p || val[p] == -1) return ;
  if (p <= seg::tot0) {
    auto it = g0[u].lower_bound(l);
    while (it != g0[u].end() && it->first <= r) {
      if (pred + it->second < dis[it->first])
        q.emplace(dis[it->first] = pred + it->second, it->first);
      it = g0[u].erase(it);
    }
    return ;
  }
  if (l == r) {
    assert(val[p] > 0);
    if (g[u].count(l) && pred + g[u][l] < dis[val[p]])
      q.emplace(dis[val[p]] = pred + g[u][l], val[p]);
    val[p] = -1;
    return ;
  }
  int mid = (l + r) >> 1;
  solve(u, pred, seg::ch[p][0], l, mid);
  solve(u, pred, seg::ch[p][1], mid + 1, r);
  val[p] = -1;
}
LL dijkstra() {
  memset(vis, false, sizeof vis);
  memset(dis, 0x3f, sizeof dis);
  q.emplace(dis[ch[0][1]] = 0, ch[0][1]);
  while (!q.empty()) {
    int id = q.top().second; q.pop();
    if (vis[id] || ban[id]) continue;
    vis[id] = true;
    debug("dis[%d] = %lld\n", id, dis[id]);
    solve(upc[id], dis[id], rt[id], 1, n);
  }
  LL ans = 1e18;
  for (int i = 1; i <= tot; i++) if (!ban[i] && upc[i] == n) ans = min(ans, dis[i]);
  return ans >= 1e18 ? -1ll : ans;
}
int main() {
#ifndef LOCAL
#ifndef NF
  freopen("path.in", "r", stdin);
  freopen("path.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) ch[0][i] = ++tot, upc[tot] = i;
  for (int i = 1, u, v, w; i <= m; i++) cin >> u >> v >> w, g[u][v] = w;
  for (int i = 1; i <= n; i++) g0[i] = g[i];
  while (k--) {
    int len, p = 0, r;
    cin >> len;
    while (len--) {
      cin >> r;
      if (!ch[p].count(r)) ch[p][r] = ++tot, upc[tot] = r;
      p = ch[p][r];
    }
    ban[p] = true;
  }
  build();
  for (int i = 1; i <= tot; i++) debug("fail[%d] = %d\n", i, fail[i]);
  for (int i = 1; i <= tot; i++) debug("upc[%d] = %d\n", i, upc[i]);
  cout << dijkstra() << endl;
  return 0;
}

标签:rt,ch,int,题解,BC2401D,seg,QOJ5034,id,dis
From: https://www.cnblogs.com/caijianhong/p/18432050/solution-QOJ5034

相关文章

  • Luogu_P10977(AcWing_299) Cut the Sequence 题解
    解题思路考虑线性dp。首先如果存在\(a_i>m\),那肯定不满足条件,输出\(-1\)。设\(f_i\)表示前\(i\)个数分成若干段,然后每段最大数之和,其中每段内的整数之和不超过\(m\)。\(f_i\)肯定是由\(f_j\)(\(1\lej<i\))转移过来的,也就是前\(j\)个数分好后再加上\((j,i]\)这一......
  • 【OJ题解-1】稀疏矩阵乘法
    一、试题题面计算两个稀疏矩阵相乘,输出相乘的结果【输入输出约定】输入:第一行输入三个正整数p、q、r,表示p×q和q×r的两个矩阵相乘;(约定0<p,q,r≤1000)然后是第一个矩阵的输入,首先是一个整数m,表示矩阵一有m个非零元素;然后是m行,每行三个整数i,j,d,表示第i行,第j列的元素为d(约定......
  • P8906 [USACO22DEC] Breakdown P 题解
    P8906[USACO22DEC]BreakdownP题解显然的套路是删边转化为加边。考虑到维护整条路径不好维护,于是考虑转化维护\(f_{i,k},g_{i,k}\)分别表示\(1,n\)到\(i\)走了\(k\)步时的最短路。那么此时\(k\le4\)。我们先考虑\(f\)的转移,\(g\)的转移是等价的。那么对于\((......
  • 题解:CF573D Bear and Cavalry
    因为这是远古题目,所以根据现在的评测机速度,用\(O(nq)\)的做法也是可以过的。也就是说,我们可以每次操作直接修改对应位置上的数字,然后设计一种\(O(n)\)的算法求解答案。这道题类似资源分配型动态规划,所以我们可以设\(dp_i\)表示分配前\(i\)个人的答案。直接写是不行的,我......
  • 题解:AT_abc204_e [ABC204E] Rush Hour 2
    变形的dijkstra。先思考什么情况下需要等待以及等待多长时间最优。我们把题目上的计算方法按照当前的时间\(t\)和通过所需的时间\(f(t)\)列个函数关系:\[f(t)=t+c+\lfloor\frac{d}{t+1}\rfloor\]然后用Desmos画个图可以得到图像(其实就是对勾函数):因为\(c,d\geq0\),所......
  • [湖北省选模拟 2023] 棋圣 / alphago 题解
    很牛的题目啊。-Alex_Wei发现这个操作比较复杂但限制较弱,考虑通过考察“不变的量”来刻画操作。容易发现若为二分图,则初始颜色不同的一定不能移动到一起。又因为在存在环的图上这个限制很弱/目前较难考虑,所以先考虑树的情况,发现答案存在可能取到的上界,令\(c_{i,j}\)为初......
  • CF1119H Triple 题解
    DescriptionSK酱送给你了一份生日礼物。礼物是\(n\)个三元组\((a_i,b_i,c_i)\)和四个正整数\(x,y,z,k\)。你利用这\(n\)个三元组填充了\(n\)个数组,其中第\(i\)个数组中有\(x\)个\(a_i\),\(y\)个\(b_i\),\(z\)个\(c_i\)(所以第\(i\)个数组长度为\((x+y+z)\)。......
  • Codeforces Round 974 (Div. 3)题解记录
    A.RobinHelps签到模拟,遍历一遍即可,注意没钱时不给钱。\(O(n)\)#include<iostream>#include<set>#include<map>#include<vector>#include<algorithm>#include<bitset>#include<math.h>#include<string>#include<string.h>#......
  • [ARC122E] Increasing LCMs 题解
    感觉像比较套路的构造题。思路假如我们正着进行构造,可以发现我们加入一个数以后,对后面的数产生的影响是很大的。但是如果我们从最后一个数开始构造,那么可以发现它是不会对之后的构造产生任何影响的。应为越前面的数的限制会越少,那么可以填的数一定是不减的。一个数可以填在后......
  • 算法题之图论 [NOIP2001 提高组] Car的旅行路线详细题解
    P1027[NOIP2001提高组]Car的旅行路线这道题的思路呢,就是建个图,然后跑一遍Floyd,比较最小值就可以解决了。but!它每个城市只给三个点(共四个),所以还得计算出第四个点坐标。这里根据矩形的中点公式来表示未知点的坐标:(这个思路源于大佬 _jimmywang_       ......