AtCoder Grand Contest 031 题解

AtCoder Grand Contest 031

Colorful Subsequence

对于每种字符，可以选某一个或者不选，最后去掉空的。

const int N = 1e5 + 7;
int n;
char s[N];

int main() {
	rd(n), rds(s, n);
	map<char, int> c;
	for (int i = 1; i <= n; i++) ++c[s[i]];
	modint ans = 1;
	for (pi o : c) ans *= o.se + 1;
	print(ans - 1);
	return 0;
}

Reversi

首先去重，显然不影响答案。

考虑 DP，设 $f_i$ 表示以 $i$ 为最终某一段的结尾。

枚举 $i$ 所在的段的长度转移，注意 $i$ 所在的段比如跟 $i$ 的颜色相同，时间复杂度 $\mathcal O(n^2)$。

考虑转移的条件，对于每种颜色记录所有这个颜色的转移和，时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, a[N];
modint c[N], f[N];

int main() {
	rd(n), rda(a, n);
	n = unique(a + 1, a + n + 1) - (a + 1);
	c[a[1]] = f[0] = 1;
	for (int i = 1; i <= n; i++)
		f[i] = c[a[i]], c[a[i+1]] += f[i];
	print(f[n]);
	return 0;
}

Differ by 1 Bit

如果 $a\operatorname{xor}b$ 中有奇数个 $1$ 则 YES，否则 NO。

构造可以递归构造，时间复杂度 $\mathcal O(n2^n)$。

void f(int a, int b, int s) {
	if (s) {
		int d = (a ^ b) & s;
		s ^= d &= -d;
		int c = a ^ (s & -s);
		f(a, c, s), f(c ^ d, b, s);
	} else print(a, ' ');
}

int main() {
	int n, a, b;
	rd(n, a, b);
	if (__builtin_parity(a ^ b)) prints("YES"), f(a, b, (1 << n) - 1);
	else prints("NO");
	return 0;
}

A Sequence of Permutations

题意

• 对于 $1 \sim n$ 的排列 $p,q$，定义排列 $f(p,q)$，满足 $f(p,q)$ 的第 $p_i$ 个元素为 $q_i$。
• 定义排列的序列 $a$ 满足，$a_1 = p$，$a_2 = q$，$a_{n+2} = f(a_n,a_{n+1})(n \ge 1)$。
• 求 $a_k$。
• $n \le 10^5$，$k \le 10^9$。

题解

注意到 $f(p,q) = qp^{-1}$，另有 $(pq)^{-1} = q^{-1}p^{-1}$，于是有： $$\begin{aligned} a_1 &= p \\\\ a_2 &= q \\\\ a_3 &= qp^{-1} \\\\ a_4 &= qp^{-1}q^{-1} \\\\ a_5 &= qp^{-1}q^{-1}pq^{-1} \\\\ a_6 &= qp^{-1}q^{-1}pq^{-1}qpq^{-1} = qp^{-1}q^{-1}p^{2}q^{-1} \\\\ a_7 &= qp^{-1}q^{-1}p^{2}q^{-1}qp^{-1}qpq^{-1} = qp^{-1}q^{-1}pqpq^{-1} \\\\ a_8 &= qp^{-1}q^{-1}pqpq^{-1}qp^{-2}qpq^{-1} = qp^{-1}q^{-1}pqp^{-1}qpq^{-1} \\\\ \end{aligned}$$ 记 $t=qp^{-1}q^{-1}p$，则 $a_7 = tpt^{-1}$，$a_8 = tqt^{-1}$。

于是得到规律：$a_{n+6} = ta_nt^{-1}$，$a_{n+6k} = t^{k}a_nt^{-k}$。

快速幂即可，时间复杂度 $\mathcal O(n \log k)$。

代码

const int N = 1e5 + 7;
int n, k, p[N], q[N], vp[N], vq[N], t[N], vt[N], ans[N];

inline void init(int *a) {
	for (int i = 1; i <= n; i++) a[i] = i;
}

inline void inv(int *a, int *b) {
	for (int i = 1; i <= n; i++) b[a[i]] = i;
}

inline void mul(int *a, int *b) {
	static int c[N];
	for (int i = 1; i <= n; i++) c[i] = a[b[i]];
	for (int i = 1; i <= n; i++) a[i] = c[i];
}

inline void ksm(int *a, int b) {
	static int d[N];
	init(d);
	while (b) {
		if (b & 1) mul(d, a);
		mul(a, a), b >>= 1;
	}
	for (int i = 1; i <= n; i++) a[i] = d[i];
}

int main() {
	rd(n, k), rda(p, n), rda(q, n), inv(p, vp), inv(q, vq);
	init(t), mul(t, q), mul(t, vp), mul(t, vq), mul(t, p), inv(t, vt);
	int r = k % 6 ? k % 6 : 6, w = (k - r) / 6;
	ksm(t, w), ksm(vt, w);
	init(ans), mul(ans, t);
	switch (r) {
		case 1 : mul(ans, p); break;
		case 2 : mul(ans, q); break;
		case 3 : mul(ans, q), mul(ans, vp); break;
		case 4 : mul(ans, q), mul(ans, vp), mul(ans, vq); break;
		case 5 : mul(ans, q), mul(ans, vp), mul(ans, vq), mul(ans, p), mul(ans, vq); break;
		case 6 : mul(ans, q), mul(ans, vp), mul(ans, vq), mul(ans, p), mul(ans, p), mul(ans, vq); break;
	}
	mul(ans, vt);
	printa(ans, n);
	return 0;
}

Snuke the Phantom Thief

题意

• 有 $n$ 个两两不同的点，第 $i$ 个点的坐标为 $(x_i,y_i)$，价值为 $v_i$。
• 你要选择一些点，满足 $m$ 条限制，每条限制形如：
  • L a b，最多选择 $b$ 个 $x_i \le a$ 的点。
  • R a b，最多选择 $b$ 个 $x_i \ge a$ 的点。
  • D a b，最多选择 $b$ 个 $y_i \le a$ 的点。
  • U a b，最多选择 $b$ 个 $y_i \ge a$ 的点。
• 求选择的点的最大价值和。
• $n \le 80$，$m \le 320$。

题解

枚举选择的点的个数 $k$，考虑费用流。

对于每一维，那么最多 $b$ 个 $\le a$ 的点可以转化为按坐标从小到大选择的第 $[b+1,k]$ 个点的坐标要 $\ge a + 1$，最多 $b$ 个 $\ge a$ 的点可以转化为选择的第 $[1,k-b]$ 个点的坐标要 $\le a - 1$。

考虑如何建图，将点 $i$ 拆成两个点 $P_i,Q_i$，另外加入 $2k$ 个点 $X_{1\dots k},Y_{1\dots k}$，表示某一维上选择的第 $i$ 个点。

连边如下：

• $(S, X_i, 1, 0)$。
• $(X_i,P_j,1,0)$，其中点 $j$ 在 $X_i$ 的坐标限制内。
• $(P_j,Q_j,1,-v_j)$。
• $(Q_j,Y_i,1,0)$，其中点 $j$ 在 $Y_i$ 的坐标限制内。
• $(Y_i,T,1,0)$。

跑最小费用最大流即可。

代码

namespace Dinic {
	const int N = 1e5 + 7, M = 2e6 + 7;
	const ll inf = 1e18;
	int n, S, T;
	int h[N], hi[N], e[M], t[M], tot;
	ll d[N], f[M], c[M], mxf, ans;
	bool v[N];

	inline void add(int x, int y, ll z, ll w, bool o = 1) {
		e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, -w, 0);
	}

	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 0, v[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop(), v[x] = 0;
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i], w = c[i];
				if (d[y] <= d[x] + w || !z) continue;
				d[y] = d[x] + w;
				if (!v[y]) q.push(y), v[y] = 1;
			}
		}
		return d[T] != inf;
	}

	ll dfs(int x, ll now = inf) {
		if (x == T) return now;
		v[x] = 1;
		ll rst = now;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i], w = c[i];
			if (v[y] || d[y] != d[x] + w || !z) continue;
			ll k = dfs(y, min(z, rst));
			if (!k) d[y] = inf;
			else ans += k * w, f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		v[x] = 0;
		return now - rst;
	}

	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dfs(S))) mxf += now;
		}
	}

	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, tot = 1, mxf = 0, ans = 0;
		for (int i = 1; i <= n; i++) h[i] = 0; 
	}
}
using Dinic::add;

const int N = 87, M = 327;
int n, m, x[N], y[N], a[M], b[M];
char t[M];
ll v[N], ans;

inline bool in(int l, int x, int r) {
	return l <= x && x <= r;
}

inline ll work(int k) {
	static int lx[N], rx[N], ly[N], ry[N];
	for (int i = 1; i <= k; i++)
		lx[i] = ly[i] = 1, rx[i] = ry[i] = 100;
	for (int i = 1; i <= m; i++)
		switch (t[i]) {
			case 'L' : {
				for (int j = b[i] + 1; j <= k; j++)
					lx[j] = max(lx[j], a[i] + 1);
				break;
			}
			case 'R' : {
				for (int j = 1; j <= k - b[i]; j++)
					rx[j] = min(rx[j], a[i] - 1);
				break;
			}
			case 'D' : {
				for (int j = b[i] + 1; j <= k; j++)
					ly[j] = max(ly[j], a[i] + 1);
				break;
			}
			case 'U' : {
				for (int j = 1; j <= k - b[i]; j++)
					ry[j] = min(ry[j], a[i] - 1);
				break;
			}
		}
	for (int i = 1; i <= n; i++)
		if (lx[i] > rx[i] || ly[i] > ry[i]) return 0;
	static int S, T, P[N], Q[N], X[N], Y[N], C;
	S = 1, T = 2, C = 2;
	for (int i = 1; i <= n; i++) P[i] = ++C, Q[i] = ++C;
	for (int i = 1; i <= k; i++) X[i] = ++C, Y[i] = ++C;
	Dinic::init(C, S, T);
	for (int i = 1; i <= n; i++) add(P[i], Q[i], 1, -v[i]);
	for (int i = 1; i <= k; i++) {
		add(S, X[i], 1, 0), add(Y[i], T, 1, 0);
		for (int j = 1; j <= n; j++) {
			if (in(lx[i], x[j], rx[i])) add(X[i], P[j], 1, 0);
			if (in(ly[i], y[j], ry[i])) add(Q[j], Y[i], 1, 0);
		}
	}
	Dinic::main();
	return Dinic::mxf == k ? -Dinic::ans : 0;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(x[i], y[i]), rd(v[i]);
	rd(m);
	for (int i = 1; i <= m; i++) rdc(t[i]), rd(a[i], b[i]);
	for (int k = 1; k <= n; k++) ans = max(ans, work(k));
	print(ans);
	return 0;
}

Walk on Graph

题意

• 给定一张 $n$ 个点 $m$ 条边的连通无向图，边有长度。
• 定义一条路径的长度为，设这条路径经过的边的长度依次为 $l_{1\dots k}$，则路径长度为 $\sum_{i=1}^{k} l_i2^{i-1}$。
• 有 $q$ 次询问，每次给定 $s,t,r$，求是否存在一条 $s \to t$ 的路径，满足其长度模 $P$ 的值为 $r$。
• $n,m,q \le 5 \times 10^4$，$P \le 10^6$ 且为奇数。

题解

倒过来考虑这个问题，走一条边 $c$ 就是 $x\to 2x+c$，因为 $P$ 是奇数，所以 $2$ 有逆元，即这是一个双射，所以一定能回到自己。

注意到一个点走两次一条边会回到自己，$x\to 4x+3c$，那么如果有另一条边 $c^\prime$，则我们能凑出 $3(c-c^\prime)$。记 $g$ 是所有边权之差以及 $P$ 的 $\gcd$，那么我们只需要在模 $\gcd(3g, P)$ 意义下考虑这个问题即可（此时模数要么是 $g$ 要么是 $3g$）。

假设所有边模 $g$ 都为 $z$，那么令 $x^\prime=x+z$，将边权减去 $z$，走一步后新的 $x^\prime$ 会变成 $2(x^\prime-z) + (c+z) + z = 2x^\prime + c$，和原来的规则一样，所以我们可以认为在新的图中，每条边都是 $g$ 的倍数。

对于 $(1,x)$，其能到的状态可以写成 $(v, 2^px+qg)(0\le q<3)$ 的形式，由之前的变换 $x\to 4x+3c$，且 $c$ 是 $g$ 的倍数，得 $x$ 和 $4x$ 是等价状态，故 $0\le p<2$。这样新的图中点数就只有 $\mathcal O(n)$ 个了，用并查集连一下就好了。

代码

const int N = 5e4 + 7, M = 1e6 + 7;
int n, m, q, P, a[N], b[N], c[N], f[N*6+1], g, z;
bool v[2][M];

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

inline void merge(int x, int y) {
	f[get(x)] = get(y);
}

inline int id(int x, int y, int z) {
	return (x - 1) * 6 + y * 3 + z;
}

int main() {
	rd(n, m, q), rd(P);
	for (int i = 1; i <= m; i++)
		rd(a[i], b[i], c[i]), g = __gcd(g, abs(c[i] - c[1]));
	g = g ? g : P, P = __gcd(P, 3 * g), z = c[1] % g;
	for (int i = 1; i <= 6 * n; i++) f[i] = i;
	for (int i = 1; i <= m; i++) {
		int w = (c[i] - z) / g;
		for (int p = 0; p < 2; p++)
			for (int q = 0; q < 3; q++)
				merge(id(a[i], p, q), id(b[i], 1 - p, (2 * q + w) % 3)),
				merge(id(b[i], p, q), id(a[i], 1 - p, (2 * q + w) % 3));
	}
	for (int i = 0, j = z; i < P << 1; i++, (j <<= 1) %= P) v[i&1][j] = 1;
	for (int i = 1, s, t, r; i <= q; i++) {
		rd(s, t, r);
		bool ans = 0;
		for (int p = 0; p < 2; p++)
			for (int q = 0; q < 3; q++)
				if (get(id(t, 0, 0)) == get(id(s, p, q)))
					ans |= v[p][(r+z+(3-q)*g)%P];
		prints(ans ? "YES" : "NO");
	}
	return 0;
}