A. Room Temperature
题目描述
有 \(N\) 个人，每个人都有一个适宜温度 \(A_i\)。现在有无限件外套，一个人每穿一件外套适宜温度就会减 \(T\)。
如果当前室温为 \(x\)，则一个人不适程度为 \(|x-A_i|\)。求所有人的不适程度最大值的最小值。
思路
首先我们可以令 \(A_i \leftarrow A_i \bmod T\)。（可以通过穿很多件外套得到）此时不适程度为 \(\lceil\frac{\max-\min}{2}\rceil\)。但这不一定是最优解，我们还可以通过脱外套来减少不适程度。所以可以用一种类似于断环成链的方法来求解
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int n, t, a[MAXN], ans;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> t;
ans = t;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] %= t;
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i) {
a[i + n] = a[i] + t;
ans = min(0ll + ans, (0ll + a[i + n - 1] - a[i] + 1) / 2);
}
cout << ans;
return 0;
}
/*
6 8
24 22 21 25 29 17
*/
B. Construction Project 2
题目描述
给定一个 \(N\) 个点，\(M\) 条边的无向带权图，你可以选择两个数 \(u,v\) 使得 \(1\le u < v \le N\)，并在 \(u\) 和 \(v\) 之间建一条边权为 \(L\) 的边。问有多少种建边的方法使得 \(S\) 到 \(T\) 的最短路 \(\le K\)。
思路
首先从 \(S\) 和 \(T\) 跑一遍最短路。如果此时的最短路就已经 \(\le K\) 了，那么直接输出 \(\frac{N(N-1)}{2}\)。
否则，很明显要满足 \(dist_{S,u}+L+dist_{v,T}\le K\)，所以就对从 \(S,T\) 出发的最短路排个序，然后做双指针就行了。
但是为什么这样不会把 \((u,v)\) 和 \((v,u)\) 都算一遍呢？可以发现这里我们的判断是把建的这条边看做一条有向边的（因为我们只判断一个方向）。
假设两个方向都是满足条件的，即
\[\begin{array}{l} dist_{S,u}+L+dist_{v,T}\le K\\ dist_{S,v}+L+dist_{u,T}\le K \end{array} \]此时一定修改了另一端的最短路，否则这条路径不可能 \(\le K\)，即
\[dist_{S,u}+L<dist_{S,v}\\ dist_{S,v}+L<dist_{S,u} \]又因为 \(dist_{S,u}+L<dist_{S,v}\)，所以 \(dist_{S,u}+L+L+dist_{u,T}\le K\)。而这里 \(dist_{S,u}+dist_{u,T}\) 就是一条从 \(S\) 到 \(T\) 的 \(\le K\) 的路径了，而这种情况我们在一开始就已经处理过了，所以不会有重复。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 200001;
const ll INF = (ll)(1e18);
struct Node {
int u;
ll dis;
};
struct cmp {
bool operator()(const Node &a, const Node &b) const {
return a.dis > b.dis;
}
};
int n, m, s, t, l;
ll dist[2][MAXN], ans, k;
bool vis[2][MAXN];
vector<pii> e[MAXN];
void dij(int S, bool op) {
priority_queue<Node, vector<Node>, cmp> pq;
for(int i = 1; i <= n; ++i) {
dist[op][i] = INF;
vis[op][i] = 0;
}
dist[op][S] = 0;
pq.push({S, 0});
for(; !pq.empty(); ) {
auto [u, dis] = pq.top();
pq.pop();
if(vis[op][u]) {
continue;
}
vis[op][u] = 1;
for(auto [v, w] : e[u]) {
if(dis + w < dist[op][v]) {
dist[op][v] = dis + w;
pq.push({v, dis + w});
}
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> s >> t >> l >> k;
for(int i = 1, u, v, w; i <= m; ++i) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
dij(s, 0);
dij(t, 1);
if(dist[0][t] <= k) {
cout << 1ll * n * (n - 1) / 2;
return 0;
}
sort(dist[0] + 1, dist[0] + n + 1);
sort(dist[1] + 1, dist[1] + n + 1);
for(int i = 1, j = n; i <= n; ++i) {
for(; j > 0 && dist[0][i] + dist[1][j] + l > k; --j) {
}
ans += j;
}
cout << ans;
return 0;
}
C. Marathon Race 2
题目描述
在一根数轴上有 \(N\) 个球，第 \(i\) 个球位于位置 \(X_i\)。你可以做以下操作：
- 在数轴上移动一个单位，花费 \(x+1\) 的时间。这里 \(x\) 是你手上球的数量
- 拿起一个球，花费 \(1\) 的时间。
有 \(Q\) 次询问，每次一开始你在位置 \(S\)，你要带着所有球去到位置 \(G\) ，问你能不能在 \(T\) 的时间内完成？
思路
由于拿球很难解决，所以我们把它倒过来，变成放球。而放球很明显每遇到一个放球的位置就一定会放下。
因此放完球的区域一定是一个区间。所以考虑区间 dp。
首先将 \(X\) 排序。
令 \(dp_{0/1,l,r}\) 表示现在已经把 \(X_l\) 到 \(X_r\) 放好，当前在 \(l/r\)，把剩下的球放好所需的最少时间。
很明显我们有：
\[dp_{0,l,r} = \min(dp_{0,l-1,r}+(X_l-X_{l-1})\cdot (n-r+l),dp_{1,l,r+1}+(X_{r+1}-X_l)\cdot(n-r+l))\\ dp_{1,l,r} = \min(dp_{0,l-1,r}+(X_r-X_{l-1})\cdot (n-r+l),dp_{1,l,r+1}+(X_{r+1}-X_r)\cdot(n-r+l)) \]但是我们还没有解决起点和终点的问题：
-
对于终点，我们可以枚举选择离 \(G\) 最近的两个点作为终点，并求出走到 \(G\) 的时间。
-
对于起点，我们可以在状态中加入一位 \(0/1\)，表示起点在 \(X_1/X_N\)。对于 \(dp_0/1\) 的 dp，其初始状态为 \(dp_{x,x,1,N}(x\in\{0,1\})\)。
但是此时时间复杂度不正确，要如何优化呢？
观察到题目的 \(T\) 只有 \(5\times 10^5\)，我们可以想到，如果不同 \(X_i\) 的数量为 \(x\) ，则至少需要 \(2+3+\dots+x+N\) 的时间，也就是只有 \(x\le O(\sqrt T)\approx 1000\) 时才有可能成功，因此我们可以把多个 \(X_i\) 相同的球压成一个做 dp，如果最终数量 \(>1005\) 就全部输出 NO。
空间复杂度 \(O(T+N)\)，时间复杂度 \(O(N\log N+T+Q)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXL = 500001, MAXN = 1010;
const ll INF = (ll)(1e18);
struct Node {
int x, cnt;
}s[MAXN];
int n, l, q, tot, mp[MAXL], sum[MAXN];
ll dp[2][2][MAXN][MAXN];
int Calc(int l, int r) {
return sum[r] - sum[l - 1];
}
int Binary_Search(int x) {
int l = 1, r = tot + 1;
for(; l < r; ) {
int mid = (l + r) >> 1;
(s[mid].x >= x ? r = mid : l = mid + 1);
}
return l;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> l;
for(int i = 1, x; i <= n; ++i) {
cin >> x;
mp[x]++;
}
cin >> q;
for(int i = 0; i <= l; ++i) {
if(mp[i]) {
s[++tot] = {i, mp[i]};
sum[tot] = sum[tot - 1] + mp[i];
if(tot == 1005) {
for(int j = 1; j <= q; ++j) {
cout << "No\n";
}
return 0;
}
}
}
for(bool op : {0, 1}) {
for(bool opt : {0, 1}) {
for(int l = 0; l <= tot + 1; ++l) {
for(int r = 0; r <= tot + 1; ++r) {
dp[op][opt][l][r] = INF;
}
}
}
dp[op][op][1][tot] = 0;
for(int len = tot - 1; len >= 1; --len) {
for(int l = 1, r = len; r <= tot; ++l, ++r) {
dp[op][0][l][r] = min(dp[op][0][l - 1][r] + 1ll * (n - Calc(l, r) + 1) * (s[l].x - s[l - 1].x),
dp[op][1][l][r + 1] + 1ll * (n - Calc(l, r) + 1) * (s[r + 1].x - s[l].x));
dp[op][1][l][r] = min(dp[op][1][l][r + 1] + 1ll * (n - Calc(l, r) + 1) * (s[r + 1].x - s[r].x),
dp[op][0][l - 1][r] + 1ll * (n - Calc(l, r) + 1) * (s[r].x - s[l - 1].x));
}
}
}
for(int i = 1, S, T, ti; i <= q; ++i) {
cin >> S >> T >> ti;
int x = Binary_Search(T);
ll ans = INF;
if(x <= tot) {
ans = min({ans, dp[0][0][x][x] + 1ll * (s[x].x - T) * (n + 1) + abs(S - s[1].x) + n,
dp[1][0][x][x] + 1ll * (s[x].x - T) * (n + 1) + abs(S - s[tot].x) + n});
}
if(x > 1) {
ans = min({ans, dp[0][0][x - 1][x - 1] + 1ll * (T - s[x - 1].x) * (n + 1) + abs(S - s[1].x) + n,
dp[1][0][x - 1][x - 1] + 1ll * (T - s[x - 1].x) * (n + 1) + abs(S - s[tot].x) + n});
}
cout << (ans <= ti ? "Yes\n" : "No\n");
}
return 0;
}
D. Gift Exchange
题目描述
有 \(N\) 个小朋友，第 \(i\) 个小朋友有一个价值为 \(A_i\) 的礼物，希望得到价值为 \(B_i(B_i<A_i)\) 的礼物。有 \(Q\) 次询问，每次询问一个区间 \([l,r]\) 是否存在一种交换礼物的方案。
这里一种交换礼物的方案是指一个排列 \(p_1,p_2,\dots,p_N\)，其中 \(p_i\ne i\) 且 \(A_{p_i}>B_i\)。
思路
首先，如果每个人都存在另一个人可以与其互换礼物，那么这就是一个可行的区间。
假设我们已经按照 \(A_i\) 排序了，那么此时对于 \(i<j\)，\(i\) 都能接受 \(j\) 的礼物。此时只要 \(j\) 能接受 \(i\) 的礼物，那么 \([i,j]\) 这个区间都能构成一个环，而既然 \(j\) 能接受 \(i\) 的礼物，那么一定也能接受 \(i+1,i+2,\dots,j-1\) 的礼物，也就是所有人都能跟 \(j\) 互换礼物，满足条件。
但这是 \(A_i\) 已经排序好的情况下，实际我们并不能这么做。
所以我们先想出一个大致的思路再一点一点实现：
-
对于每个 \(i\)，求出在左边离他最近的可以互换礼物的人 \(l_i\) 和右边的 \(r_i\)。
-
只要 \(\forall i\in [L,R]\) 都满足 \(l_i\ge L 或 r_i \le R\)，则该区间合法。
首先考虑第一个步骤：如何求出 \(l_i,r_i\)：
我们可以开一个 \(2N\) 大小的线段树，其中每个位置都存储着 \((A_i,i)\)。我们依次枚举每个 \(i\)，找到线段树中 \([1,A_i-1]\) 这段区间，找出里面所有 \(A_j > B_i\) 的 \(j\) 并让 \(r_j \leftarrow i\)，并从线段树中删掉 \(j\)。最后插入 \((A_i,i)\)。
我们在线段树中维护 \(A_i\) 的最大值，如果一个区间的最大值已经 \(\le B_i\)，那么停止递归。
这样每个 \(i\) 只会被发现并删除一次，总时间复杂度 \(O(N\log N)\)。
求 \(l_i\) 只需变成倒着枚举即可。
对于查询，我们可以离线做。首先把查询按 \(R\) 排序。
接着使用一个线段树，维护 \(l_i\) 的最小值。我们使用双指针的方法，依次枚举 \(i\le R\)，如果 \(i=r_j\)，那么位置 \(j\) 已经合法，无需管它的 \(l_j\)，所以把 \(lj\) 设为 \(\infty\)。
找到 \(i=r_j\) 的 \(j\) 可以用 vector 存储，而判断合法就是 \(\min \limits_{i=L}^{R} \{l_i\}\ge L\)。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N+Q\log Q)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int L[MAXN], R[MAXN];
struct Max_Segment_Tree {
int l[MAXN << 2], r[MAXN << 2], Max[MAXN << 2], id[MAXN << 2];
void build(int u, int s, int t) {
l[u] = s, r[u] = t, Max[u] = id[u] = 0;
if(s == t) {
return;
}
int mid = (s + t) >> 1;
build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
}
void update(int u, int p, int x, int _id) {
if(l[u] == r[u]) {
Max[u] = x, id[u] = _id;
return;
}
(p <= r[u << 1] ? update(u << 1, p, x, _id) : update((u << 1) | 1, p, x, _id));
Max[u] = max(Max[u << 1], Max[(u << 1) | 1]);
}
void GetLR(int u, int s, int t, int x, int _id, bool op) {
if(r[u] < s || l[u] > t || Max[u] <= x) {
return;
}
if(l[u] == r[u]) {
(op ? R[id[u]] = _id : L[id[u]] = _id);
Max[u] = id[u] = 0;
return;
}
GetLR(u << 1, s, t, x, _id, op), GetLR((u << 1) | 1, s, t, x, _id, op);
Max[u] = max(Max[u << 1], Max[(u << 1) | 1]);
}
}tr;
struct Min_Segment_Tree {
int l[MAXN << 2], r[MAXN << 2], Min[MAXN << 2];
void build(int u, int s, int t) {
l[u] = s, r[u] = t, Min[u] = int(1e9);
if(s == t) {
return;
}
int mid = (s + t) >> 1;
build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
}
void update(int u, int p, int x) {
if(l[u] == r[u]) {
Min[u] = x;
return;
}
(p <= r[u << 1] ? update(u << 1, p, x) : update((u << 1) | 1, p, x));
Min[u] = min(Min[u << 1], Min[(u << 1) | 1]);
}
int Getmin(int u, int s, int t) {
if(l[u] >= s && r[u] <= t) {
return Min[u];
}
int x = int(1e9);
if(s <= r[u << 1]) {
x = min(x, Getmin(u << 1, s, t));
}
if(t >= l[(u << 1) | 1]) {
x = min(x, Getmin((u << 1) | 1, s, t));
}
return x;
}
}TR;
struct Node {
int l, r, id;
}s[MAXN];
int n, q, a[MAXN], b[MAXN];
bool ans[MAXN];
vector<int> ve[MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 1; i <= n; ++i) {
cin >> b[i];
}
tr.build(1, 1, 2 * n);
for(int i = 1; i <= n; ++i) {
tr.GetLR(1, 1, a[i], b[i], i, 1);
tr.update(1, b[i], a[i], i);
}
tr.build(1, 1, 2 * n);
for(int i = n; i >= 1; --i) {
tr.GetLR(1, 1, a[i], b[i], i, 0);
tr.update(1, b[i], a[i], i);
}
cin >> q;
for(int i = 1; i <= q; ++i) {
cin >> s[i].l >> s[i].r;
s[i].id = i;
}
sort(s + 1, s + q + 1, [=](const Node &a, const Node &b) -> bool {
return a.r < b.r;
});
for(int i = 1; i <= n; ++i) {
if(R[i]) {
ve[R[i]].emplace_back(i);
}
}
TR.build(1, 1, n);
for(int i = 1, j = 1; i <= q; ++i) {
for(; j <= n && j <= s[i].r; ++j) {
TR.update(1, j, L[j]);
for(int x : ve[j]) {
TR.update(1, x, int(1e9));
}
}
ans[s[i].id] = (TR.Getmin(1, s[i].l, s[i].r) >= s[i].l);
}
for(int i = 1; i <= q; ++i) {
cout << (ans[i] ? "Yes\n" : "No\n");
}
return 0;
}