JOI Final 2020 题解

JOI Final 2020

長いだけのネクタイ (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;
}