AtCoder Grand Contest 023 题解

AtCoder Grand Contest 023

Zero-Sum Ranges

前缀和一下直接计数即可。

const int N = 2e5 + 7;
int n, a[N];
ll s, ans;

int main() {
	rd(n), rda(a, n);
	map<ll, int> c;
	for (int i = 1; i <= n; i++)
		c[s]++, s += a[i], ans += c[s];
	print(ans);
	return 0;
}

Find Symmetries

条件其实就是斜线上要回文。

预处理每个中心的最长回文串的长度，然后直接枚举判断即可。

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

const int N = 607;
int n, f[N][N], g[N][N], ans;
char s[N][N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rds(s[i], n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			s[i][j+n] = s[i+n][j] = s[i+n][j+n] = s[i][j];
	for (int i = 1; i <= n * 2; i++)
		for (int j = 1; j <= n * 2; j++) {
			int k = min(min(i, j), min(n * 2 + 1 - i, n * 2 + 1 - j));
			int &x = f[i][j] = 1;
			while (x < k && s[i+x][j-x] == s[i-x][j+x]) ++x;
		}
	for (int i = 1; i < n * 2; i++)
		for (int j = 1; j < n * 2; j++) {
			int k = min(min(i, j), min(n * 2 - i, n * 2 - j));
			int &x = g[i][j] = 0;
			while (x < k && s[i+x+1][j-x] == s[i-x][j+x+1]) ++x;
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			bool ok = 1;
			for (int k = 0; ok && k < n; k++)
				ok &= (k / 2 + 1 <= (k & 1 ? g[i+k/2][j+k/2] : f[i+k/2][j+k/2])),
				ok &= (k / 2 + 1 <= (k & 1 ? g[i+n-2-k/2][j+n-2-k/2] : f[i+n-1-k/2][j+n-1-k/2]));
			ans += ok;
		}
	print(ans);
	return 0;
}

Painting Machines

合法的前缀需要满足选择的位置间隔不超过 $1$ 且头尾都选。

因此前 $i$ 个数合法的排列数为 $\binom {i-1}{n-1-i}i!(n-1-i)!$，也就是 $i$ 个被选的位置的 $i-1$ 个间隔中选 $n-1-i$ 个没被选的位置，然后乘上阶乘数。

但是前 $i$ 个数合法的排列都包含在前 $i+1$ 个数合法的排列中，因此差分一下就是每种权值出现的次数。

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

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

Go Home

题意

• 数轴上有 $n$ 个房子，第 $i$ 个房子的坐标为 $x_i$。里面住了 $p_i$ 个人。一开始所有人都在 $s$ 处，他们会乘坐一辆大巴回家，大巴一秒行驶一个单位。
• 大巴一开始也在 $s$ 处，车上的所有人会投票决定大巴下一秒的移动方向，如果正负方向票数相同，则往负方向移动。
• 每个人每次投票可以投一票，他会投给能让他更早回家的方向（不一定是他的房子相对大巴所在的方向），如果两个方向会同时到家，他会投给负方向。
• 每当到达一个房子的位置，所有住在这个房子里的人会下车。你要求出当最后一个人下车时大巴运行了多少秒。
• $n \le 10^5$，$s,x_i,p_i \le 10^9$。

题解

如果 $s < x_1$ 或 $x_n < s$，答案显然。

否则，若 $p_1 \ge p_n$，考虑大巴在 $x_n -1$ 时的投票情况可知，大巴一定会在去 $x_n$ 之前去 $x_1$。因此第 $n$ 个房子里的人的回家时间，等于第 $1$ 个房子里的人的回家时间 $+(x_n - x_1)$。于是，第 $n$ 个房子里的人也希望第 $1$ 个房子里的人尽快回家，这意味着他们的投票是一致的。

所以，让 $p_1$ 加上 $p_n$ 然后删去第 $n$ 个房子后，这个子问题下到达 $x_1$ 的时间 $+(x_n - x_1)$ 就是答案。

如果 $p_1 < p_n$，将上述结论反过来是类似的。

于是可以递归下去求，时间复杂度 $\mathcal O(n)$。

代码

const int N = 1e5 + 7;
int n;
ll s, x[N], p[N];

ll f(int l, int r, int o) {
	if (s < x[l] || x[r] < s) return abs(s - x[o]);
	if (p[l] >= p[r]) return p[l] += p[r], f(l, r - 1, l) + abs(x[l] - x[o]);
	return p[r] += p[l], f(l + 1, r, r) + abs(x[r] - x[o]);
}

int main() {
	rd(n), rd(s);
	for (int i = 1; i <= n; i++) rd(x[i], p[i]);
	print(f(1, n, s < x[1] ? n : x[n] < s ? 1 : p[1] >= p[n] ? n : 1));
	return 0;
}

Inversions

题意

• 给定 $a_{1\dots n}$，求出所有满足 $p_i \le a_i$ 的 $1\sim n$ 的排列 $p$ 的逆序对数之和。
• $n \le 2 \times 10^5$，答案对 $10^9+7$ 取模。

题解

首先考虑如何计算排列 $p$ 的个数。

一个经典的做法是对 $a$ 排序后答案就是 $\prod_{i=1}^n (a_i - i + 1)$。

另一种思路是设 $c_i$ 表示 $a_{k} \ge i$ 的个数，那么答案就是 $\prod_{i=1}^n (c_i - (n - i))$。

考虑枚举 $i,j(i<j)$ 求出 $i,j$ 之间形成逆序对的方案数。

分类讨论：

• $a_i = a_j$。
  从概率的角度考虑，$p_i < p_j$ 和 $p_i > p_j$ 的概率是一样的，所以方案数就是总数除以 $2$。
• $a_i < a_j$。
  当 $p_j \in [a_i + 1, a_j]$ 时没有贡献，因此将 $a_j$ 变成 $a_i$ 后方案数也是总数除以 $2$。
  $a_j$ 变成 $a_i$ 在 $c$ 上的体现就是 $[a_i+1,a_j]$ 这一段全部 $-1$。
• $a_i > a_j$。
  用总方案数减去 $p_i < p_j$ 的方案数，同理 $a_i < a_j$，将 $a_i$ 变成 $a_j$。

时间复杂度 $\mathcal O(n^2)$，不可接受。

考虑优化，记 $d_i = \frac {c_i - 1 - (n-i)}{c_i - (n-i)}$，则维护前缀积然后求和即可，树状数组实现时间复杂度 $\mathcal O(n \log n)$。

注意 $d_i$ 可能为 $0$，分段计算贡献即可。

代码

const int N = 2e5 + 7;
const modint v2 = (modint)1 / 2;
int n, a[N], c[N], s0[N], p0[N];
modint d[N], vd[N], c1[N], c2[N], tot = 1, ans;

inline void add(int x, modint w) {
	while (x <= n) c1[x] += w, c2[x] += 1, x += x & -x;
}

inline modint ask(modint *c, int x) {
	modint ret = 0;
	while (x) ret += c[x], x -= x & -x;
	return ret;
}

int main() {
	rd(n), rda(a, n);
	for (int i = 1; i <= n; i++) ++c[a[i]];
	for (int i = n - 1; i; i--) c[i] += c[i+1];
	for (int i = 1; i <= n; i++) tot *= c[i] -= n - i;
	if (!tot) return print(0), 0;
	p0[0] = 1, d[0] = 1;
	for (int i = 1; i <= n; i++) {
		modint x = (modint)(c[i] - 1) / c[i];
		if (!x) s0[i] = s0[i-1] + 1, p0[s0[i]] = i, d[i] = d[i-1];
		else s0[i] = s0[i-1], d[i] = d[i-1] * x;
		vd[i] = 1 / d[i];
	}
	for (int i = 1; i <= n; i++)
		ans += (ask(c1, a[i]) - ask(c1, p0[s0[a[i]]] - 1)) * d[a[i]] * tot * v2, add(a[i], vd[a[i]]);
	for (int i = 1; i <= n; ++i) c1[i] = c2[i] = 0;
	for (int i = n; i; i--)
		ans += ask(c2, a[i] - 1) * tot - (ask(c1, a[i] - 1) - ask(c1, p0[s0[a[i]]] - 1)) * d[a[i]] * tot * v2, add(a[i], vd[a[i]]);
	print(ans.x);
	return 0;
}

01 on Tree

题意

• 给定一棵 $n$ 个节点的有根树，每个点上有一个 $0/1$ 的权值。
• 你要将这些节点排成一行，要求每个节点的右侧不存在它的祖先，在此基础上最小化逆序对数。
• $n \le 2 \times 10^5$。

题解

考虑一开始每个节点为单独一个点，然后依次向上合并。

设此时节点 $i$ 中的点集为 $s_i$，记 $a_i$ 为其中 $0$ 的个数，$b_i$ 为其中 $1$ 的个数。

那么每次将 $\frac {a_i}{b_i}$ 最大的合并到 $p_i$ 是最优的，考虑一下某个点的两个儿子哪个先合并的贡献小就可以证明了。

于是用 set 和并查集维护这个过程，每次合并将答案加上贡献即可，时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 2e5 + 7;
int n, p[N], v[N], a[N], b[N], f[N];
ll ans;

struct G {
	int x, y, i;
	inline G() {}
	inline G(int i) : x(a[i]), y(b[i]), i(i) {}
	inline bool operator < (G o) const {
		if (1ll * x * o.y == 1ll * o.x * y) return i < o.i;
		return 1ll * x * o.y < 1ll * o.x * y;
	}
};
set<G> s;

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

int main() {
	rd(n), rda(p + 1, n - 1), rda(v, n);
	for (int i = 1; i <= n; i++) v[i] ? ++b[i] : ++a[i];
	for (int i = 2; i <= n; i++) s.insert(G(i));
	iota(f + 1, f + n + 1, 1);
	while (s.size()) {
		int i = (--s.end()) -> i, x = get(p[i]);
		s.erase(G(i));
		ans += 1ll * b[x] * a[i];
		if (x != 1) s.erase(G(x));
		a[x] += a[i], b[x] += b[i], f[i] = x;
		if (x != 1) s.insert(G(x));
	}
	print(ans);
	return 0;
}