20230127 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

主席树，树上 dp + 分类讨论，最短路

# A. Specijacija

这道题还是非常有实力的。

讨论一下 $\text{lca}$ 的位置：

询问的点是祖先关系：那么哪个小是哪个。
不是祖先关系：只能是某个 $a_i$ （因为只有在 $a_i$ 处才有分叉）。

接下来只分析第二种情况。

现在我们知道了 $\text{lca}$ 一定是 $a_i$ ，我们还能观察到 $a_i$ 分别对应最底层两两叶子之间的空隙。

我们把 $a_i$ 映射到叶子的空隙中，那么 $x, y$ 的 $\text{lca}$ 就是 $x, y$ 之间所有出现的 $a_i$ 的 $i$ 的最小值。

但是 $x, y$ 之间包含了哪些叶子并不好求。

有个小结论，设 $sx, sy$ 分别是 $x, y$ 子树内的点，那么 $lca(x, y) = lca(sx, sy)$ .

所以我们考虑把 $x, y$ 下放到它子树内的某个叶子上，就可以快速求区间最小值了。

这里是下放到 $x$ 子树内最靠左的叶子。

如何实现这个映射呢？

开一个主席树，从下往上每一层就是一个版本，在叶子层把所有叶子都插入到主席树里。

如果出现一个分叉，就把分叉的右儿子删掉即可。

那么 $a_i$ 的映射呢？

找到 $i$ 的右儿子映射的叶子节点编号再减 1 即可。

$x, y$ 是祖先关系的情况就是它们对应的叶子节点编号相同。

	#include <bits/stdc++.h>
	#define pb push_back
	#define int long long
	#define mid ((l + r) >> 1)

	using namespace std;

	const int N = 1e6 + 10;
	int n, m, typ;
	int a[N];

	int siz[N << 5], ls[N << 5], rs[N << 5];
	int rt[N], tot;

	inline void ins(int &p, int l, int r, int x){
	if(!p) p = ++tot;
	siz[p]++;
	if(l == r) return;
	if(x <= mid) ins(ls[p], l, mid, x);
	else ins(rs[p], mid + 1, r, x);
	}

	inline void del(int &p, int pre, int l, int r, int x){
	if(!p) p = ++tot;
	siz[p] = siz[pre] - 1;
	if(l == r) return;
	if(x <= mid) rs[p] = rs[pre], del(ls[p], ls[pre], l, mid, x);
	else ls[p] = ls[pre], del(rs[p], rs[pre], mid + 1, r, x);
	}

	inline int kth(int p, int l, int r, int x){
	if(l == r) return l;
	if(x <= siz[ls[p]]) return kth(ls[p], l, mid, x);
	else return kth(rs[p], mid + 1, r, x - siz[ls[p]]);
	}

	int mn[N][20];

	inline int get(int x){
	int d = sqrt(2 * x);
	if(d * (d + 1) / 2 < x) d++;
	return kth(rt[d], 1, n + 1, x - d * (d - 1) / 2);
	}

	inline void init(){
	for(int i = 1; i <= n; ++i) mn[get(a[i] + i + 1) - 1][0] = a[i];
	for(int j = 1; j <= 19; ++j)
	for(int i = 1; i + (1 << j) - 1 <= n; ++i)
	mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
	}

	inline int lca(int l, int r){
	if(l == r) return 1e18;
	if(l > r) swap(l, r); r--;
	int k = log2(r - l + 1);
	return min(mn[l][k], mn[r - (1 << k) + 1][k]);
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> n >> m >> typ;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n + 1; ++i) ins(rt[n + 1], 1, n + 1, i);
	for(int i = n; i >= 1; --i)
	del(rt[i], rt[i + 1], 1, n + 1, kth(rt[i + 1], 1, n + 1, a[i] - i * (i - 1) / 2 + 1));
	init();
	int ans = 0;
	while(m--){
	int x, y; cin >> x >> y;
	if(typ){
	x = (x - 1 + ans) % ((n + 1) * (n + 2) / 2) + 1;
	y = (y - 1 + ans) % ((n + 1) * (n + 2) / 2) + 1;
	}
	cout << (ans = min({x, y, lca(get(x), get(y))})) << '\n';
	}
	return 0;
	}

# B. Svjetlo

巨大分类讨论。

设 $f_{i, j, k}$ 表示子树 $i$ 内有起点 / 终点中的 $j$ 个，且当前 $i$ 的状态为 $k$ 时的最小操作次数。

找到一个 $s_i = 0$ 的 $i$ 跑一遍树形 $\text{dp}$ 即可，因为这个点一定会被经过。

最后答案就是 $f_{i, 2, 1}$ 。

转移过程讨论接头如何合并，然后 0/1 状态是否需要改变。

就不细说了（

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	const int N = 5e5 + 10;
	int n;
	char s[N];
	vector <int> G[N];
	int siz[N], f[N][3][2];

	inline void Min(int &x, int y) {x = x < y ? x : y;}

	inline void dfs(int x, int fa){
	for(int j = 0; j < 3; ++j) f[x][j][siz[x]] = 1;
	for(auto y : G[x]){
	if(y == fa) continue;
	dfs(y, x), siz[x] += siz[y];
	if(!siz[y]) continue;
	int g[3][2];
	memset(g, 0x3f, sizeof(g));
	for(int k = 0; k < 2; ++k){
	Min(g[0][k], f[x][0][k] + f[y][0][0] + 3);
	Min(g[0][k], f[x][0][!k] + f[y][0][1] + 1);
	Min(g[1][k], f[x][1][k] + f[y][0][0] + 3);
	Min(g[1][k], f[x][1][!k] + f[y][0][1] + 1);
	Min(g[1][k], f[x][0][k] + f[y][1][1]);
	Min(g[1][k], f[x][0][!k] + f[y][1][0] + 2);
	Min(g[2][k], f[x][2][k] + f[y][0][0] + 3);
	Min(g[2][k], f[x][2][!k] + f[y][0][1] + 1);
	Min(g[2][k], f[x][1][k] + f[y][1][1]);
	Min(g[2][k], f[x][1][!k] + f[y][1][0] + 2);
	Min(g[2][k], f[x][0][k] + f[y][2][0] + 1);
	Min(g[2][k], f[x][0][!k] + f[y][2][1] + 3);
	}
	memcpy(f[x], g, sizeof(g));
	}
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> n >> (s + 1);
	for(int i = 1; i < n; ++i){
	int u, v; cin >> u >> v;
	G[u].pb(v), G[v].pb(u);
	}
	for(int i = 1; i <= n; ++i) siz[i] = (s[i] == '0');
	memset(f, 0x3f, sizeof(f));
	for(int i = 1; i <= n; ++i)
	if(s[i] == '0') {
	dfs(i, 0);
	cout << f[i][2][1] << '\n';
	return 0;
	}
	return 0;
	}

# C. Portal

连边，跑最短路即可。

向四周连边权为 1 的边。
向上下左右的墙连边权为距离上下左右的墙最短的距离的边。

	#include <bits/stdc++.h>
	#define pb push_back
	#define fi first
	#define se second

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 510;
	typedef pair<int, int> P;
	int n, m, s, t;
	char ch[N][N];
	int id[N][N], idx;
	int dx[] = {-1, 0, 1, 0};
	int dy[] = {0, 1, 0, -1};
	bool vis[N][N];
	int d[N][N], to[N][N][4];

	inline bool chk(int x, int y){
	return x >= 1 && x <= n && y >= 1 && y <= m;
	}

	inline void bfs(){
	queue <P> q;
	memset(d, 0x3f, sizeof(d));
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j)
	if(ch[i][j] == '#') q.push({i, j}), vis[i][j] = 1, d[i][j] = 0;
	while(!q.empty()){
	int x = q.front().fi, y = q.front().se; q.pop();
	for(int i = 0; i < 4; ++i){
	int tx = x + dx[i], ty = y + dy[i];
	if(chk(tx, ty) && !vis[tx][ty]){
	d[tx][ty] = d[x][y] + 1, vis[tx][ty] = 1, q.push({tx, ty});
	}
	}
	}
	}

	struct node{
	int v, w, nxt;
	}edge[N * N * 10];
	int head[N * N], tot;
	int dis[N * N];

	inline void add(int x, int y, int z){
	edge[++tot] = (node){y, z, head[x]}, head[x] = tot;
	}

	inline int dij(){
	memset(dis, 0x3f, sizeof(dis));
	priority_queue <P, vector<P>, greater<P> > q;
	q.push(P(0, s)), dis[s] = 0;
	while(!q.empty()){
	int x = q.top().se, d = q.top().fi; q.pop();
	if(dis[x] < d) continue;
	for(int i = head[x]; i; i = edge[i].nxt){
	int y = edge[i].v;
	if(dis[y] > dis[x] + edge[i].w)
	dis[y] = dis[x] + edge[i].w, q.push(P(dis[y], y));
	}
	}
	return dis[t];
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read(), m = read();
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j) id[i][j] = ++idx;
	for(int i = 1; i <= n; ++i){
	scanf("%s", ch[i] + 1);
	for(int j = 1; j <= m; ++j){
	if(ch[i][j] == 'C') s = id[i][j];
	if(ch[i][j] == 'F') t = id[i][j];
	}
	}
	bfs();
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j)
	if(ch[i][j] != '#'){
	to[i][j][0] = (ch[i - 1][j] == '#') ? id[i][j] : to[i - 1][j][0];
	to[i][j][3] = (ch[i][j - 1] == '#') ? id[i][j] : to[i][j - 1][3];
	}
	for(int i = n; i >= 1; --i)
	for(int j = m; j >= 1; --j)
	if(ch[i][j] != '#'){
	to[i][j][1] = (ch[i][j + 1] == '#') ? id[i][j] : to[i][j + 1][1];
	to[i][j][2] = (ch[i + 1][j] == '#') ? id[i][j] : to[i + 1][j][2];
	}
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j){
	if(ch[i][j] == '#') continue;
	for(int k = 0; k < 4; ++k){
	int x = i + dx[k], y = j + dy[k];
	if(ch[x][y] != '#') add(id[i][j], id[x][y], 1);
	if(to[i][j][k] != id[i][j]) add(id[i][j], to[i][j][k], d[i][j]);
	}
	}
	int ans = dij();
	if(ans > 1e9) puts("nemoguce");
	else write(ans), puts("");
	return 0;
	}

# A. Specijacija

# B. Svjetlo

# C. Portal

20230117

Codeforces Round 843 (Div. 2) 题解