2024.2.15 集训记录

__vector__ · 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。