Visits: 371

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$ 中选择恰好一个。

可行的方案有三种：

1. 全选 $a$，合法性显然，不证。
2. 全选 $b$，合法性显然，不证。
3. 至少有一个 $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;
}