AtCoder Grand Contest 028 题解

AtCoder Grand Contest 028

Two Abbreviations

答案显然要么为 $-1$ 要么为 $\text{lcm}(n,m)$ ，判一下就好了。

const int N = 1e5 + 7;
int n, m, d;
char a[N], b[N];

int main() {
	rd(n, m), d = __gcd(n, m);
	rds(a, n), rds(b, m);
	int s = n / d, t = m / d;
	for (int i = 1, j = 1; i <= n; i += s, j += t)
		if (a[i] != b[j]) return print(-1), 0;
	print(1ll * n * m / d);
	return 0;
}

Removing Blocks

考虑两个数 $i,j$ ，不妨设 $i<j$ ，则在删 $i$ 时 $j$ 有贡献当且仅当 $i$ 比 $[i+1,j]$ 先删，方案数为 $\frac{n!}{j-i+1}$ 。

对 $\frac{n!}{i}$ 做前缀和，枚举 $j$ 计算贡献，时间复杂度 $\mathcal O(n)$ 。

const int N = 1e5 + 7;
int n, a[N];
modint s[N], ans;

int main() {
	rd(n), rda(a, n), init(n);
	for (int i = 1; i <= n; i++) s[i] = p[n] * v[i] + s[i-1];
	for (int i = 1; i <= n; i++)
		ans += a[i] * (s[i] + s[n-i+1] - s[1]);
	print(ans);
	return 0;
}

Min Cost Cycle

题意

有一张 $n$ 个点的有向完全图。
每个点 $i$ 有两个权值 $a_i,b_i$ ，对于两个点 $x,y$ ，边 $x \to y$ 的长度为 $\min(a_x,b_y)$ 。
考虑图中经过每个点恰好一次的有向环，求出其中的最短路径长。
$n \le 10^5$ 。

题解

换个角度考虑，相当于要从 $2n$ 个数中选择 $n$ 个数，使其可以连成一个环，环中每条边前一个 $a$ 和后一个 $b$ 中选择恰好一个。

可行的方案有三种：

全选 $a$ ，合法性显然，不证。
全选 $b$ ，合法性显然，不证。
至少有一个 $i$ 满足 $a_i,b_i$ 都被选了。

第三种的合法性证明如下：

显然每个数只有四种状态，我们将其看成 $00,01,10,11$ 四种，那么条件就是至少有一个 $11$ 。
因为 $1$ 的总数为 $n$ ，所以 $11$ 和 $00$ 的数量相等，将它们交替放（ $00 \sim 11 \sim 00 \sim 11 \sim\cdots$ ）。
将所有 $01$ 和 $10$ 首尾相连变成一个 $01$ 一个 $10$ ，然后随便插到 $00 \sim 11$ 的环中合法的位置即可。

而除了这三种方案，剩下的情况的不合法性也很显然。

于是用 set 维护前 $n$ 小的数，然后枚举 $a_i,b_i$ 都被选的 $i$ ，可以 $\mathcal O(\log n)$ 得到答案。

总时间复杂度 $\mathcal O(n \log n)$ 。

代码

const int N = 1e5 + 7;
int n, a[N], b[N];
ll sa, sb, sum, ans;
set<pi> s;
bool v[N], w[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++)
		rd(a[i], b[i]), sa += a[i], sb += b[i], 
		s.insert(mp(a[i], i)), s.insert(mp(b[i], -i));
	ans = min(sa, sb), sum = sa + sb;
	while ((int)s.size() > n)
		sum -= (--s.end()) -> fi, s.erase(--s.end());
	for (pi o : s)
		if (o.se > 0) v[o.se] = 1;
		else w[-o.se] = 1;
	for (int i = 1; i <= n; i++)
		if (v[i]) {
			if (w[i]) ans = min(ans, sum);
			else {
				auto it = --s.end();
				while (it -> se == i) --it;
				ans = min(ans, sum + b[i] - (it -> fi));
			}
		} else {
			if (w[i]) {
				auto it = --s.end();
				while (it -> se == -i) --it;
				ans = min(ans, sum + a[i] - (it -> fi));
			} else {
				auto it1 = --s.end(), it2 = --(--s.end());
				ans = min(ans, sum + a[i] + b[i] - (it1 -> fi) - (it2 -> fi));
			}
		}
	print(ans);
	return 0;
}

Chords

题意

一个圆上均匀分布着 $2n$ 个点。
你要把这些点分成 $n$ 对，每对的两点之间连接一条线。
其中有 $k$ 对点已经确定了，你要求出每种方案通过连线连通的块数。
$n \le 300$ ，答案对 $10^9 + 7$ 取模。

题解

首先断环成链，圆上的一个连通块在链上等价于一个区间，满足整个连通块都在这个区间内，且区间的两端点都属于这个连通块，但是注意并不要求整个区间都属于这个连通块，因为其中可能还有小连通块。

令 $f_{i,j}$ 表示 $[i,j]$ 为上述连通块对应的区间的方案数。

如果任意连边，方案数为 $g_{c_{i,j}}$ ，其中 $c_{i,j}$ 表示 $[i,j]$ 内还没确定连边的点数， $g_x$ 表示将 $x$ 个点两两连边的方案数，有 $g_x = [x \bmod 2 = 0](x-1)!!$ ，特别地 $g_0 = 1$ 。

但是还要求 $i,j$ 都属于这个连通块，考虑容斥，枚举跟 $i$ 在同一个连通块的右端点 $k$ ，有： $f_{i,j} = g_{c_{i,j}} - \sum_{k=i}^{j-1} f_{i,k}g_{c_{k+1,j}}$ 最终的答案为 $\sum_{i,j} f_{i,j}g_{2(n-k)-c_{i,j}}$ 。

代码

const int N = 607;
int n, k, p[N], c[N];
modint f[N][N], g[N], ans;
bool v[N][N];

inline int C(int i, int j) {
	return j - i + 1 - c[j] + c[i-1];
}

inline modint F(int i, int j) {
	if (v[i][j]) return f[i][j];
	v[i][j] = 1;
	if (((j - i + 1) & 1) || (C(i, j) & 1)) return 0;
	for (int k = i; k <= j; k++)
		if (p[k] && (p[k] < i || p[k] > j)) return 0;
	f[i][j] = g[C(i,j)];
	for (int k = i; k < j; k++)
		f[i][j] -= F(i, k) * g[C(k+1,j)];
	return f[i][j];
}

int main() {
	rd(n, k);
	for (int i = 1, x, y; i <= k; i++)
		rd(x, y), p[x] = y, p[y] = x, c[x] = 1, c[y] = 1;
	for (int i = 1; i <= n << 1; i++) c[i] += c[i-1];
	g[0] = 1;
	for (int i = 2; i <= n << 1; i++)
		g[i] = g[i-2] * (i - 1);
	for (int i = 1; i <= n << 1; i++)
		for (int j = i; j <= n << 1; j++)
			ans += F(i, j) * g[2*(n-k)-C(i,j)];
	print(ans);
	return 0;
}

High Elements

题意

给定一个 $1 \sim n$ 的排列 $p$ 。
求出字典序最小的满足下列条件的 $0/1$ 串 $s_{1\dots n}$ ，或判断不存在：
- 一开始有两个空序列 $x,y$ 。
- 依次考虑 $i \in [1,n]$ ，若 $s_i$ 为 0 则将 $p_i$ 加入 $x$ 末尾，否则加入 $y$ 末尾。
- $x,y$ 中为前缀 $\max$ 的位置数量相同。
$n \le 2\times 10^5$ 。

题解

看到字典序显然贪心，现在前 $i-1$ 位已经确定，考虑第 $i$ 位，先假设为 0，如果不合法则改成 1。接下来的问题就是如何判断是否合法。

首先可以证明，如果存在合法的 $s$ ，必然可以使得 $x,y$ 两个数列中，有一个数列的前缀 $\max$ 都是 $p$ 中的前缀 $\max$ 。这是因为如果不是，交换两个不是 $p$ 中前缀 $\max$ 的前缀 $\max$ 可以把这两个前缀 $\max$ 都消掉。

不妨假设 $x$ 中的前缀 $\max$ 都由 $p$ 的前缀 $\max$ 构成，令 $x,y$ 当前的前缀 $\max$ 个数为 $c_x,c_y$ ， $p_{i\dots n}$ 中前缀 $\max$ 个数为 $c_p$ 。设 $y$ 中将会有 $k$ 个前缀 $\max$ 也是 $p$ 的前缀 $\max$ ，则 $x$ 中会有 $c_p - k$ 个。再设 $y$ 中不是 $p$ 的前缀 $\max$ 的前缀 $\max$ 个数为 $m$ ，我们能得到等式： $c_x + c_p - k = c_y + k + m$ 即： $2k+m = c_p+c_x-c_y$ 其中右边是常量，设为 $c$ 。

由于在 $x>0$ 或 $y>1$ 时可以从 $2k+m$ 的方案构造出减少 $2$ 的方案，因此若满足存在 $2k+m \ge c$ 且 $2k+m \equiv c \pmod 2$ ，就存在合法解。

考虑 $2k+m$ ，相当于我们把 $p$ 中的前缀 $\max$ 的权值设为 $2$ ，其它位置的权值设为 $1$ 后的带权最长上升子序列长度。

于是用权值线段树维护单点修改和区间求 $\max$ ，求出 $f_{i,0/1}$ 从 $i$ 开始长度为偶/奇数的带权最长上升子序列的长度，判断时用类似的操作求出 $2k + m$ 在偶/奇数下的最大值即可。

由于我们的贪心策略默认了有解，所以最后如果 $cx \ne cy$ 则说明无解。

时间复杂度 $\mathcal O(n\log n)$ 。

代码

const int N = 2e5 + 7, inf = 1e9;
int n, p[N], c[N], cx, cy;
bool v[N];
char s[N];

struct SGT {
	struct T {
		int l, r, x;
	} t[N<<2|1];

	inline void update(int p) {
		t[p].x = max(t[ls].x, t[rs].x);
	}

	void build(int p, int l, int r, int x) {
		t[p].l = l, t[p].r = r;
		if (l == r) return t[p].x = x, void();
		build(ls, l, md, x), build(rs, md + 1, r, x);
		update(p);
	}

	void add(int p, int x, int k) {
		if (t[p].l == t[p].r) return t[p].x = k, void();
		if (x <= md) add(ls, x, k);
		if (x > md) add(rs, x, k);
		update(p);
	}

	int ask(int p, int l, int r) {
		if (t[p].l >= l && t[p].r <= r) return t[p].x;
		int ret = -inf;
		if (l <= md) ret = max(ret, ask(ls, l, r));
		if (r > md) ret = max(ret, ask(rs, l, r));
		return ret;
	}
} t[2];

inline bool pd(int x, int k) {
	return k < 0 ? 0 : t[k&1].ask(1, x, n) >= k;
}

int main() {
	rd(n), rda(p, n);
	for (int i = 1, x = 0; i <= n; i++)
		if (p[i] > x) x = p[i];
		else v[i] = 1;
	t[0].build(1, 1, n, 0), t[1].build(1, 1, n, -inf);
	for (int i = n; i; i--) {
		int x0 = t[0].ask(1, p[i], n), x1 = t[1].ask(1, p[i], n);
		t[0].add(1, p[i], (v[i] ? x1 + 1 : x0 + 2));
		t[1].add(1, p[i], (v[i] ? x0 + 1 : x1 + 2));
		c[i] = c[i+1] + !v[i];
	}
	for (int i = 1, x = 0, y = 0; i <= n; i++) {
		t[0].add(1, p[i], 0), t[1].add(1, p[i], -inf);
		if (pd(y, c[i+1] + cx - cy + (p[i] > x)) || pd(max(x, p[i]), c[i+1] + cy - cx - (p[i] > x)))
			s[i] = '0', cx += p[i] > x, x = max(x, p[i]);
		else s[i] = '1', cy += p[i] > y, y = max(y, p[i]);
	}
	if (cx == cy) prints(s, n);
	else print(-1);
	return 0;
}

Reachable Cells

题意

给定一个 $n \times n$ 的网格，每个位置上要么是障碍，要么写有一个 $[1,9]$ 的数。
我们称位置 $x$ 可以到达位置 $y$ 当且仅当：
- $x \ne y$ 。
- $x,y$ 都不是障碍。
- 存在一条从 $x$ 到 $y$ 的路径，满足只经过不是障碍的格子，同时每次只向下或者向右走到相邻的格子。
对于二元组 $(x,y)$ ，若 $x$ 可以到达 $y$ ，则 $(x,y)$ 合法且权值为 $x,y$ 上写的数的乘积。
要求所有合法二元组的权值之和。
$n \le 1.5 \times 10^3$ 。

题解

考虑从大到小枚举位置 $(i,j)$ 求出能到达的点的权值和 $s_{i,j}$ 。

如果 $(i,j+1)$ 和 $(i+1,j)$ 中至多一个不是障碍则很简单，否则直接加 $s_{i+1,j}$ 和 $s_{i,j+1}$ 会算重，要减掉两个点都可达的。

设 $l_{i,j,k},r_{i,j,k}$ 表示 $(i,j)$ 能到达的点在第 $k$ 行列数的最小值和最大值，显然对于 $(i,j+1)$ 和 $(i+1,j)$ 都能到达的行 $k$ 有 $l_{i+1,j,k} \le l_{i,j+1,k}$ ， $r_{i+1,j,k} \le r_{i,j+1,k}$ 。

注意到如果第 $k$ 行有 $(i,j+1)$ 和 $(i+1,j)$ 都能到达的点，那么必然包括 $(k,l_{i,j+1,k})$ ，且 $(i,j+1)$ 和 $(i+1,j)$ 都能到达的点恰好为若干个 $(k,l_{i,j+1,k})$ 能到达的点的并集，使这些点集不交。

于是可以 $\mathcal O(n^3)$ 计算，常数很小可以通过，注意滚动数组防止炸空间。

代码

const int N = 1.5e3 + 7;
int n, s[N][N], p[N][N], l[2][N][N], r[2][N][N];
char a[N][N];
ll ans;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rds(a[i], n);
	for (int i = n, o = 0; i; i--, o ^= 1)
		for (int j = n; j > 0; j--)
			if (a[i][j] != '#') {
				a[i][j] -= '0';
				s[i][j] = s[i][j+1] + s[i+1][j] + a[i][j];
				p[i][j] = max(max(p[i][j+1], p[i+1][j]), i);
				l[o][j][i] = j;
				for (int k = i + 1; k <= p[i+1][j]; k++)
					l[o][j][k] = l[o^1][j][k];
				for (int k = max(p[i+1][j], i) + 1; k <= p[i][j+1]; k++)
					l[o][j][k] = l[o][j+1][k];
				r[o][j][i] = j;
				for (int k = i; k <= p[i][j+1]; k++)
					r[o][j][k] = r[o][j+1][k];
				for (int k = max(p[i][j+1], i) + 1; k <= p[i+1][j]; k++)
					r[o][j][k] = r[o^1][j][k];
				for (int k = i + 1; k <= min(p[i][j+1], p[i+1][j]); k++)
					if (r[o^1][j][k] >= l[o][j+1][k])
						s[i][j] -= s[k][l[o][j+1][k]],
						k = p[k][l[o][j+1][k]];
				ans += 1ll * a[i][j] * (s[i][j] - a[i][j]);
			}
	print(ans);
	return 0;
}