JZTXT

Codeforces Round 864 (Div. 2) 题解

发布时间 2023-04-11 20:54:28作者: SF71-H

A. Li Hua and Maze

题目保证了两个点的哈密顿距离至少为 \(2\)，所以他们不会相邻。

只要有点在角上答案就是 \(2\)，在边上但不在角上就是 \(3\)，否则就是 \(4\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
signed main () {
	int _;
	scanf ("%d", &_);
	while (_ --) {
		int n, m, x_1, y_1, x_2, y_2;
		scanf ("%d %d", &n, &m);
		scanf ("%d %d %d %d", &x_1, &y_1, &x_2, &y_2);
		if (x_1 == 1 && y_1 == 1) printf ("2\n");
		else if (x_1 == 1 && y_1 == m) printf ("2\n");
		else if (x_1 == n && y_1 == 1) printf ("2\n");
		else if (x_1 == n && y_1 == m) printf ("2\n");
		else if (x_2 == 1 && y_2 == 1) printf ("2\n");
		else if (x_2 == 1 && y_2 == m) printf ("2\n");
		else if (x_2 == n && y_2 == 1) printf ("2\n");
		else if (x_2 == n && y_2 == m) printf ("2\n");
		else {
			if (x_1 == 1 || x_1 == n || y_1 == 1 || y_1 == m) printf ("3\n");
			else if (x_2 == 1 || x_2 == n || y_2 == 1 || y_2 == m) printf ("3\n");
			else printf ("4\n");
		}
	}
	return 0;
}

B. Li Hua and Pattern

设原来的矩阵为 \(A\)，旋转 \(180\) 度后的矩阵为 \(B\)，那么就有：

\[A_{i,j}=B_{n-i+1,n-j+1} \]

\[A_{n-i+1,n-j+1}=B_{i,j} \]

那么就统计 \(A_{i,j} \neq B_{n-i+1,n-j+1}\) 的对数 \(x\)，最后别忘了去重（\(\dfrac{x}{2} \to x\)）。

如果 \(n\) 是奇数，那么选最中间的那个点多少次都满足条件，所以只需要 \(x \leq k\)。

如果 \(n\) 是偶数，多余的步数必须以 \(2\) 步为单位选，需要 \(x \leq k\) 并且 \((k-x) \bmod 2 = 0\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int a[1005][1005], n, k, diff;
signed main () {
	int _;
	scanf ("%d", &_);
	while (_ --) {
		scanf ("%d %d", &n, &k);
		for (int i = 1;i <= n; ++ i) {
			for (int j = 1;j <= n; ++ j) {
				scanf ("%d", &a[i][j]);
			}
		}
		diff = 0;
		for (int i = 1;i <= n; ++ i) {
			for (int j = 1;j <= n; ++ j) {
				diff += (a[i][j] != a[n - i + 1][n - j + 1]);
			}
		}
		diff /= 2;
		if (n % 2 == 1 && diff <= k) printf ("YES\n");
		else if (n % 2 == 0 && diff <= k && diff % 2 == k % 2) printf ("YES\n");
		else printf ("NO\n");
	}
	return 0;
}

C. Li Hua and Chess

容易发现如果查询 \((x,y)\)，目标点为 \((x',y')\)，那么就会返回 \(\max(|x-x'|,|y-y'|)\)。

查询 \((1,1)\) 加上 \(1\) 可以求出 \(\max(x',y')\)。

容易发现 \(\max(x',y')\) 肯定等于 \(\text{ask}(1,\max(x',y'))+1\) 或 \(\text{ask}(\max(x',y'),1)+1\)，等于前者那 \(x'\) 更大，否则 \(y'\) 更大，另一个可以由查询结果得出。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int ask (int x, int y) {
	cout << "? " << x << ' ' << y << endl;
	int ans;
	cin >> ans;
	return ans;
}
inline int dec (int x, int y) {
	cout << "! " << x << ' ' << y << endl;
}
signed main () {
	int t;
	cin >> t;
	while (t --) {
		int n, m;
		cin >> n >> m;
		int mxy = ask (1, 1) + 1;
		if (mxy > n) {
			int qwq = ask (1, mxy);
			dec (qwq + 1, mxy);
		}
		else if (mxy > m) {
			int qwq = ask (mxy, 1);
			dec (mxy, qwq + 1);
		}
		else {
			int X = ask (1, mxy) + 1;
			int Y = ask (mxy, 1) + 1;
			if (X != mxy) dec (X, mxy);
			else dec (mxy, Y);
		}
	}
	return 0;
}

D. Li Hua and Tree

可以暴力维护每个点的 \(father, size, val\)。

\(val\) 表示其子树中每个节点的重要度之和。

可以用 \(n\) 个堆动态维护重儿子。

容易发现，每次对 \(u\) 操作，只会修改 \(u,father_u,son_u\) 的参数，自己画画图就知道了（再不知道就看代码）。

\(father_u\) 的堆里面还需要删除 \(u\)，只需要用懒标记删除就行了。

均摊一下就是 \(O((n+m) \log n)\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
int n, m, a[100005], sub[100005], siz[100005], fath[100005];
vector < int > G[100005];
priority_queue < PII, vector < PII >, less < PII > > son[100005];
map < int, int > mp[100005];
inline void dfs (int u, int fa) {
	fath[u] = fa;
	siz[u] = 1;
	sub[u] = a[u];
	for (int v : G[u]) {
		if (v != fa) {
			dfs (v, u);
			siz[u] += siz[v];
			sub[u] += sub[v];
		}
	}
}
inline void dfs2 (int u, int fa) {
	if (fa != 0) son[fa].push (make_pair (siz[u], -u)), mp[fa][u] = 1; 
	for (int v : G[u]) {
		if (v != fa) {
			dfs2 (v, u);
		}
	} 
}
signed main () {
	scanf ("%lld %lld", &n, &m);
	for (int i = 1;i <= n; ++ i) scanf ("%lld", &a[i]);
	for (int i = 1;i < n; ++ i) {
		int u, v;
		scanf ("%lld %lld", &u, &v);
		G[u].push_back (v);
		G[v].push_back (u);
	}
	dfs (1, 0);
	dfs2 (1, 0);
	while (m --) {
		int op, x;
		scanf ("%lld %lld", &op, &x);
		if (op == 1) printf ("%lld\n", sub[x]);
		else {
			if (son[x].empty ()) continue;
			int S = -1, U = x, F = fath[x];
			while (!son[U].empty ()) {
				int nd = -son[U].top ().second;
				if (mp[U][nd] == 0) {
					son[U].pop ();
				}
				else {
					S = nd;
					break;
				}
			}
			if (S == -1) continue;
			int Sp = sub[S];
			sub[S] = sub[U];
			sub[U] -= Sp;
			Sp = siz[S];
			siz[S] = siz[U];
			siz[U] -= Sp;
			son[U].pop ();
			son[S].push (make_pair (siz[U], -U));
			if (!son[F].empty () && son[F].top ().second == -U) {
				son[F].pop ();
			}
			son[F].push (make_pair (siz[S], -S));
			mp[F][S] = 1;
			mp[F][U] = 0;
			mp[S][U] = 1;
			mp[U][S] = 0;
			fath[S] = F;
			fath[U] = S;
		}
	}
	return 0;
}

E. Li Hua and Array

这题有点像区间开根，容易发现每个数被操作 \(\log\) 次就会变成 \(1\)。

动态维护每个数操作的次数（非 \(1 \to 1\) 的次数），然后再枚举最终变成的值（一定不会太多），用一堆数据结构动态维护即可。

用了 FHQ Treap & Segment Tree & Vector & Prefix Sum，所以跑的很慢，2.73s。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
const int V = 5e6 + 5;
const int N = 1e5 + 5;
int th, phi[V], siz[V], vis[V];
vector < int > st[V], idx[V], pre[V];
int n, m, a[N];
struct fhq_treap {
	int root, tot;
	struct node {int ls, rs, val, pri, siz;} tr[N];
	inline void update (int u) {tr[u].siz = tr[tr[u].ls].siz + tr[tr[u].rs].siz + 1;}
	inline void split (int u, int v, int &x, int &y) {
		if (!u) {x = y = 0; return ;}
		if (tr[u].val <= v) split (tr[u].rs, v, tr[x = u].rs, y);
		else split (tr[u].ls, v, x, tr[y = u].ls);
		update (u);
	}
	inline int merge (int x, int y) {
		if (!x || !y) return x | y;
		if (tr[x].pri < tr[y].pri) return tr[y].ls = merge (x, tr[y].ls), update (y), y;
		return tr[x].rs = merge (tr[x].rs, y), update (x), x;
	}
	inline int create (int w) {int x = ++ tot; tr[x].val = w, tr[x].pri = randomly (1, V), tr[x].siz = 1; return x;}
	inline void ins (int w) {
		int x, y; x = y = 0;
		split (root, w - 1, x, y);
		root = merge (merge (x, create (w)), y);
	}
	inline void del (int w) {
		int x, y, z; x = y = z = 0;
		split (root, w, x, z), split (x, w - 1, x, y);
		root = merge (merge (x, y = merge (tr[y].ls, tr[y].rs)), z);
	}
	inline int kth (int k) {
		int u = root;
		while (true) {
			if (k <= tr[tr[u].ls].siz) u = tr[u].ls;
			else if (k == tr[tr[u].ls].siz + 1) return tr[u].val;
			else k -= tr[tr[u].ls].siz + 1, u = tr[u].rs;
		}
	}
	inline int pre (int w) {
		int u = root, ans = 0;
		while (true) {
			if (!u) return ans;
			else if (w <= tr[u].val) u = tr[u].ls;
			else ans = tr[u].val, u = tr[u].rs;
		}
	}
	inline int nxt (int w) {
		int u = root, ans = 0;
		while (true) {
			if (!u) return ans;
			else if (w >= tr[u].val) u = tr[u].rs;
			else ans = tr[u].val, u = tr[u].ls;
		}
	}
	inline int rank (int w) {
		int x, y, ans; x = y = ans = 0;
		split (root, w - 1, x, y), ans = tr[x].siz + 1;
		return root = merge (x, y), ans; 
	}
} fhq;
struct segtree {
	int mn[N << 2], inc[N << 2];
	inline void push_up (int u) {mn[u] = min (mn[u << 1], mn[u << 1 | 1]);}
	inline void push_down (int u) {
		if (inc[u] == -1) return ;
		mn[u << 1] = mn[u << 1 | 1] = inc[u];
		inc[u << 1] = inc[u << 1 | 1] = inc[u];
		inc[u] = -1;
	}
	inline void build (int u, int l, int r) {
		inc[u] = -1;
		if (l == r) {
			mn[u] = a[l];
			return ;
		}
		int mid = l + r >> 1;
		build (u << 1, l, mid);
		build (u << 1 | 1, mid + 1, r);
		push_up (u);
	}
	inline void update (int u, int l, int r, int x, int y, int v) {
		if (x <= l && r <= y) {
			mn[u] = v;
			inc[u] = v;
			return ;
		}
		push_down (u);
		int mid = l + r >> 1;
		if (x <= mid) update (u << 1, l, mid, x, y, v);
		if (y > mid) update (u << 1 | 1, mid + 1, r, x, y, v);
		push_up (u);
	}
	inline int query (int u, int l, int r, int x, int y) {
		if (x <= l && r <= y) return mn[u];
		push_down (u);
		int mid = l + r >> 1, ans = 1e7;
		if (x <= mid) ans = min (ans, query (u << 1, l, mid, x, y));
		if (y > mid) ans = min (ans, query (u << 1 | 1, mid + 1, r, x, y));
		return ans;
	}
} seg;
struct paint_paint {
	int sum[N << 2], inc[N << 2];
	inline void push_up (int u) {sum[u] = sum[u << 1] + sum[u << 1 | 1];}
	inline void push_down (int u, int l, int r) {
		if (!inc[u]) return ;
		int mid = l + r >> 1;
		sum[u << 1] += inc[u] * (mid - l + 1);
		sum[u << 1 | 1] += inc[u] * (r - mid);
		inc[u << 1] += inc[u];
		inc[u << 1 | 1] += inc[u];
		inc[u] = 0;
	}
	inline void modify (int u, int l, int r, int x, int y, int v) {
		if (x <= l && r <= y) {
			sum[u] += v * (r - l + 1);
			inc[u] += v;
			return ;
		}
		push_down (u, l, r);
		int mid = l + r >> 1;
		if (x <= mid) modify (u << 1, l, mid, x, y, v);
		if (y > mid) modify (u << 1 | 1, mid + 1, r, x, y, v);
		push_up (u);
	}
	inline int query (int u, int l, int r, int x, int y) {
		if (x <= l && r <= y) return sum[u];
		push_down (u, l, r);
		int mid = l + r >> 1, ans = 0;
		if (x <= mid) ans += query (u << 1, l, mid, x, y);
		if (y > mid) ans += query (u << 1 | 1, mid + 1, r, x, y);
		return ans;
	}
} seg2;
inline int binary (int id, int val) {
	if (!siz[id]) return -1;
	if (st[id][siz[id]] < val) return -1;
	int L = 1, R = siz[id];
	while (R - L > 1) {
		int mid = L + R >> 1;
		if (st[id][mid] >= val) R = mid;
		else L = mid;
	}
	if (st[id][L] >= val) return L;
	else return R;
}
inline void query_phi () {
	while (true) {
		int x;
		scanf ("%d", &x);
		printf ("%d\n", phi[x]);
	} 
}
signed main () {
	for (int i = 1;i <= 5e6; ++ i) {
		phi[i] = i;
	}
	for (int i = 2;i <= 5e6; ++ i) {
		if (vis[i]) continue;
		phi[i] = i - 1;
		for (int j = i + i;j <= 5e6; j += i) {
			vis[j] = 1;
			phi[j] -= phi[j] / i;
		}
	}
//	query_phi (); 
	scanf ("%d %d", &n, &m);
	for (int i = 1;i <= n; ++ i) scanf ("%d", &a[i]);
	fhq.root = fhq.tot = 0;
	for (int i = 0;i <= n + 1; ++ i) {
		if (i >= 1 && i <= n && a[i] == 1) continue;
		fhq.ins (i);
	}
	seg.build (1, 1, n);
	for (int i = 1;i <= 5e6; ++ i) {
		st[i].push_back (0);
		idx[i].push_back (0);
	}
	for (int i = 1;i <= n; ++ i) {
		if (a[i] == 1) {
			st[1].push_back (i);
			idx[1].push_back (0);
			siz[1] ++;
			continue;
		} 
		int cnt = 0, x = a[i];
		while (true) {
			st[x].push_back (i);
			idx[x].push_back (cnt);
			siz[x] ++;
			x = phi[x], cnt ++;
			if (x == 1) break;
		}
		st[1].push_back (i);
		idx[1].push_back (cnt);
		siz[1] ++;
	}
	for (int i = 1;i <= 5e6; ++ i) {
		pre[i].push_back (0);
		for (int j = 1;j <= siz[i]; ++ j) pre[i].push_back (pre[i][j - 1] + idx[i][j]);
	}	
	while (m --) {
		int q, l, r;
		scanf ("%d %d %d", &q, &l, &r);
		if (q == 1) {
			int lcq = l - 1;
			while (true) {
				lcq = fhq.nxt (lcq);
				if (lcq > r) break;
				if (a[lcq] == 1) {
					fhq.del (lcq);
					continue;
				}
				a[lcq] = phi[a[lcq]];
				seg.update (1, 1, n, lcq, lcq, a[lcq]);
				seg2.modify (1, 1, n, lcq, lcq, 1);
				if (a[lcq] == 1) fhq.del (lcq);
			}
		}
		else {
			int cur = a[l], flag = 0, ans = 2e9, mn = seg.query (1, 1, n, l, r);
			int sum = seg2.query (1, 1, n, l, r);
			while (true) {
				if (flag == 1) break;
				if (cur == 1) flag = 1;
				if (mn >= cur) ;
				else {
					cur = phi[cur];
					continue;
				}
				int idxl = binary (cur, l);
				int idxr = binary (cur, r);
				if (idxl == -1 || idxr == -1) {
					cur = phi[cur];
					continue;
				}
				if (st[cur][idxl] != l || st[cur][idxr] != r || idxr - idxl + 1 != r - l + 1) {
					cur = phi[cur];
					continue;
				} 
				int sum2 = pre[cur][idxr];
				if (idxl != 0) sum2 -= pre[cur][idxl - 1];
				ans = min (ans, sum2 - sum);
				cur = phi[cur];
			}
			printf ("%d\n", ans);
		}
	}
	return 0;
}
/*
hack.in:
6 4
1 7 15 12 18 24
2 1 6
1 1 4
2 1 4
2 4 6
------------------
hack.out:
17
7
6
*/