JOI Open 2019 题解

JOI Open 2019

三级跳

考虑 $a,b$ ，注意到如果存在 $a < i < b$ 且 $A_i \ge A_a$ ， $A_i \ge A_b$ ，则选择 $a,i$ 或者 $i,b$ 一定比 $a,b$ 不劣。

因此理论上可能成为答案的 $a,b$ 只有 $\mathcal O(n)$ 组，具体而言就是每个 $i$ 的左右第一个 $\ge A_i$ 的位置，用单调栈就可以求出来。

把询问离线下来按照 $l$ 从大到小排序，用一个指针从右向左扫。

当扫到 $i$ 时，把所有 $a = i$ 的 $A_a + A_b$ 加到 $\ge 2b - a$ 的位置，然后对于所有 $l = i$ 的询问，查询 $[l,r]$ 的最大值。

用线段树维护即可，对于一个区间要维护最大的 $a$ 以及最大的加权。

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

const int N = 5e5 + 7;
int n, m;
ui a[N], ans[N];
vector<pi> q[N];

struct SGT {
	struct T {
		int l, r;
		ui x, y, z;
	} t[N<<2|1];
	
	inline void update(int p) {
		t[p].z = max(t[ls].z, t[rs].z);
	}

	inline void work(int p, ui x) {
		t[p].z = max(t[p].z, t[p].x + (t[p].y = max(t[p].y, x)));
	}
	
	inline void spread(int p) {
		if (t[p].y) work(ls, t[p].y), work(rs, t[p].y), t[p].y = 0;
	}

	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		if (l == r) return t[p].x = a[l], void();
		build(ls, l, md), build(rs, md + 1, r);
		t[p].x = max(t[ls].x, t[rs].x);
	}

	void add(int p, int l, int r, ui x) {
		if (t[p].l >= l && t[p].r <= r) return work(p, x);
		spread(p);
		if (l <= md) add(ls, l, r, x);
		if (r > md) add(rs, l, r, x);
		update(p);
	}

	ui ask(int p, int l, int r) {
		if (t[p].l >= l && t[p].r <= r) return t[p].z;
		spread(p);
		ui ret = 0;
		if (l <= md) ret = max(ret, ask(ls, l, r));
		if (r > md) ret = max(ret, ask(rs, l, r));
		return ret;
	}
} sgt;

int s[N], t;
vi p[N];

int main() {
	rd(n), rda(a, n), sgt.build(1, 1, n), rd(m);
	for (int i = 1; i <= n; i++) {
		while (t && a[s[t]] < a[i]) p[s[t--]].pb(i);
		if (s[t]) p[s[t]].pb(i);
		s[++t] = i;
	}
	for (int i = 1, l, r; i <= m; i++)
		rd(l, r), q[l].pb(mp(r, i));
	for (int i = n; i; i--) {
		for (int j : p[i])
			if (2 * j - i <= n)
				sgt.add(1, 2 * j - i, n, a[i] + a[j]);
		for (pi o : q[i])
			ans[o.se] = sgt.ask(1, i, o.fi);
	}
	for (int i = 1; i <= m; i++) print(ans[i]);
	return 0;
}

汇款

暴力，不停地贪心地给钱。

由于每轮能给的钱数都会折半，因此最多只有 $\mathcal O(\log w)$ 轮。

最后判一下特殊情况即可。

const int N = 1e6 + 7;
int n, a[N], b[N]; 

int main() {
	rd(n);
	for (int i = 0; i < n; i++) rd(a[i], b[i]);
	while (1) {
		bool ok = 0;
		for (int i = 0, j = 1; i < n; i++, j = ++j == n ? 0 : j) {
			int c = (a[i] - b[i]) >> 1;
			if (a[i] - b[i] > 1) a[j] += c, a[i] -= c << 1, ok = 1; 
		}
		if (!ok) break;
	}
	bool ok1 = 1, ok2 = 1, ok3 = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) ok1 = 0;
		if (a[i] != b[i] + 1) ok2 = 0;
		if (a[i] >= 2) ok3 = 1;
	}
	prints((ok1 || (ok2 && ok3)) ? "Yes" : "No");
	return 0;
}

病毒实验

先预处理 $2^4$ 种状态在字符串环上的最长连续段。

考虑一开始每个点都是一个集合，每个集合中有一个特殊点，表示在这个集合中的所有点都可以感染到这个特殊点。

每次枚举一个集合 A，从 A 的特殊点开始 BFS，如果能 BFS 到 B 集合，则将 AB 集合合并，以 B 集合的特殊点作为合并后集合的特殊点。

如果 A 不能走到其他集合，则用它更新答案，A 的特殊点能感染到的点数就是这个集合的最小答案，同时也是方案数。

这么做时间复杂度为 $\mathcal O((nm)^2)$ ，考虑优化。

有一个求 MST 的算法叫 Boruvka 算法：

每次暴力地给每一个连通块找一条最小的出边，然后合并起来。
直到最后只剩下一个连通块。
每次连通块数都会减半，整个过程最多进行 $\mathcal O(\log n)$ 次。
时间复杂度为 $\mathcal O(n \log n)$ 。

用在这道题上就可以了，注意在 A 合并到 B 上之后，不能再用 B 向外找出边，否则会重复访问 A。

时间复杂度 $\mathcal O(nm \log (nm))$ 。

const int K = 2e5 + 7;
char s[K];
const char dc[] = {'N', 'S', 'W', 'E'};
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

const int N = 807;
int n, m, k, a[N][N], p[17], f[N*N], ans, cnt;
bool v[N][N], w[N*N];

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

inline int F(int x, int y) {
	return x * m + y;
}

inline void F(int z, int &x, int &y) {
	x = z / m, y = z - x * m;
}

inline bool pd(int x, int y) {
	if (!a[x][y]) return 0;
	int t = 0;
	for (int o = 0; o < 4; o++) {
		int X = x + dx[o], Y = y + dy[o];
		if (X < 0 || X >= n || Y < 0 || Y >= m) continue;
		if (v[X][Y]) t |= 1 << (o ^ 1);
	}
	return p[t] == k || p[t] >= a[x][y];
}

inline int work(int i) {
	int sx, sy, t = -1;
	F(i, sx, sy);
	queue<int> qx, qy;
	vi vx, vy;
	qx.push(sx), qy.push(sy), vx.pb(sx), vy.pb(sy), v[sx][sy] = 1;
	while (qx.size()) {
		int x = qx.front(), y = qy.front();
		qx.pop(), qy.pop();
		for (int o = 0; o < 4; o++) {
			int X = x + dx[o], Y = y + dy[o];
			if (X < 0 || X >= n || Y < 0 || Y >= m || v[X][Y]) continue;
			if (pd(X, Y)) {
				if (get(F(X, Y)) == i)
					qx.push(X), qy.push(Y), vx.pb(X), vy.pb(Y), v[X][Y] = 1;
				else {
					t = get(F(X, Y));
					break;
				}
			}
		}
		if (~t) break;
	}
	for (ui i = 0; i < vx.size(); i++) v[vx[i]][vy[i]] = 0;
	if (~t) return f[i] = t, w[t] = 1, 0;
	return vx.size();
}

int main() {
	rd(k, n, m), rds(s, k);
	for (int i = 1; i <= k; i++) s[i+k] = s[i];
	k <<= 1;
	for (int s = 1; s < 16; s++) {
		map<char, bool> v;
		for (int i = 0; i < 4; i++)
			v[dc[i]] = s >> i & 1;
		for (int i = 1, t = 0; i <= k; i++)
			if (v[::s[i]]) p[s] = max(p[s], ++t);
			else t = 0;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			rd(a[i][j]);
	for (int i = 0; i < n * m; i++) f[i] = i;
	while (1) {
		for (int i = 0; i < n * m; i++) w[i] = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (!a[i][j]) w[F(i,j)] = 1;
		ans = 0, cnt = 0;
		bool ok = 0;
		for (int i = 0; i < n * m; i++)
			if (!w[i] && i == get(i)) {
				int ret = work(i);
				if (ret) {
					if (!ans || ret < ans) ans = cnt = ret;
					else if (ans == ret) cnt += ret;
				} else ok = 1;
			}
		if (!ok) break;
	}
	print(ans), print(cnt);
	return 0;
}

三级跳

汇款

病毒实验

评论