思路
首先简单分析一下问题
首先我们要为每只兔子选择一个 \(st_i \in [bas_i + L, bas_i + R]\) 表示其起始位置
然后我们要找到最小的 \(t\), 使得 \(\Big({\times d} + [L, R]\Big)^t\) 之后能到达一个 \(\bmod \, n = 0\) 的数
首先 \(R - L + 1 \leq n - 1\) 且初始区间不满足要求, 否则直接输出 \(0\)
这个时候我们不难发现 \([bas_i + L, bas_i + R]\) 在 \(\bmod \, n\) 意义下是一个区间
因此判断答案是否为 \(0\) 之后, 我们只需要处理一个区间中的最小答案即可
记 \(ans_x\) 表示 \(x\) 通过多少次 \(\Big({\times d} + [L, R]\Big)\) 之后能到达一个 \(\bmod \, n = 0\) 的数
每次就是对 \(ans\) 的一个 \(\text{RMQ}\) 问题
下面都在 \(\bmod \, n\) 意义下讨论
简单的情况下, 我们可以直接连边 \(\Big({x \times d} + [L, R]\Big) \to x\), 对于 \(x \bmod n = 0\), \(dis_x = 0\), 然后跑一个最短路即可
但是这个时候我们发现, 我们的边数是 \(O(n^2)\) 的, 会 TLE
因此我们需要优化一下边数
不难发现每次连边可以表示为向至多两个区间连边, 因此使用线段树优化建图即可
综合复杂度 \(\mathcal{O} \bigg\{T \Big(n \log n + q\Big) \bigg\}\)
代码
#include <bits/stdc++.h>
#define int long long
// const int MAXN = 2e6 + 50000;
const int MAXN = 300;
const int INF = 1e18;class SOLVER {
private:int n, d, LC, RC, q;struct EDGE { int to, w, nxt; } edge[MAXN << 2];int head[MAXN], ecnt = -1;void addedge(int u, int v, int w) { edge[++ecnt] = {v, w, head[u]}, head[u] = ecnt; }int ans[MAXN];int ST[MAXN << 2][22];bool check(int x) { return ((x + LC) % n == 0 || (x + LC) % n > (x + RC) % n); }int ncnt;int lc[MAXN << 2], rc[MAXN << 2];void build(int &o, int l, int r) {if (l == r) { o = l; return; }o = ++ncnt;int mid = (l + r) >> 1;build(lc[o], l, mid);build(rc[o], mid + 1, r);addedge(lc[o], o, 0); addedge(rc[o], o, 0);}void connect(int o, int l, int r, int L, int R, int from) {if (l >= L && r <= R) { addedge(o, from, 1); return; }int mid = (l + r) >> 1;if (L <= mid) connect(lc[o], l, mid, L, R, from);if (R > mid) connect(rc[o], mid + 1, r, L, R, from);}int vis[MAXN << 2];public:void solve() {ecnt = -1;memset(lc, 0, sizeof lc), memset(rc, 0, sizeof rc);memset(head, -1, sizeof head); memset(vis, false, sizeof vis);scanf("%lld %lld %lld %lld %lld", &n, &d, &LC, &RC, &q); ncnt = n - 1;if (RC - LC + 1 >= n) {for (int i = 1; i <= q; i++) printf("0\n");return;}/*处理建图*/int root; build(root, 0, n - 1);for (int i = 0; i < n; i++) {/*处理 [id + L % n, id + R % n]*/int id = (i * d) % n;// printf("%lld %lld %lld\n", (id + LC) % n, (id + RC) % n, i);if ((id + LC) % n <= (id + RC) % n) {int l = (id + LC) % n, r = (id + RC) % n;connect(root, 0, n - 1, l, r, i);} else {int l1 = (id + LC) % n, r1 = n - 1;int l2 = 0, r2 = (id + RC) % n;connect(root, 0, n - 1, l1, r1, i);connect(root, 0, n - 1, l2, r2, i);}}// printf("----------------------------------------------------------------------");// for (int u = 0; u <= ncnt; u++) {// for (int e = head[u]; ~e; e = edge[e].nxt) {// int v = edge[e].to, w = edge[e].w;// printf("%lld %lld %lld\n", u, v, w);// }// }/*从 0 开始跑最短路*/std::deque<int> dq;dq.push_back(0);for (int i = 0; i <= ncnt; i++) ans[i] = INF;ans[0] = 0;while (!dq.empty()) {int u = dq.front(); dq.pop_front();if (vis[u]) continue;vis[u] = true;for (int e = head[u]; ~e; e = edge[e].nxt) {int v = edge[e].to, w = edge[e].w;if (ans[v] > ans[u] + w) {ans[v] = ans[u] + w;if (w == 0) dq.push_front(v);else dq.push_back(v);}}}/*建立 ST 表*/for (int i = 0; i < n; i++) ST[i][0] = ans[i];for (int j = 1; j <= 20; j++) {for (int i = 0; i + (1 << j) - 1 < n; i++) ST[i][j] = std::min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);}for (int i = 1, bas; i <= q; i++) {scanf("%lld", &bas);bas %= n;if (check(bas)) { printf("0\n"); continue; }/*求 [bas + LC, bas + RC] 中的最小答案*/int l = (bas + LC) % n, r = (bas + RC) % n;int res = INF;if (l <= r) {int k = std::log2(r - l + 1);res = std::min(res, std::min(ST[l][k], ST[r - (1 << k) + 1][k]));} else {/*先处理 l, n - 1*/int k = std::log2(n - l);res = std::min(res, std::min(ST[l][k], ST[n - (1 << k) + 1][k]));/*再处理 0, r*/k = std::log2(r + 1);res = std::min(res, std::min(ST[0][k], ST[r - (1 << k) + 1][k]));}if (res == INF) printf("-1\n");else printf("%lld\n", res);}}
} MAIN;signed main() {// freopen("ex_calculator2.in", "r", stdin);// freopen("ex_calculator2.out", "w", stdout);int _; scanf("%lld", &_);while (_--) MAIN.solve();return 0;
}
总结
非常简单的一种优化建图方式
我草我草