luogu P2371 [国家集训队] 墨墨的等式
思路
同余最短路
同余最短路
同余最短路与差分约束有异曲同工之妙,都将约束条件转化为边,每种状态转化为点。把本来与图论毫不相干的问题抽象到具体的图上,通过拓扑排序,最短路等基础算法获得最小状态,从而解决问题。
在本题中,以 \(0\) 到 \(a_1 - 1\) 为节点,对于节点 \(v\) ,遍历 \(a\) ,将 \(v\) 和 \((v + a_j) \bmod a_1\) 连权值为 \(a_j\) 的边。
把图建完之后,就形成了一个有向图,跑最短路后 \(dis_v\) 的值即为用题目给出的数能获得的最小的,对 \(a_1\) 取模为 \(v\) 的值。
\(\forall v\) ,\(1\) 到 \(n\) 中有 \(\dfrac{n - dis_v}{a_1} + 1\) 数是可以用题目给出的数到达,所以答案为 \(\sum_i^{a_1 - 1} \dfrac{r - dis_v}{a_1} - \dfrac{l - 1 - dis_v}{a_1}\)
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
typedef long long LL;
using namespace std;
const int N = 15, M = 5e5 + 5;
const LL inf = 1e18;
#define pb push_back
#define pi pair<LL, LL>
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
priority_queue< pi, vector< pi >, greater< pi >> que;
vector< pi > g[M];
LL n, Min = 1e9;
LL l, r, dis[M], ans;
bool vis[M];
LL a[N];
void dijkstra() {
dis[0] = 0;
que.push({0, 0});
while (que.size()) {
int u = que.top().second;
que.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto to : g[u]) {
int v = to.first, w = to.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
que.push({dis[v], v});
}
}
}
}
int main() {
scanf("%lld%lld%lld", &n, &l, &r);
LF(i, 1, n) {
scanf("%lld", &a[i]);
Min = min(Min, a[i]);
}
if (Min == 1) {
printf("%lld\n", r - l + 1);
return 0;
}
LF(i, 0, a[1] - 1) {
LF(j, 1, n) g[i].pb({(i + a[j]) % a[1], a[j]});
dis[i] = inf;
}
dijkstra();
LF(i, 0, a[1] - 1) if (r >= dis[i]) ans += (r - dis[i]) / a[1] + 1;
LF(i, 0, a[1] - 1) if (l - 1 >= dis[i]) ans -= (l - 1 - dis[i]) / a[1] + 1;
printf("%lld", ans);
return 0;
}
标签:LF,int,题解,LL,P2371,que,luogu,pi,dis From: https://www.cnblogs.com/faruzan/p/18331104Und verloren sei uns der Tag, wo nicht ein Mal getanzt wurde!
每个不曾起舞的日子,都是对生命的一种辜负。
——《查拉图斯特拉如是说》