AtCoder Grand Contest 036 题解

作者: xht37 分类: 题解 发布时间: 2020-06-30 15:32

点击数:29

AtCoder Grand Contest 036

Triangle

考虑 $\triangle (0,0)(x,n)(n,y)$ 的面积为 $n^2 – xy$,找到最小的 $n$ 满足 $n^2 \ge S$,设 $k = n^2 – S$,有 $0 \le k \le 2n-1$。

若 $k < n$,则 $\triangle (0,0)(k,n)(n,1)$ 满足条件,否则 $\triangle (0,0)(k-n,n-1)(n,1)$ 满足条件。

注意可能会有精度误差,要简单调一下。

inline void out(ll x, ll y) {
    print(x, ' '), print(y, ' ');
}

int main() {
    ll s;
    rd(s);
    ll n = sqrt(s);
    while (n * n >= s) --n;
    while (n * n < s) ++n;
    ll k = n * n - s;
    if (k < n) out(0, 0), out(k, n), out(n, 1);
    else out(0, 0), out(k - n, n - 1), out(n, 1);
    return 0;
}

Do Not Duplicate

考虑对于每个 $i$ 求出以 $a_i$ 开始的情况下需要多少步会清空,清空后下一个填的数。

设步数为 $d_i$,填的数为 $t_i$,连一条 $(i,t_i,d_i)$ 的有向边,则会形成一个 $n$ 个点的基环内向边带权森林。

整个过程会从起点开始,走到环上之后,绕环若干圈,最后再走不到整环的一段。

模拟就好了,时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, a[N<<1|1], b[N<<1|1], t[N], d[N], p[N];
ll k, s[N];
bool v[N];

inline void work(int &o, ll &k, int ed = 0) {
    while (o != ed && k >= d[o])
        k -= d[o], o = t[o];
}

int main() {
    rd(n), rd(k), k *= n;
    rda(a, n);
    for (int i = 1; i <= n; i++) a[i+n] = a[i];
    for (int i = n << 1; i; i--) b[i] = p[a[i]], p[a[i]] = i;
    for (int i = 1; i <= n; i++)
        t[i] = b[i] % n + 1, d[i] = b[i] - i + 1;
    int o = 1;
    v[o] = 1;
    while (!v[t[o]]) {
        v[t[o]] = 1;
        s[t[o]] = s[o] + d[o];
        o = t[o];
    }
    ll g = s[o] + d[o] - s[t[o]];
    int x = t[o];
    o = 1;
    work(o, k, x);
    k %= g;
    work(o, k);
    for (int i = 1; i <= n; i++) v[i] = 0;
    vi ans;
    while (k--) {
        if (o == n + 1) o = n;
        int w = a[o++];
        if (v[w]) while (v[w]) v[ans.back()] = 0, ans.pop_back();
        else ans.pb(w), v[w] = 1;
    }
    for (int x : ans) print(x, ' ');
    return 0;
}

GP 2

满足条件的序列等价于(从 $1$ 开始编号):

  • $a_i \le 2m$。
  • $\sum_{i=1}^n a_i = 3m$。
  • $\sum_{i=1}^n \lfloor \frac {a_i}2 \rfloor \ge m$。

枚举 $\sum_{i=1}^n \lfloor \frac {a_i}2 \rfloor$ 的值,剩下就是一个多重集组合数,容斥一下发现计算量是常数,时间复杂度 $\mathcal O(n)$。

int n, m;
modint ans;

int main() {
    rd(n, m), init(n + 3 * m / 2);
    for (int k = m; k <= 3 * m / 2; k++) {
        int b = 3 * m - 2 * k, a = n - b;
        if (a < 0 || b < 0) continue;
        ans += binom(n, a) * (binom(n + k - 1, n - 1) - a * binom(n + k - m - 2, n - 1) - b * binom(n + k - m - 1, n - 1));
    }
    print(ans);
    return 0;
}

Negative Cycle

题意

  • 有一张 $n$ 个点的有向图,点的编号为 $0 \sim n – 1$。
  • 一开始有 $n-1$ 条边,对于 $i\in [0,n-2]$,有边 $(i,i+1,0)$。
  • 另外若 $i<j$,加边 $(i,j,-1)$;若 $i>j$,加边 $(i,j,1)$。这些边都可以删除,边 $(i,j)$ 删除的代价为 $a_{i,j}$。
  • 你希望用最小的代价删除某些边,使得图中不存在负环。
  • $n \le 500$,$a_{i,j} \le 10^9$。

题解

考虑差分约束模型,图中不存在负环等价于存在一组合法的差分约束的解。

将每个节点作为一个变量,第 $i$ 个节点对应的变量为 $x_i$。因为初始的边不能删去,所以一定有 $x_i \ge x_{i + 1}$。

令 $q_i = x_i – x_{i + 1}$,有 $q_i \ge 0$。

假设保留了一条边权为 $-1$ 的 $i \to j(i < j)$ 的边,有 $x_i – 1 \ge x_j$,即 $x_i – x_j \ge 1$,即 $q_i + q_{i + 1} + \cdots + q_{j – 1} \ge 1$;假设保留了一条边权为 $1$ 的 $i \to j(i>j)$ 的边,有 $x_i + 1 \ge x_j$,即 $x_j – x_i \le 1$,即 $q_j + q_{j + 1} + \cdots + q_{i – 1} \le 1$。

反过来想,如果确定了所有的 $q_i$,那么每一条边就应该尽可能地保留下来,这样代价最小。

对于边权为 $-1$ 的边,是区间和 $\ge 1$ 才能保留,也就是说如果区间和 $= 0$ 就必须删除;对于边权为 $1$ 的边,是区间和 $\le 1$ 才能保留,也就是说如果区间和 $\ge 2$ 就必须删除。

也就是说,对于一种 $q$ 的取值方案,$q_i = 0$ 的每个连续段,都对应着一系列的边权为 $-1$ 的边的删除,而区间和 $\ge 2$ 的区间也对应着边权为 $1$ 的边的删除。

可以发现如果出现了 $q_i \ge 2$,不如把它变成 $1$,这样一定更优,所以只需要考虑 $q$ 的取值为 $0/1$ 的情况。

考虑 DP,设 $f_{i,j}$ 表示最后一个 $1$ 取在 $q_i$ 处,倒数第二个 $1$ 取在 $q_j$ 处的情况下,前缀 $i$ 的代价的最小值。

转移枚举下一个 $1$ 的位置即可,二维前缀和预处理转移系数后,时间复杂度 $\mathcal O(n^3)$。

代码

const int N = 507;
const ll inf = 1e18;
int n;
ll a[N][N], b[N][N], f[N][N], ans = inf;

inline ll calc(int k, int j, int i) {
    return b[j+1][i] + a[n][j] - a[n][k] - a[i][j] + a[i][k];
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j) rd(a[i][j]);
    for (int j = 1; j <= n; j++)
        for (int i = j; i; i--)
            b[i][j] = b[i+1][j] + b[i][j-1] - b[i+1][j-1] + a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    for (int i = 1; i < n; i++) {
        f[i][0] = calc(0, 0, i);
        ans = min(ans, f[i][0] + calc(0, i, n));
        for (int j = 1; j < i; j++) {
            f[i][j] = inf;
            for (int k = 0; k < j; k++)
                f[i][j] = min(f[i][j], f[j][k] + calc(k, j, i));
            ans = min(ans, f[i][j] + calc(j, i, n));
        }
    }
    print(ans);
    return 0;
}

ABC String

题意

  • 给定一个仅包含 ABC 的字符串 $s$。
  • 要求 $s$ 的一个最长子序列,满足 ABC 出现次数相同,且相邻字符不同。
  • $|s| \le 10^6$。

题解

考虑将 $s$ 中相邻的相同字符缩成一个,这显然不影响答案。

记 $s$ 中 A,B,C 的出现次数分别为 $c_A,c_B,c_C$,不妨设 $c_A \le c_B \le c_C$。

A 看作分隔符,则将当前串分成了 $c_A + 1$ 段,每段只有 B,c。记 B,C 都有的段数为 $c_1$,单个 B 的段数为 $c_2$,单个 C 的段数为 $c_3$,若 $c_1 + c_2 \ge c_3$,可以构造取到答案的上界 $3c_A$:

  1. 每次找到一个 C,满足删去它之后串内相邻字符依然不相同,删去它,直到 $c_B = c_C$。
  2. 每次找到相邻的 BC,满足删去它们之后串内相邻字符依然不相同,删去它们,直到 $c_A = c_B = c_C$。

若 $c_1 + c_2 < c_3$,每次找到单个 C 段,删去 C 以及 $0/1$ 个 A(优先考虑首尾,这样不用删 A),直到 $c_1+c_2 \ge c_3$,然后使用上面的构造方法即可。

使用链表维护,时间复杂度 $\mathcal O(n)$;使用 set 维护,时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 1e6 + 7;
int n, t[3];
char s[N], c[3];
set<int> p;

inline void del(int x, int c) {
    p.erase(x), --t[c];
}

int main() {
    rds(s, n);
    for (int i = 0; i < 3; i++) c[i] = 'A' + i;
    for (int i = 1; i <= n; i++)
        if (s[i] != s[i+1]) p.insert(i), ++t[s[i]-'A'];
    if (t[1] > t[2]) swap(t[1], t[2]), swap(c[1], c[2]);
    if (t[0] > t[1]) swap(t[0], t[1]), swap(c[0], c[1]);
    if (t[1] > t[2]) swap(t[1], t[2]), swap(c[1], c[2]);
    int c1 = 0, c2 = 0, c3 = 0, o1 = 0, o2 = 0;
    for (int x : p)
        if (s[x] == c[0]) {
            if (o1 && o2) ++c1;
            else if (o1) ++c2;
            else if (o2) ++c3;
            o1 = o2 = 0;
        } else if (s[x] == c[1]) o1 = 1;
        else o2 = 1;
    if (o1 && o2) ++c1;
    else if (o1) ++c2;
    else if (o2) ++c3;
    o1 = o2 = 0;
    if (c1 + c2 < c3) {
        if (s[*p.begin()] == c[2] && s[*++p.begin()] == c[0])
            del(*p.begin(), 2), --c3;
        if (c1 + c2 < c3) {
            if (s[*--p.end()] == c[2] && s[*--(--p.end())] == c[0])
                del(*--p.end(), 2), --c3;
            if (c1 + c2 < c3)
                for (int x : p)
                    if (s[x] == c[0]) {
                        if (o1 && o2) {
                            del(o1, 0), del(o2, 2);
                            o1 = x, o2 = 0;
                            if (c1 + c2 == --c3) break;
                        } else o1 = x, o2 = 0;
                    } else if (s[x] == c[1]) o1 = 0, o2 = 0;
                    else if (s[x] == c[2]) {
                        if (o1 && !o2) o2 = x;
                        else o1 = 0, o2 = 0;
                    }
        }
    }
    if (t[1] < t[2]) {
        auto it = p.begin();
        while (it != p.end()) {
            auto itl = it, itr = it;
            if (s[*it] != c[2] || !(it == p.begin() || ++itr == p.end() || s[*--itl] != s[*itr])) {
                ++it;
                continue;
            }
            del(*it++, 2);
            if (t[1] == t[2]) break;
        }
    }
    if (t[0] < t[1]) {
        auto it = p.begin();
        while (it != p.end()) {
            auto itl = it, itr = it, itrr = it;
            if (s[*it] == c[0] || ++itr == p.end() || s[*itr] == c[0] || s[*it] == s[*itr] || !(it == p.begin() || (itrr = itr, ++itrr) == p.end() || s[*--itl] != s[*itrr])) {
                ++it;
                continue;
            }
            int x = s[*it] == c[1] ? 1 : 2, y = x == 1 ? 2 : 1;
            del(*it++, x), del(*it++, y);
            if (t[0] == t[1]) break;
        }
    }
    for (int x : p) printc(s[x]);
    return 0;
}

Square Constraints

题意

  • 给定 $n$,求满足以下条件的 $0 \sim 2n-1$ 的排列 $p_{0\dots2n-1}$ 的个数。
    • 对于 $i \in [0,2n-1]$,满足 $n^2 \le i^2 + p_i^2 \le (2n)^2$。
  • $n \le 250$,答案对 $P$ 取模。

题解

本质上,这依然是一个 $p_i \in [l_i,r_i]$ 的计数问题。

在没有下界限制的情况下,我们有个经典的做法是,将 $r_i$ 从小到大排序,这样当考虑第 $i$ 个数时,由于前面的 $r$ 都 $\le r_i$,因此无论前面怎么填,第 $i$ 个数的方案数都为 $r_i + 1 – i$(编号从 $0$ 开始),总方案数为 $\prod_{i=0}^{2n-1} r_i + 1 – i$。

在有下界时,我们可以考虑容斥,设 $f(k)$ 表示至少有 $k$ 个数小于下界时的方案数,则答案为 $\sum_{k=0}^{2n} (-1)^kf(k)$。

回到本题,题意的约束条件比较奇怪,考虑将它变得直观一点就是:

  • 以原点为圆心在第一象限画两个半径分别为 $n,2n$ 的 $1/4$ 圆,对于 $i \in [0,2n-1]$,$(i,p_i)$ 必须在这两个 $1/4$ 圆之间(含圆上)。

于是我们有 $l_{n\dots2n-1} = 0$,因此只有对于 $i \in [0,n-1]$ 才有可能 $p_i < l_i$。

考虑枚举若干个 $i$ 要求 $p_i < l_i$,则此时相当于没有下界限制的计数,用上面的方法即可。

然而显然我们不能枚举每个 $i \in [0, n-1]$ 是否要求 $p_i < l_i$,有没有什么办法可以直接计算出 $f(k)$ 呢?

注意到对 $r$ 排序后求 $\prod_{i=0}^{2n-1} r_i + 1 – i$,本质上相当于对于每个 $i$,其贡献为,$\le r_i$ 的数的个数($r_i+1$ 个),减去比 $r_i$ 小的限制的个数($r_i$ 相同则钦定一个顺序)。

考虑:

  • 对于 $i \in[0,n-1]$,以 $l_i – 1$ 为第一关键字,$r_i$ 为第二关键字。
  • 对于 $i \in [n, 2n-1]$,以 $r_i$ 为第一关键字,$l_i-1$ 为第二关键字。

排序,设排序后的序列为 $q_{1\dots2n}$(注意,这里是从 $1$ 开始编号,也只有这里从 $1$ 开始编号)。

考虑 DP,设 $f_{i,j}$ 表示对于 $q_{1\dots i}$ 均满足 $\le r$,且其中有 $j$ 项满足 $< l$ 时对答案的贡献。

设 $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的有 $t$ 个,考虑如何转移,观察上面那个直观的限制图:

  • 若 $q_i \in [0,n-1]$,且只要求 $p_{q_i} \le r_{q_i}$,其贡献为:
    $\le r_{q_i}$ 的数($r_{q_i} + 1$ 个),减去比 $r_{q_i}$ 小的限制的个数:
    • 所有 $i \in [n,2n-1]$ 的 $r_i$($n$ 个)
    • $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的 $q$($t$ 个)
    • $q_{i+1\dots 2n-1}$ 中 $\in [0,n-1]$ 且要求 $<l$ 的 $q$($k-j$ 个)

    转移:$f_{i,j}\leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 – (n + t + k – j))$。

  • 若 $q_i \in [0,n-1]$,且要求 $p_{q_i} < l_{q_i}$,其贡献为:
    $< l_{q_i}$ 的数($l_{q_i}$ 个),减去比 $l_{q_i}-1$ 小的限制的个数:

    • $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$($i-1-t$ 个)
    • $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$($j-1$ 个)

    转移:$f_{i,j} \leftarrow f_{i-1,j-1} \cdot (l_{q_i} – (i-1-t+(j-1)))$。

  • 若 $q_{n,2n-1}$,其贡献为:
    $\le r_{q_i}$ 的数($r_{q_i} + 1$ 个),减去比 $r_{q_i}$ 小的限制的个数:

    • $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$($i-1-t$ 个)
    • $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$($j$ 个)

    转移:$f_{i,j} \leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 – (i-1-t+j))$。

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

代码

const int N = 507;
int n, l[N], r[N], q[N];
modint f[N][N], ans;

inline modint calc(int k) {
    f[0][0] = 1;
    for (int i = 1, t = 0; i <= n << 1; t += q[i] < n, i++)
        for (int j = 0; j <= min(min(i, k), t + (q[i] < n)); j++)
            if (q[i] < n) f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (n + t + k - j)) + (j ? f[i-1][j-1] * (l[q[i]] - (i - 1 - t + (j - 1))) : 0);
            else f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (i - 1 - t + j));
    return f[n<<1][k];
}

int main() {
    rd(n, P);
    for (int i = 0; i < n << 1; i++)
        l[i] = max(0, (int)ceil(sqrt(n * n - i * i))),
        r[i] = min(2 * n - 1, (int)floor(sqrt(4 * n * n - i * i))),
        q[i+1] = i;
    sort(q + 1, q + (n << 1 | 1), [&](int i, int j) {
        pi x = i < n ? mp(l[i] - 1, r[i]) : mp(r[i], l[i] - 1);
        pi y = j < n ? mp(l[j] - 1, r[j]) : mp(r[j], l[j] - 1);
        return x < y;
    });
    for (int i = 0; i <= n; i++)
        if (i & 1) ans -= calc(i);
        else ans += calc(i);
    print(ans);
    return 0;
}

发表评论

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