JOISC 2020 题解 · 徐皓天

JOISC 2020

Day1

ビルの飾りつけ 4 (Building 4)

先考虑 $n \le 2 \times 10^3$ 怎么做。

设 $f_{i,j,0/1}$ 表示考虑前 $i$ 个数，在 $a$ 中选了 $j$ 个数，第 $i$ 个数选的是 $a/b$ 是否可行。

那么 $\mathcal O(n^2)$ dp 即可，如果有方案，从后往前构造。

注意到对于 $f_{i,j,0/1}$ ，如果 $i,0/1$ 固定， $j$ 可行的方案为一个区间。

因此只用 $\mathcal O(n)$ dp 出对于每个 $i,0/1$ ， $f_{i,j,0/1}$ 中 $j$ 的可行区间。

const int N = 5e5 + 7, inf = 1e9;
int n, a[N<<1], b[N<<1];
pi f[N<<1][2];

inline void upd(pi &a, pi b, bool c) {
	a.fi = min(a.fi, b.fi + c), a.se = max(a.se, b.se + c);
}

inline bool pd(pi a, int x) {
	return a.fi <= x && a.se >= x;
}

int main() {
	rd(n), rda(a, n << 1), rda(b, n << 1);
	f[1][0] = mp(1, 1), f[1][1] = mp(0, 0);
	for (int i = 2; i <= (n << 1); i++)
		for (int j = 0; j < 2; j++)
			f[i][j] = mp(inf, -inf);
	for (int i = 1; i < (n << 1); i++)
		for (int j = 0; j < 2; j++)
			if (f[i][j] != mp(inf, -inf)) {
				if (j == 0 && a[i+1] >= a[i])
					upd(f[i+1][0], f[i][j], 1);
				if (j == 1 && a[i+1] >= b[i])
					upd(f[i+1][0], f[i][j], 1);
				if (j == 0 && b[i+1] >= a[i])
					upd(f[i+1][1], f[i][j], 0);
				if (j == 1 && b[i+1] >= b[i])
					upd(f[i+1][1], f[i][j], 0);
			}
	if (!pd(f[n<<1][0], n) && !pd(f[n<<1][1], n)) return print(-1), 0;
	int p = n, q = 0;
	string s;
	a[n<<1|1] = b[n<<1|1] = inf;
	for (int i = n << 1; i; i--)
		if (pd(f[i][0], p) && a[i] <= (q ? b[i+1] : a[i+1]))
			s += 'A', --p, q = 0;
		else s += 'B', q = 1;
	reverse(s.begin(), s.end());
	prints(s);
	return 0;
}

美味しい美味しいハンバーグ (Hamburg Steak)

ouuan 的做法，不知道为啥能过。（upd：现在似乎已经被卡掉了）

首先随机 $k$ 个矩形，然后依次将剩下的矩形与 $k$ 个矩形求交，哪个剩下的面积与原来的面积之比最大就选择哪个。

多次随机直到找到解，可以通过本题全部数据。

const int N = 2e5 + 7;
const ld eps = 1e-10L;
int n, k;
struct P {
	int l, d, r, u;
	inline P() {}
	inline P(int l, int d, int r, int u) : l(l), d(d), r(r), u(u) {}
	inline void in() { rd(l), rd(d), rd(r), rd(u); }
	inline ll s() {
		return (l > r || d > u) ? 0ll : 1ll * (r - l + 1) * (u - d + 1);
	}
} p[N];
vector<P> a;

inline ll calc(P a, P b) {
	a.l = max(a.l, b.l);
	a.d = max(a.d, b.d);
	a.r = min(a.r, b.r);
	a.u = min(a.u, b.u);
	return a.s();
}

inline void upd(P &a, P b) {
	a.l = max(a.l, b.l);
	a.d = max(a.d, b.d);
	a.r = min(a.r, b.r);
	a.u = min(a.u, b.u);
}

inline bool work() {
	a.clear();
	map<int, bool> v;
	for (int i = 0; i < k; i++) {
		int x = rdm(1, n);
		while (v[x]) x = rdm(1, n);
		v[x] = 1, a.pb(p[x]);
	}
	for (int i = 1; i <= n; i++)
		if (v.find(i) == v.end()) {
			ld x = 0.0L;
			int o = -1;
			for (int j = 0; j < k; j++) {
				ld y = 1.0L * calc(a[j], p[i]) / a[j].s();
				if (y > x + eps) x = y, o = j;
			}
			if (!~o) return 0;
			upd(a[o], p[i]);
		}
	return 1;
}

int main() {
	srand(time(0));
	rd(n), rd(k);
	for (int i = 1; i <= n; i++) p[i].in();
	while (!work());
	for (int i = 0; i < k; i++) print(a[i].l, ' '), print(a[i].d);
	return 0;
}

掃除 (Sweeping)

写一个可能过不了的做法。。。

先考虑没有操作 $4$ ，即没有加入新点的情况。

首先有一个显然的结论：对于至少被移动过一次的点 $i,j$ ，一定不会出现 $x_i < x_j$ 且 $y_i < y_j$ 的情况。

因此，如果我们对至少被移动过一次的点，以横坐标从小到大为第一关键字，纵坐标从大到小为第二关键字排序，则每次移动的一定是一个区间，且移动前后排序关系不变。

考虑移动的本质为，将某一个区间里的点的横坐标或纵坐标对一个定值取 $\max$ 。

于是我们可以用一个支持区间修改，单点查询的数据结构维护，比如线段树。

那对于没有被移动过的点怎么办呢？

我们可以找到每个点第一次移动的时间，然后在那个时间插入到线段树中......

插入到线段树？这件事显然做不到，因此我们还要将线段树换成平衡树。

如何找到每个点第一次移动的时间呢？

由于移动涉及到的点都在一个矩形内，因此可以用可持久化线段树维护对于每个纵坐标，任意时刻受到影响的最大横坐标。然后对于每个点，在主席树上二分即可。

查询时，直接找到一个点在平衡树中的点，然后从这个点找到根再回溯，过程中下传区间修改时的标记即可。

设 $m,q$ 同阶，时间复杂度 $\mathcal O(m \log^2 m)$ 。

如果有加入新点的操作，考虑二进制分组维护这个过程。

即，假设当前有 $k$ 个点，按照 $k$ 的二进制位下 $1$ 的位置进行分组。比如如果 $k = 21$ ，则分成 $16+4+1$ 三组。显然，组的个数是 $\mathcal O(\log k)$ 的。

对于每组内部维护没有加入新点时的情况。当加入一个新点时，分成的组会从后往前合并，合并的同时暴力重构这一组即可。

由于每个节点至多被重构 $\mathcal O(\log m)$ 次，总时间复杂度为 $\mathcal O(m \log^3 m)$ 。

代码不写了。。。

Day2

カメレオンの恋 (Chameleon's Love)

对于两个点 $x,y$ ，如果我们按照如下方式建图：

若 $x,y$ 颜色相同，则 $x,y$ 之间连一条无向边，记为 $x \leftrightarrow y$ 。
若 $x$ 喜欢 $y$ ，则连一条 $x \to y$ 的有向边。

先不考虑询问的限制次数。

如果我们询问所有的点对 $(x,y)$ ，返回的结果要么为 $1$ ，要么为 $2$ 。

如果为 $1$ ，则只有以下三种情况：

$x,y$ 颜色相同。
$x$ 喜欢 $y$ ，但 $y$ 不喜欢 $x$ 。
$y$ 喜欢 $x$ ，但 $x$ 不喜欢 $y$ 。

容易发现，当答案为 $1$ 时， $x,y$ 之间一定有边；答案为 $2$ 时， $x,y$ 之间一定无边，除了 $x \to y$ 且 $y \to x$ 的情况。

进一步可以发现，每个点的度数都是 $3$ ，但是询问出来的度数可能为 $1$ 。

若询问出来 $x$ 的度数为 $1$ ，则说明存在一个度数同样为 $1$ 的点 $y$ ，符合 $x \to y$ 且 $y \to x$ 的情况，而询问出来的那条边，则是一条无向边 $x \leftrightarrow z$ ，这意味着 $x,z$ 的颜色相同。

若询问出来 $x$ 的度数为 $3$ ，设这 $3$ 个点为 $y,z,w$ 。考虑到如果我们询问 $(x,y,z),(x,y,w),(x,z,w)$ ，其中有且仅有一组的答案为 $1$ ，其它两组的答案都为 $2$ 。

不妨设为 $1$ 的询问为 $(x,y,z)$ ，则只可能是 $x \leftrightarrow y$ 且 $z \to x$ ，或者 $x \leftrightarrow z$ 且 $y \to x$ 。

尽管我们无法得知是哪种，但是我们可以以此确定 $x \to w$ 这条边。

通过这种方法，我们可以确定所有的有向边，那么剩下的边就是无向边，即颜色相同的点。

这个做法的询问次数为 $\mathcal O(n^2)$ 的，瓶颈在询问两两点对上。

考虑优化这个过程。

我们可以通过 $\mathcal O(n)$ 次询问求出一个极大独立集。

方法为，从 $1 \sim 2n$ 依次尝试加入当前的极大独立集 $S$ ，如果询问 $(S,x)$ 的答案为 $|S| + 1$ ，则说明可以加入，否则说明有边。

找到极大独立集之后，对于独立集之外的点，在独立集中二分找到所有边。

此时还剩下独立集之外的点中的边没有找到，那么重复上述过程，直到所有剩下的点都是一个独立集。

由于每个点的度数最多为 $3$ ，因此每次独立集的大小 $\ge$ 总点数的 $\frac 14$ 。这意味着每次我们可以将点的规模缩小到原来的 $\frac 34$ ，那么一共只需要最多重复 $\mathcal O(\log n)$ 次就能找到所有边，因此求最大独立集部分的询问次数为 $\mathcal O(n \log n)$ 。

又由于每找到一条边需要一次二分，而边数是 $\mathcal O(n)$ 的，所以二分部分也只有 $\mathcal O(n \log n)$ 次询问。

这样我们就可以用 $\mathcal O(n \log n)$ 次询问找到所有边，为了减小常数防止被卡，可以先对点进行 random_shuffle。

inline int get(int x, vi p) {
	int l = 0, r = p.size() - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		vi q(1, x);
		for (int i = l; i <= mid; i++) q.pb(p[i]);
		if (Query(q) != (int)q.size()) r = mid;
		else l = mid + 1;
	}
	return p[l];
}

inline int ask(int x, int y, int z) {
	vi p(3);
	p[0] = x, p[1] = y, p[2] = z;
	return Query(p);
}

void Solve(int n) {
	srand(time(0));
	vi A, B;
	for (int i = 1; i <= (n << 1); i++) B.pb(i);
	random_shuffle(B.begin(), B.end());
	vector<vi> e(n << 1 | 1);
	while (B.size()) {
		vi S = B, v(n << 1 | 1);
		A.clear(), B.clear();
		for (int x : S) {
			A.pb(x);
			if (Query(A) != (int)A.size()) A.pop_back(), B.pb(x);
			else v[x] = 1;
		}
		for (int i : B) {
			vi p = A;
			p.pb(i);
			do {
				p.pop_back();
				int k = get(i, p);
				e[k].pb(i), e[i].pb(k);
				for (int &x : p)
					if (x == k) swap(x, p.back());
				p.pop_back();
				p.pb(i);
			} while (Query(p) != (int)p.size());
		}
	}
	vi v(n << 1 | 1);
	vector<map<int, bool>> f(n << 1 | 1);
	for (int x = 1; x <= (n << 1); x++)
		if (e[x].size() == 3u) {
			int y = e[x][0], z = e[x][1], w = e[x][2];
			if (ask(x, y, w) == 1) swap(z, w);
			else if (ask(x, z, w) == 1) swap(y, w);
			f[x][w] = f[w][x] = 1;
		}
	for (int x = 1; x <= (n << 1); x++)
		if (!v[x])
			for (int y : e[x])
				if (!f[x][y]) v[x] = v[y] = 1, Answer(x, y);
}

ジョイッターで友だちをつくろう (Making Friends on Joitter is Fun)

并查集维护每个极大团即可。

如果某一次加边后，存在两个团之间可以互相到达，则需要合并这两个团。

用 set 维护每个团内的节点，点团之间的边，和团团之间的边，合并时启发式合并。

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

const int N = 1e5 + 7;
int n, m, f[N];
set<int> s[N], e[N], g[N], fe[N], fg[N];
deque<int> X, Y;
ll ans;

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

inline void work(int x, int y) {
	int fx = get(x), fy = get(y);
	if (fx == fy) return;
	if (fe[fy].find(fx) == fe[fy].end()) {
		if (g[fy].find(x) == g[fy].end())
			ans += s[fy].size(),
			e[x].insert(fy), g[fy].insert(x),
			fe[fx].insert(fy), fg[fy].insert(fx);
		return;
	}
	ans -= 1ll * s[fx].size() * (s[fx].size() - 1);
	ans -= 1ll * s[fy].size() * (s[fy].size() - 1);
	fe[fy].erase(fx), fg[fx].erase(fy);
	if (s[fx].size() < s[fy].size()) swap(fx, fy);
	for (int i : s[fy]) {
		for (int j : e[i])
			ans -= s[j].size(),
			g[j].erase(i),
			X.pb(i), Y.pb(j);
		e[i].clear();
	}
	for (int i : g[fy])
		ans -= s[fy].size(),
		e[i].erase(fy),
		X.pb(i), Y.pb(fx);
	g[fy].clear();
	for (int i : fe[fy]) fg[i].erase(fy);
	for (int i : fg[fy]) fe[i].erase(fy);
	for (int i : s[fy]) s[fx].insert(i);
	f[fy] = fx;
	ans += 1ll * s[fx].size() * (s[fx].size() - 1);
	ans += 1ll * g[fx].size() * s[fy].size();
	s[fy].clear();
}

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) f[i] = i, s[i].insert(i);
	for (int i = 1, x, y; i <= m; i++) {
		rd(x), rd(y), X.pb(x), Y.pb(y);
		while (X.size()) work(X[0], Y[0]), X.pop_front(), Y.pop_front();
		print(ans);
	}
	return 0;
}

最古の遺跡 3 (Ruins 3)

题目太神仙了，先咕咕咕着。

Day3

星座 3 (Constellation 3)

考虑从上往下选，则如果选择了一个星星，那下面就由一些星星不能选了。

建出笛卡尔树之后可以发现，笛卡尔树上面的每个节点都对应着一个极大矩形，而一棵星星所在的极大矩形，在笛卡尔树上正好是一条，从某个节点到其子树内某个叶子的路径。

因此对于一个笛卡尔树上的节点，其对应区间的上面最多只会有一颗星星。考虑树形 dp，设 $f_{i,j}$ 表示在横坐标为 $i$ 的节点对应区间的上面，星星的纵坐标为 $j$ 时的最大权值和。

直接 dp 状态数有 $\mathcal O(n^2)$ 个，但有效的状态只和星星数有关。

因此用 map 记录有效状态，转移时启发式合并即可，时间复杂度 $\mathcal O(n \log^2 n)$ 。

const int N = 2e5 + 7;
int n, m, a[N], s[N], t, l[N], r[N], rt;
map<int, ll> f[N];
ll g[N], z[N], ans, sum;

inline void work(int x, int y) {
	while (f[x].size() && f[x].begin() -> fi <= y)
		g[x] = max(g[x], f[x].begin() -> se + z[x]), f[x].erase(f[x].begin());
}

inline int merge(int x, int y) {
	if (f[x].size() < f[y].size()) swap(x, y);
	z[x] += g[y], z[y] += g[x], g[x] += g[y];
	for (auto o : f[y]) f[x][o.fi] = max(f[x][o.fi], o.se + z[y] - z[x]);
	return x;
}

int dfs(int x) {
	int y = x;
	if (l[x]) l[x] = dfs(l[x]), work(l[x], a[x]), y = merge(y, l[x]);
	if (r[x]) r[x] = dfs(r[x]), work(r[x], a[x]), y = merge(y, r[x]);
	return y;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		rd(a[i]);
		int k = t;
		while (k && a[s[k]] < a[i]) --k;
		if (k) r[s[k]] = i;
		if (k < t) l[i] = s[k+1];
		s[++k] = i, t = k;
	}
	rt = s[1];
	rd(m);
	for (int i = 1, x, y, z; i <= m; i++)
		rd(x), rd(y), rd(z), f[x][y] = z, sum += z;
	rt = dfs(rt), ans = g[rt];
	for (auto o : f[rt]) ans = max(ans, o.se + z[rt]);
	print(sum - ans);
	return 0;
}

収穫 (Harvest)

题目太神仙了，先咕咕咕着。

迷い猫 (Stray Cat)

通信题，扔了。

Day4

首都 (Capital City)

答案相当于要找到一个包含颜色最少的连通块，满足连通块内的颜色和连通块外的颜色两两不同，我们称这样的连通块为合法连通块。

考虑点分治，对于每一次点分出来的重心和连通块，我们在连通块中找到最小的包含重心的合法连通块，用这个连通块的答案去更新答案。

这样，最优解一定会被更新到，时间复杂度 $\mathcal O(n \log n)$ 。

const int N = 2e5 + 7;
int n, m, a[N], c[N], ans, f[N], s[N], rt, mn;
vi e[N], b[N], p;
bool u[N], v[N], w[N];

void getrt(int x, int S) {
	v[x] = 1, s[x] = 1;
	if (!b[a[x]].size()) p.pb(a[x]);
	b[a[x]].pb(x); 
	int o = 0;
	for (int y : e[x])
		if (!v[y] && !w[y]) getrt(y, S), s[x] += s[y], o = max(o, s[y]);
	o = max(o, S - s[x]);
	if (o < mn) rt = x, mn = o;
	v[x] = 0;
}

void dfs(int x) {
	v[x] = 1, s[x] = 1;
	for (int y : e[x])
		if (!v[y] && !w[y]) f[y] = x, dfs(y), s[x] += s[y];
	v[x] = 0;
}

void solve(int x, int S) {
	rt = x, mn = S, f[x] = 0, getrt(x, S), dfs(rt);
	queue<int> q;
	q.push(a[rt]), u[a[rt]] = 1, v[rt] = 1;
	int cnt = 0;
	bool ok = (int)b[a[rt]].size() == c[a[rt]];
	while (ok && q.size()) {
		int x = q.front();
		q.pop();
		for (int y : b[x])
			while (!v[y]) {
				v[y] = 1;
				if (!u[a[y]]) {
					if ((int)b[a[y]].size() != c[a[y]]) ok = 0;
					q.push(a[y]), u[a[y]] = 1, ++cnt;
				}
				y = f[y];
			}
	}
	if (ok) ans = min(ans, cnt);
	for (int x : p) {
		for (int y : b[x]) v[y] = 0;
		b[x].clear(), u[x] = 0;
	}
	p.clear();
	w[rt] = 1;
	int now = rt;
	for (int nxt : e[now])
		if (!w[nxt]) solve(nxt, s[nxt]);
}

int main() {
	rd(n), rd(m), ans = m;
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	for (int i = 1; i <= n; i++) rd(a[i]), ++c[a[i]];
	solve(1, n), print(ans);
	return 0;
}

伝説の団子職人 (Legendary Dango Maker)（1,2,3,4,5,6）

提答题，扔了。

治療計画 (Treatment Project)

我们以横坐标为时间轴，纵坐标为位置轴构建平面直角坐标系。

考虑一个治疗方案 $(T_i,L_i,R_i)$ 单独在这样一个坐标系中的覆盖区域，可以发现其覆盖的区域为以 $(T_i,L_i),(T_i,R_i)$ 为两个 $45^\circ$ 角向右的一个等腰直角三角形。

特别地，对于 $L_i = 1$ 的方案，它还能多覆盖一点三角形下方的区域；对于 $R_i = n$ 的方案，它还能多覆盖一点三角形上方的区域。具体可以自己手画一下。

由于最终要求所有人都被治愈，因此一个方案合法当且仅当这些区域可以拼接起来且使某个 $L_i=1$ 的方案与某个 $R_i = n$ 的方案连通。

注意，这里的拼接并不是指有交，对于方案 $i,j$ ， $i$ 可以与 $j$ 单向地拼接当且仅当 $|T_i-T_j|\le R_i - L_j + 1$ ，具体也可以自己手画一下。

显然，求解这个问题就是一个最短路。

直接连边边数是 $\mathcal O(m^2)$ 的，显然无法承受，用线段树 + set 优化连边即可。

这个优化连边的 Trick 跟 P5471 [NOI2019]弹跳很像。具体来说，在点权最短路上，每个点最多只会被松弛一次，即对于每个点，第一次更新到它时的值就是它的最短路（在边权最短路中这显然是不一定的）。于是我们可以在某一个点被更新过就立刻删掉它，这样时间复杂度就与边数无关，为 $\mathcal O(n \log n)$ 了。

这两道题都有一个共同点是，二维平面上从一个点到一个区域连边跑点权最短路，于是我们可以用一棵线段树维护第一维，线段树中每个节点用一个 set 存下在第一维里这个区间内的所有点，这样每个点被复制了 $\mathcal O(\log m)$ 次，总点数为 $\mathcal O(m \log m)$ ，跑上述所说的点权最短路，总时间复杂度为 $\mathcal O(m \log^2 m)$ 。

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m;
struct P {
	int t, l, r, c;
	inline void in() { rd(t), rd(l), rd(r), rd(c); }
	inline bool operator < (const P o) const { return t < o.t; }
} p[N];
struct T {
	int l, r;
	set<pi> s;
} t1[N<<2], t2[N<<2];
ll d[N], ans = inf;
pq<pair<ll, int>> q;
bool v[N], w[N];

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

void ins(T *t, int p, int x, pi k) {
	t[p].s.insert(k);
	if (t[p].l == t[p].r) return;
	if (x <= md) ins(t, ls, x, k);
	if (x > md) ins(t, rs, x, k);
}

void upd(T *t, int p, int l, int r, int x, ll k) {
	if (l <= t[p].l && r >= t[p].r) {
		while (t[p].s.size() && t[p].s.begin() -> fi <= x) {
			int y = t[p].s.begin() -> se;
			t[p].s.erase(t[p].s.begin());
			if (w[y]) continue;
			d[y] = k + ::p[y].c, q.push(mp(-d[y], y)), w[y] = 1;
		}
		return;
	}
	if (l <= md) upd(t, ls, l, r, x, k);
	if (r > md) upd(t, rs, l, r, x, k);
}

int main() {
	rd(m), rd(n);
	for (int i = 1; i <= n; i++) p[i].in();
	sort(p + 1, p + n + 1);
	build(t1, 1, 1, n), build(t2, 1, 1, n);
	for (int i = 1; i <= n; i++)
		ins(t1, 1, i, mp(p[i].l - p[i].t, i)),
		ins(t2, 1, i, mp(p[i].l + p[i].t, i));
	for (int i = 1; i <= n; i++)
		if (p[i].l != 1) d[i] = inf;
		else d[i] = p[i].c, q.push(mp(-d[i], i)), w[i] = 1;
	while (q.size()) {
		int x = q.top().se;
		q.pop();
		if (v[x]) continue;
		v[x] = 1;
		if (x != 1) upd(t1, 1, 1, x - 1, p[x].r - p[x].t + 1, d[x]);
		if (x != n) upd(t2, 1, x + 1, n, p[x].r + p[x].t + 1, d[x]);
	}
	for (int i = 1; i <= n; i++)
		if (p[i].r == m) ans = min(ans, d[i]);
	print(ans == inf ? -1 : ans);
	return 0;
}

Day1

Day2

Day3

Day4

伝説の団子職人 (Legendary Dango Maker)（1,2,3,4,5,6）

评论