JOI Final 2018 题解

JOI Final 2018

ストーブ (Stove)

用个堆维护差分后的序列，每次取最小的。

const int N = 1e5 + 7;
int n, k, a[N], ans;

int main() {
	rd(n, k), rda(a, n), ans = n;
	pq<int> q;
	for (int i = 1; i < n; i++)
		q.push(-a[i+1] + a[i] + 1);
	while (k++ < n) ans -= q.top(), q.pop();
	print(ans);
	return 0;
}

美術展 (Art Exhibition)

排序后前缀和统计。

const int N = 5e5 + 7;
const ll inf = 1e18;
int n;
pair<ll, ll> a[N];
ll now = inf, ans;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i].fi, a[i].se);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		a[i].se += a[i-1].se;
		now = min(now, a[i-1].se - a[i].fi);
		ans = max(ans, a[i].se - a[i].fi - now);
	}
	print(ans);
	return 0;
}

団子職人 (Dango Maker)

将每个 G 横纵方向的合法情况当成一个点，显然可以得到一个二分图匹配模型。

然后会发现有连边的只可能是 $(x,y)$ 与 $(x+1,y-1)$ 的两个不同方向。

于是对于每一条斜线 DP 即可，总时间复杂度 $\mathcal O(nm)$。

const int N = 3e3 + 7, inf = 1e9;
int n, m, ans, f[2][N][N];
char s[N][N];

inline bool pd(int o, int i, int j) {
	if (!o) return s[i][j-1] == 'R' && s[i][j] == 'G' && s[i][j+1] == 'W';
	return s[i-1][j] == 'R' && s[i][j] == 'G' && s[i+1][j] == 'W';
}

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++) rds(s[i], m);
	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++)
			f[0][i][j] = f[1][i][j] = -inf;
	for (int i = 2; i <= n + m; i++) {
		int now = 0, X = 0, Y = 0;
		for (int x = max(1, i - m); x <= min(n, i - 1); x++) {
			int y = i - x;
			if (pd(0, x, y)) f[0][x][y] = max(f[0][x-1][y+1], now) + 1;
			if (pd(1, x, y)) f[1][x][y] = max(f[1][x-1][y+1], now) + 1;
			now = max(now, max(f[0][x-1][y+1], f[1][x-1][y+1]));
			X = x, Y = y;
		}
		ans += max(now, max(f[0][X][Y], f[1][X][Y]));
	}
	print(ans);
	return 0;
}

定期券 (Commuter Pass)

首先跑 $4$ 遍 Dijkstra 求出四个特殊点到每个点的最短路。

把从 $s$ 到 $t$ 的所有可能是最短路的边找出来，发现这一定是个 DAG。

没有代价的部分一定是 DAG 上的一条路径，于是 DAG 上 DP 一下即可，采用记忆化搜索会很方便。

总时间复杂度 $\mathcal O(m \log n)$。

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m, s, t, a, b;
ll ds[N], dt[N], da[N], db[N], ans;
vector<pi> e[N];

bool v[N];
pq<pair<ll, int>> q;

inline void dij(int S, ll *d) {
	for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
	d[S] = 0, q.push(mp(0, S));
	while (q.size()) {
		int x = q.top().se;
		q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (pi o : e[x]) {
			int y = o.fi, z = o.se;
			if (d[y] > d[x] + z)
				d[y] = d[x] + z, q.push(mp(-d[y], y));
		}
	}
}

vi g[N];
ll fa[N], fb[N];

void dfs(int x) {
	if (v[x]) return;
	v[x] = 1;
	fa[x] = da[x], fb[x] = db[x];
	for (int y : g[x])
		dfs(y), fa[x] = min(fa[x], fa[y]), fb[x] = min(fb[x], fb[y]);
	ans = min(ans, min(fa[x] + db[x], fb[x] + da[x]));
}

int main() {
	rd(n, m), rd(s, t), rd(a, b);
	for (int i = 1, x, y, z; i <= m; i++)
		rd(x, y, z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	dij(s, ds), dij(t, dt), dij(a, da), dij(b, db);
	ans = da[b];
	for (int x = 1; x <= n; x++)
		for (pi o : e[x]) {
			int y = o.fi, z = o.se;
			if (ds[x] + z + dt[y] == ds[t]) g[x].pb(y);
		}
	for (int i = 1; i <= n; i++) v[i] = 0;
	dfs(s);
	print(ans);
	return 0;
}

毒蛇の脱走 (Snake Escaping)

毒瘤题。

注意到对于每次询问 $\max(c_?,c_0,c_1) \le 6$。

对于 $c_?$ 暴力枚举；对于 $c_0,c_2$ 容斥，需要 FWT 预处理。

总时间复杂度 $\mathcal O(l2^l + 2^{\lfloor \frac l3 \rfloor}q)$。

随手跑了个 LOJ 最优解是怎么回事。。。

const int N = 20;
int l, n, q, a[1<<N|7], b[1<<N|7], c[1<<N|7];
string s, t;
int cx, c0, c1, kx, k0, k1, ans;

int main() {
	rd(l, q), n = 1 << l, rds(s);
	for (int i = 0; i < n; i++) a[i] = b[i] = c[i] = s[i] & 15;
	for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
		for (int i = 0; i < n; i += o)
			for (int j = 0; j < k; j++)
				b[i+j+k] += b[i+j], c[i+j] += c[i+j+k];
	while (q--) {
		rds(t), cx = c0 = c1 = kx = k0 = k1 = ans = 0;
		for (int i = 0; i < l; i++)
			switch (t[i]) {
				case '?' : ++cx, kx |= 1 << (l - 1 - i); break;
				case '0' : ++c0, k0 |= 1 << (l - 1 - i); break;
				case '1' : ++c1, k1 |= 1 << (l - 1 - i); break;
			}
		if (cx <= c0 && cx <= c1) {
			ans = a[k1];
			for (int s = kx; s; s = (s - 1) & kx) ans += a[s|k1];
			print(ans);
		} else if (c1 <= c0) {
			ans = (__builtin_popcount(k1) & 1) ? -b[kx] : b[kx];
			for (int s = k1; s; s = (s - 1) & k1)
				ans += (__builtin_popcount(s ^ k1) & 1) ? -b[kx^s] : b[kx^s];
			print(ans);
		} else {
			kx = (n - 1) ^ kx;
			ans = (__builtin_popcount(k0) & 1) ? -c[kx] : c[kx];
			for (int s = k0; s; s = (s - 1) & k0)
				ans += (__builtin_popcount(s ^ k0) & 1) ? -c[kx^s] : c[kx^s];
			print(ans);
		}
	}
	return 0;
}