JOI Final 2020 题解
Visits: 589
長いだけのネクタイ (Just Long Neckties)
显然 $a,b$ 排序后对应位置上的数相减最优，multiset 维护一下即可，时间复杂度 $\mathcal O(n \log n)$。
const int N = 2e5 + 7;
int n, a[N], b[N], p[N], ans[N];
multiset<int> s;
int main() {
rd(n), rda(a, n + 1), rda(b, n);
for (int i = 1; i <= n + 1; i++) p[i] = i;
sort(p + 1, p + n + 2, [&](int i, int j) { return a[i] < a[j]; });
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) s.insert(max(a[p[i+1]] - b[i], 0));
ans[p[1]] = *--s.end();
for (int i = 1; i <= n; i++) {
s.erase(s.find(max(a[p[i+1]] - b[i], 0)));
s.insert(max(a[p[i]] - b[i], 0));
ans[p[i+1]] = *--s.end();
}
for (int i = 1; i <= n + 1; i++)
print(ans[i], " \n"[i==n+1]);
return 0;
}
JJOOII 2 (JJOOII 2)
前缀和一下，然后枚举开头 $s$，二分出从 $s$ 开始的第 $k$ 个 J 的位置 $x$，从 $x$ 开始的第 $k$ 个 O 的位置 $y$，从 $y$ 开始的第 $k$ 个 I 的位置 $z$，从而求得答案，时间复杂度 $\mathcal O(n \log n)$。
当然也可以用类似 Two Pointers 的思想做到线性。
const int N = 2e5 + 7, inf = 1e9;
int n, k, f[3][N], ans = inf;
char s[N];
int main() {
rd(n, k), rds(s, n);
map<char, int> p;
p['J'] = 0, p['O'] = 1, p['I'] = 2;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) f[j][i] = f[j][i-1];
++f[p[s[i]]][i];
}
for (int i = 0; i < n; i++) {
if (f[0][i] + k > f[0][n]) break;
int x = lower_bound(f[0] + 1, f[0] + n + 1, f[0][i] + k) - f[0];
if (f[1][x] + k > f[1][n]) break;
int y = lower_bound(f[1] + 1, f[1] + n + 1, f[1][x] + k) - f[1];
if (f[2][y] + k > f[2][n]) break;
int z = lower_bound(f[2] + 1, f[2] + n + 1, f[2][y] + k) - f[2];
ans = min(ans, z - i - 3 * k);
}
print(ans == inf ? -1 : ans);
return 0;
}
スタンプラリー 3 (Collecting Stamps 3)
断环成链，区间 DP。
设 $f_{l,r,0/1,i}$ 表示已经处理了 $l\sim r$ 种邮票，现在在 $l/r$ 的位置上，已经收集了 $i$ 种邮票的最小花费时间。
每次枚举走到 $l-1$ 还是走到 $r+1$，时间复杂度 $\mathcal O(n^3)$。
const int N = 207;
const ll inf = 1e18;
int n, m, p[N<<1|1], t[N<<1|1], ans;
ll f[N<<1|1][N<<1|1][2][N];
inline void upd(ll &x, ll y) {
x = min(x, y);
}
int main() {
rd(n, m), rda(p + n + 1, n), rda(t + n + 1, n);
for (int i = 1; i <= n; i++) p[i] = p[i+n+1] - m, t[i] = t[i+n+1];
for (int l = 1; l <= n + 1; l++)
for (int r = n + 1; r <= (n << 1 | 1); r++)
for (int k = 0; k < 2; k++)
for (int i = 0; i <= n; i++)
f[l][r][k][i] = inf;
f[n+1][n+1][0][0] = f[n+1][n+1][1][0] = 0;
for (int len = 0; len < n; len++)
for (int l = n + 1 - len, r = n + 1; l <= n + 1; l++, r++)
for (int k = 0; k < 2; k++)
for (int i = 0; i < n; i++)
upd(f[l-1][r][0][i+(f[l][r][k][i]+p[k?r:l]-p[l-1]<=t[l-1])],
f[l][r][k][i] + p[k?r:l] - p[l-1]),
upd(f[l][r+1][1][i+(f[l][r][k][i]+p[r+1]-p[k?r:l]<=t[r+1])],
f[l][r][k][i] + p[r+1] - p[k?r:l]);
for (int l = 1; l <= n + 1; l++)
for (int r = n + 1; r <= (n << 1 | 1); r++)
for (int k = 0; k < 2; k++)
for (int i = 0; i <= n; i++)
if (f[l][r][k][i] != inf) ans = max(ans, i);
print(ans);
return 0;
}
オリンピックバス (Olympic Bus)
首先求出不变向时的答案，由于本题中的图是稠密图，我们考虑用 $\mathcal O(n^2 + m)$ 的 Dijkstra 跑。
考虑一条边 $(u,v)$ 变向之后造成的影响，不妨考虑 $1 \to n$ 的部分，$n \to 1$ 同理。
如果 $(u,v)$ 不在原本 $1 \to n$ 的最短路上，则此时的最短路要么不变，要么是强制经过 $(v,u)$ 且不经过 $(u,v)$ 的最短路。
考虑如何求后者，相当于我们要求不经过 $(u,v)$ 的情况下 $1 \to v$ 和 $u \to n$ 的最短路。考虑图中以 $1$ 为起点的最短路树和反图中以 $n$ 为起点的最短路树，若 $(u,v)$ 不在前/后者中，则可以直接得到答案，否则重新跑一遍最短路。由于最短路树上的边数只有 $\mathcal O(n)$ 条，因此这部分的时间复杂度为 $\mathcal O(n^3 + nm)$。
如果 $(u,v)$ 在原本 $1 \to n$ 的最短路上，则同样重新跑一遍最短路，时间复杂度同样为 $\mathcal O(n^3 + nm)$。
const int N = 207, M = 1e5 + 7;
const ll inf = 1e18;
int n, m;
int h[N], e[M], t[M], tot = 1;
ll c[M], d[M], now, ans = inf;
bool u[M];
struct Gragh {
ll f[N];
bool in[M];
} G1, Gn, GT1, GTn;
inline void add(int x, int y, int c, int d, int o = 1) {
e[++tot] = y, t[tot] = h[x], h[x] = tot;
::c[tot] = c, ::d[tot] = d, u[tot] = o;
if (o) add(y, x, c, d, 0);
}
namespace Dij {
ll e[N][N], f[N];
int a[N][N], g[N];
bool v[N];
inline ll dij(int S, int T) {
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++)
e[x][y] = inf;
for (int i = h[x]; i; i = t[i]) {
if (!u[i]) continue;
int y = ::e[i];
if (e[x][y] > c[i])
e[x][y] = c[i], a[x][y] = i;
}
}
for (int i = 0; i <= n; i++)
f[i] = inf, g[i] = v[i] = 0;
f[S] = 0;
for (int i = 1; i <= n; i++) {
int x = 0;
for (int j = 1; j <= n; j++) {
if (v[j]) continue;
if (f[j] < f[x]) x = j;
}
v[x] = 1;
for (int y = 1; y <= n; y++) {
if (v[y]) continue;
if (f[y] > f[x] + e[x][y])
f[y] = f[x] + e[x][y], g[y] = a[x][y];
}
}
return f[T];
}
inline void get(Gragh &G) {
for (int i = 1; i <= n; i++) G.f[i] = f[i], G.in[g[i]] = 1;
}
}
using Dij::dij;
using Dij::get;
inline ll work(int i) {
now = d[i];
u[i] = 0, u[i^1] = 1;
if (G1.in[i]) now += dij(1, n);
else {
ll cur = c[i] + G1.f[e[i]];
if (GTn.in[i]) cur += dij(e[i^1], n);
else cur += GTn.f[e[i^1]];
now += min(G1.f[n], cur);
}
if (Gn.in[i]) now += dij(n, 1);
else {
ll cur = c[i] + Gn.f[e[i]];
if (GT1.in[i]) cur += dij(e[i^1], 1);
else cur += GT1.f[e[i^1]];
now += min(Gn.f[1], cur);
}
u[i] = 1, u[i^1] = 0;
return now;
}
int main() {
rd(n, m);
for (int i = 1, x, y, c, d; i <= m; i++)
rd(x, y), rd(c, d), add(x, y, c, d);
now += dij(1, n), get(G1);
now += dij(n, 1), get(Gn);
ans = min(ans, now);
for (int i = 2; i <= tot; i++) u[i] ^= 1;
dij(1, n), get(GT1);
dij(n, 1), get(GTn);
for (int i = 2; i <= tot; i++) u[i] ^= 1;
for (int i = 2; i <= tot; i += 2) ans = min(ans, work(i));
print(ans == inf ? -1 : ans);
return 0;
}
火事 (Fire)
考虑平面直角坐标系中 $([1,n],[0,n])$ 的部分，其中 $(i,j)$ 对应题目中的 $S_i(j)$。
注意到每个 $S_i$ 的覆盖范围都是一个平行四边形，而这样一个平行四边形可以拆成四个三角形，每个三角形 $(a,b,c)$ 表示 $([a,+\infty), [x-b,+\infty))$ 的部分权值 $+c$。
再看询问，一次询问 $(t,l,r)$ 可以差分为 $(t,r) – (t,l-1)$，其中 $(t,p)$ 表示 $((-\infty, p], t)$ 的权值和。
于是问题变成 $(a,b,c)$ 加 $(t,p)$ 求和，以 $y$ 轴正方向进行扫描线，考虑一个 $(a,b,c)$ 在满足 $a-b \le t$ 的情况下对 $(t,p)$ 的贡献为 $c\cdot (\min(t+b,p)-\min(a-1,p))$。
由于 $(t,p)$ 是 $(t,l,r)$ 差分而来的，不妨将这个贡献差分前后都减去 $ct$，则贡献为 $c\cdot (\min(b,p-t)-\min(a-1,p))$。
考虑在 $p-t$ 处维护 $c\cdot \min(b,p-t)$ 的贡献，在 $p$ 处维护 $c \cdot \min(a-1,p)$ 的贡献。于是问题变成维护一个序列，每次在 $x$ 处加 $c \cdot \min(k,x)$，同时单点查询，用两个树状数组即可维护。
最后的问题是如何找到每个 $S-i$ 覆盖的平行四边形，其实就是要找到每个 $S_i$ 左边第一个 $> S_i$ 和右边第一个 $\ge S_i$ 的位置，正反做两次单调栈即可。
总时间复杂度 $\mathcal O(n \log n)$。
const int N = 2e5 + 7;
int n, m, l[N], r[N];
ll a[N], ans[N];
struct P {
int a, b;
ll c;
inline P() {}
inline P(int a, int b, ll c) : a(a), b(b), c(c) {}
};
vector<P> p[N];
struct Q {
int p, i, o;
inline Q() {}
inline Q(int p, int i, int o) : p(p), i(i), o(o) {}
};
vector<Q> q[N];
struct BIT {
vector<ll> c;
inline BIT(int n = N) { c.resize(n); }
inline void add(ui x, ll k) {
while (x < c.size()) c[x] += k, x += x & -x;
}
inline ll ask(ui x) {
ll k = 0;
while (x) k += c[x], x -= x & -x;
return k;
}
};
int main() {
rd(n, m), rda(a, n);
for (int i = 1, t, l, r; i <= m; i++) {
rd(t, l, r);
q[t].pb(Q(r, i, 1));
q[t].pb(Q(l - 1, i, -1));
}
stack<int> st;
for (int i = 1; i <= n; i++) {
while (st.size() && a[st.top()] <= a[i]) st.pop();
l[i] = st.size() ? st.top() : 0;
st.push(i);
}
while (st.size()) st.pop();
for (int i = n; i; i--) {
while (st.size() && a[st.top()] < a[i]) st.pop();
r[i] = st.size() ? st.top() : n + 1;
st.push(i);
}
for (int i = 1; i <= n; i++) {
p[0].pb(P(i, i, a[i]));
if (l[i]) p[i-l[i]].pb(P(i, l[i], -a[i]));
if (r[i] != n + 1) p[r[i]-i].pb(P(r[i], i, -a[i]));
if (l[i] && r[i] != n + 1) p[r[i]-l[i]].pb(P(r[i], l[i], a[i]));
}
BIT cx1 = BIT(N << 1 | 1), ck1 = BIT(N << 1 | 1), cx2, ck2;
for (int t = 0; t <= n; t++) {
for (P p : ::p[t]) {
int a = p.a, b = p.b;
ll c = p.c;
cx1.add(1, c), cx1.add(b + n + 1, -c);
ck1.add(b + n + 1, c * b);
cx2.add(1, c), cx2.add(a, -c);
ck2.add(a, c * (a - 1));
}
for (Q o : ::q[t]) {
int p = o.p;
ans[o.i] += o.o * cx1.ask(p - t + n + 1) * (p - t);
ans[o.i] += o.o * ck1.ask(p - t + n + 1);
ans[o.i] -= o.o * cx2.ask(p + 1) * p;
ans[o.i] -= o.o * ck2.ask(p + 1);
}
}
for (int i = 1; i <= m; i++) print(ans[i]);
return 0;
}
