T3 涂鸦带师 题解
T3 涂鸦带师 题解
T3 涂鸦带师 题解#
倍增很重要，经常想不到
题意#
- 圆上周长为 \(C\)，第 \(i\) 张纸必须从 \(X_i\) 开始覆盖长度 \(L_i\)，即覆盖圆上的弧 \([X_i,\ X_i+L_i] \pmod C\)。
- 求最少用几张纸覆盖整个圆。
- 若某张纸满足 \(L_i \ge C\)，一张就能覆盖整个圆，答案直接是 \(1\)。
贪心思路#
- 断环成链：枚举第一张纸作为起点，把圆从 \(X_i\) 处切开拉直成 \([X_i,\ X_i+C]\)。
- 每张纸在数轴上出现两次：\([X_i,\ X_i+L_i]\) 和 \([X_i+C,\ X_i+C+L_i]\)，排序后转化为普通线段覆盖。
- 贪心策略：当前已覆盖到 \(cur\)，下一步从所有左端点 \(\le cur\) 的区间中，选择右端点最远的那个。
- 正确性：调整法: 设最优解第一步选区间 \(A\)，右端点为 \(r_A\)；贪心选区间 \(B\)，右端点为 \(r_B \ge r_A\)。贪心之后能接上的区间集合包含最优解之后的集合，因此把最优解第一步替换成贪心选择不会变差，归纳即证贪心最优。
- 暴力瓶颈：枚举 \(n\) 个起点，每个起点内层从头扫描 \(2n\) 个区间，复杂度 \(O(n^2)\)，问题在于每个起点都重复扫描。
倍增优化#
-
固定第一张纸后，贪心过程就是沿一个确定的函数 \(nxt\) 跳。从区间 \(i\) 出发贪心跳一步到哪，与起点无关，可以预处理好供所有起点复用。
-
令\(pre[i] = [1, i]\) 中右端点最大的区间编号,\(nxt[i] =\)从区间 \(i\) 贪心跳一步到达的区间
-
在所有满足 \(l_j \le r_i\) 的区间中，选择右端点 \(r_j\) 最大的区间。区间已按左端点排序，二分找到最后一个满足 \(l_p \le r_i\) 的位置 \(p\)，再用前缀最大 \(pre[p]\) 直接得到右端点最远的区间编号。若最远右端点都不超过 \(r_i\)，说明卡住，令 \(nxt[i]=i\)。
-
构造倍增表：\(up[i][k]\) 表示从区间 \(i\) 出发贪心跳 \(2^k\) 步后到达的区间。递推为 \(up[i][k]=up[up[i][k-1]][k-1]\)，从而把跳很多步压缩到 \(O(\log n)\)。
-
退出倍增循环时，\(cur\) 一定还没到达目标，因此需要再补一步 \(nxt[cur]\)。补完后若 \(sr \ge target\)，说明该起点有解。
复杂度#
- \(O(n\log n)\)。
AC code#
#include <bits/stdc++.h>
using namespace std;using ll = long long;
using pll = pair<ll, ll>;
const int N = 2e5 + 5;
const int LOG = 20;
const ll INF = 1e18;
ll C, n, m;
ll x[N], l[N], y[N];
ll sl[N * 2], sr[N * 2];
ll pre[N * 2], nxt[N * 2];
ll up[N * 2][LOG];
int main () {
freopen("paper.in", "r", stdin);
freopen("paper.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(class="hljs-number">0);
cin >> C >> n;
for (int i = class="hljs-number">1; i <= n; i ++) cin >> x[i] >> l[i], y[i] = x[i] + l[i];
for (int i = class="hljs-number">1; i <= n; i ++) {
if (l[i] >= C) {
cout << class="hljs-number">1 << class="hljs-string">'\n';
return class="hljs-number">0;
}
}
vector<pll> seg;
for (int i = class="hljs-number">1; i <= n; i ++) {
seg.push_back({ x[i], y[i] });
seg.push_back({ x[i] + C, y[i] + C });
}
sort(seg.begin(), seg.end());
m = class="hljs-number">2 * n;
for (int i = class="hljs-number">1; i <= m; i ++) {
sl[i] = seg[i - class="hljs-number">1].first;
sr[i] = seg[i - class="hljs-number">1].second;
}
for (int i = class="hljs-number">1; i <= m; i ++) {
if (i == class="hljs-number">1 || sr[i] > sr[pre[i - class="hljs-number">1]]) pre[i] = i;
else pre[i] = pre[i - class="hljs-number">1];
}
for (int i = class="hljs-number">1; i <= m; i ++) {
int l = class="hljs-number">1, r = m, p = class="hljs-number">0;
while (l <= r) {
int mid = (l + r) / class="hljs-number">2;
if (sl[mid] <= sr[i]) {
p = mid;
l = mid + class="hljs-number">1;
}
else r = mid - class="hljs-number">1;
}
int j = pre[p];
if (sr[j] <= sr[i]) nxt[i] = i;
else nxt[i] = j;
}
for (int i = class="hljs-number">1; i <= m; i ++) up[i][class="hljs-number">0] = nxt[i];
for (int k = class="hljs-number">1; k < LOG; k ++) {
for (int i = class="hljs-number">1; i <= m; i ++) {
up[i][k] = up[up[i][k - class="hljs-number">1]][k - class="hljs-number">1];
}
}
ll ans = INF;
for (int i = class="hljs-number">1; i <= n; i ++) {
int st = lower_bound(seg.begin(), seg.end(), make_pair(x[i], y[i])) - seg.begin() + class="hljs-number">1;
ll ed = x[i] + C;
int cur = st;
ll cnt = class="hljs-number">1;
bool flag = true;
for (int k = LOG - class="hljs-number">1; k >= class="hljs-number">0; k --) {
int nx = up[cur][k];
if (nx != cur && sr[nx] < ed) {
cur = nx;
cnt += (class="hljs-number">1 << k);
}
}
int nx = nxt[cur];
if (nx != cur) {
cur = nx;
cnt ++;
}
if (sr[cur] < ed) flag = false;
if (flag) ans = min(ans, cnt);
}
if (ans == INF) cout << class="hljs-string">"-class="hljs-number">1\n";
else cout << ans << class="hljs-string">'\n';
return class="hljs-number">0;
}
评论