徐皓天 / 博客
← 全部文章

AtCoder Grand Contest 033 题解

题解

本文目录（15 节）
  1. Darker and Darker
  2. LRUD Game
  3. Removing Coins
  4. Complexity
  5. 题意
  6. 题解
  7. 代码
  8. Go around a Circle
  9. 题意
  10. 题解
  11. 代码
  12. Adding Edges
  13. 题意
  14. 题解
  15. 代码

AtCoder Grand Contest 033

Darker and Darker

怎么 AGC 还有这种垃圾题啊。

const int N = 1e3 + 7;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
int n, m, d[N][N], ans;
queue<pi> q; 

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			char c;
			rdc(c);
			if (c == '#') q.push(mp(i, j));
			else d[i][j] = -1; 
		}
	while (q.size()) {
		int x = q.front().fi, y = q.front().se;
		q.pop();
		ans = d[x][y];
		for (int i = 0; i < 4; i++) {
			int X = x + dx[i], Y = y + dy[i];
			if (X < 1 || X > n || Y < 1 || Y > m || ~d[X][Y]) continue;
			d[X][Y] = d[x][y] + 1, q.push(mp(X, Y));
		}
	}
	print(ans);
	return 0;
}

LRUD Game

四个方向独立，每个方向都判一下即可。

const int N = 2e5 + 7;
int n, m, k, x, y;
char a[N], b[N];

inline bool pd(int t, int w, char p, char q) {
	for (int i = 1; i <= k; i++) {
		if (a[i] == p) --t;
		if (!t) return 0;
		if (t != w && b[i] == q) ++t;
	}
	return 1;
}

int main() {
	rd(n, m, k), rd(x, y), rds(a, k), rds(b, k);
	if (!pd(x, n, 'U', 'D')) return prints("NO"), 0;
	if (!pd(n - x + 1, n, 'D', 'U')) return prints("NO"), 0;
	if (!pd(y, m, 'L', 'R')) return prints("NO"), 0;
	if (!pd(m - y + 1, m, 'R', 'L')) return prints("NO"), 0;
	prints("YES");
	return 0;
}

Removing Coins

考虑直径，设直径包含的点数为 dd，若 d≥3d \ge 3，则每次操作可以把 dd 减去 11 或 22，否则只能把 dd 减 11。

于是变成一个经典的博弈论问题，当一开始 d≡2(mod3)d \equiv 2 \pmod 3 时后手胜，否则先手胜。

const int N = 2e5 + 7;
int n, d[N];
vi e[N];

void dfs(int x, int f) {
	for (int y : e[x])
		if (y != f) d[y] = d[x] + 1, dfs(y, x);
}

int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	d[1] = 1, dfs(1, 0);
	int rt = max_element(d + 1, d + n + 1) - d;
	d[rt] = 1, dfs(rt, 0);
	int ans = *max_element(d + 1, d + n + 1);
	prints(ans % 3 == 2 ? "Second" : "First");
	return 0;
}

Complexity

题意

  • 给定一个 nn 行 mm 列的字符矩阵，每个位置上要么为 . 要么为 #。
  • 定义一个字符矩阵的凌乱度为：
    • 若所有字符都相同，则凌乱度为 00。
    • 否则，考虑所有的沿水平或者竖直方向的直线，将字符矩阵分成两个不为空的部分，设两个部分的凌乱度分别为 aa 和 bb，则凌乱度为 max⁡(a,b)+1\max(a,b)+1 的最小值。
  • 要求给定的字符矩阵的凌乱度是多少。
  • n,m≤185n,m \leq 185。

题解

一个显而易见的 DP 是，将每个子矩阵当作一个状态，枚举直线转移，时间复杂度 O(n5)\mathcal O(n^5)。

注意到凌乱度的最大值是 O(log⁡n)\mathcal O(\log n) 的，于是设 fi,u,d,lf_{i,u,d,l} 表示 (u,d,l)(u,d,l) 的情况下凌乱度为 ii 的最大 rr，同理 gi,u,l,rg_{i,u,l,r} 表示 (u,l,r)(u,l,r) 的情况下凌乱度为 ii 的最大 dd。

此时转移可以双指针，时间复杂度 O(n3log⁡n)\mathcal O(n^3\log n)，注意滚动数组优化空间。

代码

const int N = 187;
int n, m, w;
char a[N][N];
int f[N][N][N], g[N][N][N], F[N], G[N];

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++) rds(a[i], m);
	int tn = n - 1, tm = m - 1;
	while (tn) ++w, tn >>= 1;
	while (tm) ++w, tm >>= 1;
	for (int l = 1; l <= n; l++)
		for (int r = l; r <= n; r++) {
			f[l][r][m+1] = m;
			for (int j = m; j; j--)
				if (!(l == r || (a[l][j] == a[r][j] && f[l][r-1][j] >= j))) f[l][r][j] = j - 1;
				else f[l][r][j] = a[l][j] == a[l][j+1] ? f[l][r][j+1] : j;
		}
	for (int l = 1; l <= m; l++)
		for (int r = l; r <= m; r++) {
			g[l][r][n+1] = n;
			for (int i = n; i; i--)
				if (!(l == r || (a[i][l] == a[i][r] && g[l][r-1][i] >= i))) g[l][r][i] = i - 1;
				else g[l][r][i] = a[i][l] == a[i+1][l] ? g[l][r][i+1] : i;
		}
	if (f[1][n][1] == m) return print(0), 0;
	for (int k = 1; k <= w; k++) {
		for (int l = 1; l <= n; l++)
			for (int r = l; r <= n; r++)
				for (int j = 1; j <= m; j++)
					f[l][r][j] = f[l][r][f[l][r][j]+1];
		for (int l = 1; l <= m; l++)
			for (int r = l; r <= m; r++)
				for (int i = 1; i <= n; i++)
					g[l][r][i] = g[l][r][g[l][r][i]+1];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				for (int p = i; p <= n; p++) F[p] = f[i][p][j];
				for (int p = j; p <= m; p++) G[p] = g[j][p][i];
				F[n+1] = j - 1, G[m+1] = i - 1;
				for (int p = i; p <= n; p++)
					for (int w = F[p]; w > F[p+1]; w--)
						g[j][w][i] = max(g[j][w][i], p);
				for (int p = j; p <= m; p++)
					for (int w = G[p]; w > G[p+1]; w--)
						f[i][w][j] = max(f[i][w][j], p);
			}
		if (f[1][n][1] == m) return print(k), 0;
	}
	return 0;
}

Go around a Circle

题意

  • 有一个圆被 nn 个点分成了等长的 nn 段，每段的颜色为 R 或者 B。注意，染色方案旋转不同构。
  • 给定一个长度为 mm 的只包含 R 和 B 的字符串 ss，求出有多少种染色方案，满足将棋子放在任意一个点上，都存在一种进行 mm 次操作的方案，每次操作选择将棋子顺时针或逆时针移动一段，使得经过的第 ii 段为 sis_i。
  • n,m≤2×105n,m \le 2 \times 10^5，答案对 109+710^9+7 取模。

题解

不妨设 s1s_1 为 R，若不是则交换 R 和 B，那么圆上显然不存在连续两段为 B。

若 ss 中没有 B，则问题等价于圆上不存在两个连续的 B 的方案数，直接 DP 即可，接下来不考虑这种情况。

由于不存在连续两段为 B，因此我们可以当作圆上若干个非空 R 段被 B 隔开。

记 ss 中每一个极大的相同字符段长度为 c1…kc_{1\dots k}，我们容易得到若干条件：

  1. 圆上每一个 R 段的长度都为奇数。
  2. 圆上每一个 R 段的长度都不超过 c1+1c_1 + 1。
  3. 若 kk 为奇数，即 ss 中最后一段为 R，则可以将 ss 中的这一段直接去掉，也就是直接将 kk 减 11。
  4. 对于 i∈[2,k]i \in [2,k] 且 ii 为奇数，若 cic_i 为奇数，则圆上每一个 R 段的长度都不超过 cic_i。

可以证明这些条件为充要条件。

于是问题变成每一段的长度为奇数且不超过一个定值，可以使用前缀和优化 DP 解决，时间复杂度 O(n)\mathcal O(n)。

代码

const int N = 2e5 + 7;
int n, m, c[N], k, w;
char s[N];

namespace k1 {
	modint f[N][2][2];
	inline void main() {
		f[1][0][0] = f[1][1][1] = 1;
		for (int i = 1; i < n; i++)
			f[i+1][0][0] = f[i][0][0] + f[i][0][1],
			f[i+1][0][1] = f[i][0][0],
			f[i+1][1][0] = f[i][1][0] + f[i][1][1],
			f[i+1][1][1] = f[i][1][0];
		print(f[n][0][0] + f[n][0][1] + f[n][1][0]);
	}
}

modint f[N], g[N], ans;

int main() {
	rd(n, m), rds(s, m);
	for (int l = 1, r = 1; l <= m; l = ++r) {
		while (r < m && s[r+1] == s[l]) ++r;
		c[++k] = r - l + 1;
	}
	if (k == 1) return k1::main(), 0;
	if (n & 1) return print(0), 0;
	w = c[1] + !(c[1] & 1), k -= k & 1;
	for (int i = 3; i <= k; i += 2)
		if (c[i] & 1) w = min(w, c[i]);
	n >>= 1, w >>= 1;
	f[1] = g[1] = 1;
	for (int i = 2; i <= n; i++)
		g[i] = g[i-1] + (f[i] = g[i-1] - (i - w - 2 >= 0 ? g[i-w-2] : 0));
	for (int i = 0; i <= min(n, w); i++) ans += f[n-i] * (i + 1);
	print(ans + ans);
	return 0;
}

Adding Edges

题意

  • 给定一棵 nn 个点的树 TT 和一张 nn 个点 mm 条边的无向图 GG。
  • 每次可以选择三个满足下列条件的整数 a,b,ca,b,c，在 GG 中添加边 (a,c)(a,c)：
    • GG 中存在边 (a,b)(a,b) 和 (b,c)(b,c)，但不存在边 (a,c)(a,c)。
    • TT 中存在一条简单路径以某种顺序包含了 a,b,ca,b,c。
  • 求最终 GG 中的边数。
  • n,m≤2×103n,m \le 2 \times 10^3。

题解

考虑压缩 GG，如果存在 (a,b),(a,c)(a,b),(a,c) 且在 TT 中存在一条路径顺次包含 a,b,ca,b,c，那么删除 (a,c)(a,c) 加上 (b,c)(b,c) 不改变答案。

对 GG 进行充分压缩后，有结论：最终 (x,y)(x,y) 有边当且仅当存在 a1,a2,⋯ ,ata_1,a_2,\cdots,a_t 满足：

  • a1=xa_1 = x，at=ya_t = y。
  • GG 中存在边 (ai,ai+1)(a_i,a_{i+1})。
  • TT 中存在一条路径顺次包含 a1,a2,⋯ ,ata_1,a_2,\cdots,a_t。

这个就很好统计了，考虑如何压缩 GG。

对于一条加边 (a,b)(a,b)，记 p(a,b)p(a,b) 表示在 TT 中以 aa 为根离 bb 最近且在 GG 中与 bb 相连的祖先，若 p(a,b)p(a,b) 存在，则应该直接加 (b,p(a,b))(b,p(a,b))，否则将 bb 子树打上标记，碰到边时压缩即可。

时间复杂度 O(n(n+m))\mathcal O(n(n+m))。

代码

const int N = 2e3 + 7;
int n, m, ans;
vi e[N];
int f[N][N], p[N][N];
bool g[N][N];

void dfs(int x, int *f) {
	for (int y : e[x])
		if (y != f[x]) f[y] = x, dfs(y, f);
}

inline void add(int x, int y) {
	if (p[x][y] == y || p[y][x] == x) return;
	if (p[x][y]) return add(p[x][y], y);
	if (p[y][x]) return add(p[y][x], x);
	vector<pi> a;
	for (int i = 0; i < 2; i++) {
		g[x][y] = 1, p[x][y] = y;
		queue<int> q;
		q.push(y);
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int v : e[u])
				if (v != f[x][u]) {
					if (!p[x][v]) p[x][v] = y, q.push(v);
					else if (g[x][v]) g[x][v] = g[v][x] = 0, a.pb(mp(y, v));
				}
		}
		swap(x, y);
	}
	for (pi o : a) add(o.fi, o.se);
}

void dfs1(int x, int t, int *f) {
	if (p[t][x] == x) ++ans, t = x;
	for (int y : e[x])
		if (y != f[x]) dfs1(y, t, f);
}

int main() {
	rd(n, m);
	for (int i = 1, x, y; i < n; i++) rd(x, y), e[x].pb(y), e[y].pb(x);
	for (int x = 1; x <= n; x++) dfs(x, f[x]);
	for (int i = 1, x, y; i <= m; i++) rd(x, y), add(x, y);
	for (int x = 1; x <= n; x++)
		for (int y : e[x]) dfs1(y, x, f[x]);
	print(ans >> 1);
	return 0;
}

标签：DP、Two Pointers、前缀和/差分、博弈论、组合计数、贪心

评论

    填写昵称即可留言。评论经站主审核后公开，请勿提交私人信息。

    正在连接评论服务…