本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 17:48:26

lxn 要求写笔记，所以就写笔记了。

学习了一些新的 tricks。

• P2371 [国家集训队] 墨墨的等式
  本质上和跳楼机相同。
  另外，可以通过差分忽略 $l$ 的限制。
  可以看成初始在 $0$，每次可以上升 $a_i$ 格，或者回到 $0$，问 $r$ 以下的格子有多少能到达。
  这里注意，如果一个层数 $x$ 可以被到达，那么 $x - k \cdot a_i$ 也可以被到达。
  也就是说，我们可以在模意义下执行操作！！！
  事实上选择任何一个 $a_i$ 进行取模都可以，但是为了更快的计算，这里选择 $\min_{1 \le i \le n}a_i$。
  然后没然后了。
• P5304 [GXOI/GZOI2019] 旅行者
  首先，如果是两个点集，求在两个集合各选一个点使得最短路长度最小，只需要建立一个超级源点，一个超级汇点，源点到汇点的最短路就是最小值。
  假设 $x,y$ 在原图中最短路最小，则试图把他们分成两个集合。
  想一想以什么为依据划分，使得他们一定包含在不同的集合中。
  注意到 $x,y$ 至少有一位二进制不同，所以可以依此枚举 $i$，编号第 $i$ 位为 $0$ 放入第一个集合，否则放入第二个集合，然后反过来跑一遍。
• Complete The Graph
  两种做法。
  首先，假设不确定的边全是最小值 $1$，共有 $c$ 个边不确定，然后依此将 第 $1,2,3,\cdots,c,1,2,3,\cdots,c,1,2,3,\cdots$ 加 $1$，这样每次最短路最多加 $1$。
  只需要二分就行。
  第二种，不确定的边按照最小值 $1$ 跑 dijkstra，记录 $dif = L-dis_t$，第二次 dijkstra 大概是以动态确定的方式，若 $dis_{to} + dif \gt dis_u + edge[i].val$，那么修改本边的权值使得 $dis_{to} + dif = dis_u + edge[i].val$，这样就能保证最终的最短路加上 $dif$。