AtCoder Grand Contest 023 题解
Visits: 585
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;
}
