AtCoder Grand Contest 023 题解

作者: xht37 分类: 题解 发布时间: 2020-07-18 01:52

点击数:71

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注