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

数学 + exgcd，树形 dp，模拟 + STL，主席树 + hash

# A. 方程的解

完全就是 Luogu 上 exgcd 板子的弱化版，然而好久不写连 exgcd 都不会了 QwQ。

于是硬写一手暴力。

不过这题判无解什么的还是挺麻烦的，改题的时候各种 RE，这里就直接放代码吧。

	#include <bits/stdc++.h>
	#define int long long

	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 > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	int T, a, b, c;

	inline int exgcd(int a, int b, int &x, int &y){
	if(!b) return x = 1, y = 0, a;
	int d = exgcd(b, a % b, x, y), z = x;
	x = y, y = z - a / b * y;
	return d;
	}

	signed main(){
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	T = read();
	while(T--){
	int a = read(), b = read(), c = read(), x, y;
	if(!a && !b) {puts(!c ? "ZenMeZheMeDuo" : "0"); continue;}
	if(!a) {puts(!(c % b) && b * c > 0 ? "ZenMeZheMeDuo" : "0"); continue;}
	if(!b) {puts(!(c % a) && a * c > 0 ? "ZenMeZheMeDuo" : "0"); continue;}
	int d = exgcd(a, b, x, y);
	if(c % d) {puts("0"); continue;}
	if(a * b < 0) {puts("ZenMeZheMeDuo"); continue;}
	x = c / d, y = c / d;
	int p = b / d, q = a / d, k;
	if(x < 0) k = ceil((1.0 - x) / p), x += p * k, y -= q * k;
	else if(x >= 0) k = (x - 1) / p, x -= p * k, y += q * k;
	if(y > 0){
	if((y - 1) / q + 1 > 65535 \|\| (y - 1) / q + 1 < 0) puts("ZenMeZheMeDuo");
	else write((y - 1) / q + 1), puts("");
	}else puts("0");
	}
	return 0;
	}
	// X.K.

# B. 染色

之前写过，但是忘了 /kk。

考场上光顾着推 $\text{exgcd}$ 的式子，以及去写 $\text{C}$ 的暴力了，没有仔细去想。

那么这题就是一道树上背包经典题。

设 $f_{x, i}$ 表示 $x$ 子树内有 $i$ 个点被染成黑色，此时 $x$ 子树内的权值和。

转移也比较简单，枚举 $x$ 子树内有 $j$ 个点被染成了黑色，再枚举当前的儿子 $y$ 中有 $k$ 个点被染成黑色，有：

$f_{x, j} = \max\{f_{x, j - k} + f_{y, k} + (k \times (m - k) + (siz_y - k) \times (n - m - siz_y + k) ) \times w(x, y) \}$

转移就是考虑 $x \rightarrow y$ 这条边的贡献，也就是这条边被经过的次数乘上它的权值。

$k \times (m - k)$ 是黑色点经过的次数， $(siz_y - k) \times (n - m - siz_y + k)$ 是白色点经过的次数。

另外注意转移的时候要先判断一下是否合法再转移，具体见代码吧。

	#include <bits/stdc++.h>
	#define int long long

	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 > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 2010;
	int n, m;
	struct node{
	int v, w, nxt;
	}edge[N << 1];
	int head[N], tot;
	int f[N][N], siz[N];

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

	inline void dfs(int x, int fa){
	siz[x] = 1, f[x][0] = f[x][1] = 0;
	for(int i = head[x]; i; i = edge[i].nxt){
	int y = edge[i].v;
	if(y == fa) continue;
	dfs(y, x), siz[x] += siz[y];
	for(int j = min(m, siz[x]); j >= 0; --j){
	if(f[x][j] != -1) f[x][j] += f[y][0] + siz[y] * (n - m - siz[y]) * edge[i].w;
	for(int k = min(j, siz[y]); k > 0; --k)
	if(f[x][j - k] != -1) f[x][j] = max(f[x][j], f[x][j - k] + f[y][k] + (k * (m - k) + (siz[y] - k) * (n - m - siz[y] + k)) * edge[i].w);
	}
	}
	}

	signed main(){
	// freopen("coloration.in", "r", stdin);
	// freopen("coloration.out", "w", stdout);
	n = read(), m = read();
	if(n - m < m) m = n - m;
	for(int i = 1; i < n; ++i){
	int x = read(), y = read(), z = read();
	add(x, y, z), add(y, x, z);
	}
	memset(f, -1, sizeof(f));
	dfs(1, 0);
	write(f[1][m]), puts("");
	return 0;
	}
	// X.K.

# C. 光

就是一个大模拟，暴力就不多说了，除了难写以外没什么难的。

暴力模拟的时候我们是一格一格走的，但是这样的效率太低了，考虑如何优化。

我们把所有的障碍物存起来，由于移动的时候是斜着走的，所以我们对每条对角线都开一个 $\text{set}$ 来存障碍物。

移动的时候直接在当前对角线对应的 $\text{set}$ 里面二分查找一下第一个碰到的障碍物是哪个。

然后计算答案，再移动过去即可。

有一些小细节：

可以先单独跑一边，把第一个碰到的障碍物当作起点。
有的情况我们会把整个路径遍历两遍，所以要标记一下，输出答案的时候要处理一下。

（代码中有非常神妙的方向判断之类的，个人认为这种东西不是人能想出来的）

	#include <bits/stdc++.h>
	#define int long long

	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 > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e5 + 10;
	typedef pair<int, int> P;
	int n, m, k;
	set <P> s[2][N << 1];
	map <int, int> mp[N << 1];

	inline int get_id(int op, int x, int y) {return !op ? x - y + m + 1 : x + y;}

	inline void ins(int x, int y){
	s[0][get_id(0, x, y)].insert(P(x, y));
	s[1][get_id(1, x, y)].insert(P(x, y));
	mp[x][y] = 1;
	}

	int x, y, d, ans, flag = 1;
	string str;
	int dx[4] = {1, 1, -1, -1};
	int dy[4] = {1, -1, -1, 1};

	inline void calc(){
	if(str == "NW") d = 0;
	if(str == "NE") d = 1;
	if(str == "SE") d = 2;
	if(str == "SW") d = 3;
	}

	inline void solve(){
	auto it = s[d & 1][get_id(d & 1, x, y)].lower_bound(P(x, y));
	if(d < 2) it--;
	int sx = (it).first, sy = (it).second;
	ans += abs(x - sx);
	x = sx + dx[d], y = sy + dy[d];
	bool f1 = mp[sx].count(y), f2 = mp[x].count(sy);
	if(!(f1 ^ f2)) flag = 2, d = (d + 2) % 4;
	else if(f1) y = sy, d ^= 3;
	else x = sx, d ^= 1;
	}

	signed main(){
	n = read(), m = read(), k = read();
	for(int i = 1, x, y; i <= k; ++i)
	x = read(), y = read(), ins(x, y);
	for(int i = 0; i <= n + 1; i++) ins(i, 0), ins(i, m + 1);
	for(int i = 0; i <= m + 1; i++) ins(0, i), ins(n + 1, i);
	x = read(), y = read(), cin >> str;
	calc(), solve();
	int tx = x, ty = y, td = d;
	ans = 0, solve();
	while(x != tx \|\| y != ty \|\| d != td) solve();
	write(ans / flag), puts("");
	return 0;
	}
	// X.K.

# D. 无向图

题意之困难令人叹为观止（

简单来说就是让我们找某种判断条件下的从 $1 \sim n$ 字典序最小的路径，并输出。

判断条件就是对于每个 $p_i$ ，路径上的点 $u$ 使得 $f_u = p_i$ 的个数，按照字典序那种比较方法比， $f_i$ 和 $p_i$ 均为输入的数。

既然题目让我们找字典序最小，不妨反向思考一下。

对于 $p_x = i$ ，我们令 $rk_i = x$ 。

然后对于输入的 $f_x$ ，我们可以获得一个点权 $v_x = rk[f_x]$ 。

我们对每个点开一个桶，对于 $x \rightarrow y$ 这条边，我们只需要把 $x$ 点的桶中 $v_y$ 这一位 +1，然后把这个桶给 $y$ ，也就是说这两个点的桶中只有一个位置的数不一样。

此时字典序最小的条件就转化为了桶的字典序最小，也就是高位要尽可能的小。

我们开个优先队列（以字典序排序的小根堆）从 1 节点进行广搜，第一次搜到 $n$ 的时候字典序肯定是最小的，直接输出就可以了。

关于如何更新桶以及让小根堆按照我们想要的方式排序，也很简单，开个主席树存桶的 $\text{hash}$ 值，更新的时候就主席树正常操作更新，查询的话就在主席树上二分判断 $\text{hash}$ 值即可。

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

	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 > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 2e5 + 10;
	const int mod = 998244353;
	int n, m;
	int p[N], v[N], rk[N];
	ull px[N];
	vector <int> g[N];
	int T[N], ls[N << 5], rs[N << 5], cnt[N << 5], tot;
	ull ha[N << 5];

	inline bool cmp(int u, int v, int l, int r){
	if(!u \|\| !v) return u < v;
	if(l == r) return cnt[u] < cnt[v];
	if(ha[ls[u]] == ha[ls[v]]) return cmp(rs[u], rs[v], mid + 1, r);
	else return cmp(ls[u], ls[v], l, mid);
	}

	struct Pair{
	int rt, x;
	Pair(int _rt = 0, int _x = 0) {rt = _rt, x = _x;}
	inline bool operator < (const Pair &b) const {return ha[b.rt] == ha[rt] ? 0 : cmp(b.rt, rt, 1, n);}
	};
	priority_queue <Pair> q;

	inline int update(int pre, int l, int r, int x){
	int p = ++tot;
	ls[p] = ls[pre], rs[p] = rs[pre], cnt[p] = cnt[pre], ha[p] = ha[pre];
	if(l == r) return ha[p] = ++cnt[p], p;
	if(x <= mid) ls[p] = update(ls[pre], l, mid, x);
	else rs[p] = update(rs[pre], mid + 1, r, x);
	return ha[p] = ha[ls[p]] * px[mid - l + 1] + ha[rs[p]], p;
	}

	inline void print(int rt, int l, int r){
	if(!rt) return;
	if(l == r){
	for(int i = 1; i <= cnt[rt]; ++i) write(p[l]), putchar(' ');
	return;
	}
	print(ls[rt], l, mid), print(rs[rt], mid + 1, r);
	}

	signed main(){
	// freopen("D.in", "r", stdin);
	// freopen("D.out", "w", stdout);
	n = read(), m = read();
	px[0] = 1;
	for(int i = 1; i <= n; ++i) px[i] = px[i - 1] * 233;
	for(int i = 1; i <= n; ++i) rk[p[i] = read()] = i;
	for(int i = 1; i <= n; ++i) v[i] = rk[read()];
	for(int i = 1, u, v; i <= m; ++i)
	u = read(), v = read(), g[u].pb(v), g[v].pb(u);
	if(n == 1) return write(v[1]), puts(""), 0;
	T[1] = update(T[1], 1, n, v[1]), q.push(Pair(T[1], 1));
	while(!q.empty()){
	int x = q.top().x; q.pop();
	for(auto y : g[x]){
	if(!T[y]) T[y] = update(T[x], 1, n, v[y]), q.push(Pair(T[y], y));
	if(y == n) return print(T[n], 1, n), 0;
	}
	}
	return 0;
	}
	// X.K.

# A. 方程的解

# B. 染色

# C. 光

# D. 无向图

CF1111E Tree 题解

20220502