AtCoder Grand Contest 045 题解

作者: xht37 分类: 题解 发布时间: 2020-06-16 22:58

点击数:71

AtCoder Grand Contest 045

Xor Battle

倒序考虑,如果在一个 $1$ 处能够成功加入线性基,则说明无论 $1$ 之前的数是什么情况,都可以使 $1$ 之后的数不在线性基内,因此 $1$ 赢,否则 $0$ 赢。

const int N = 207;
int n;
ll a[N], b[61];
char s[N];

inline bool ins(ll x) {
    for (int i = 60; ~i; i--)
        if (x >> i & 1) {
            if (!b[i]) return b[i] = x, 1;
            x ^= b[i];
        }
    return 0;
}

inline void solve() {
    memset(b, 0, sizeof(b));
    rd(n), rda(a, n), rds(s, n);
    reverse(a + 1, a + n + 1);
    reverse(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++)
        if (ins(a[i]) && s[i] == '1') return print(1);
    print(0);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

01 Unbalanced

$0$ 当成 $1$,$1$ 当成 $-1$,则目标相当于最小化前缀和的极差。

考虑枚举前缀和的最小值 $x$,然后从后往前贪心,找到在这个最小值的限制下前缀和最大值的最小值。

然后可以发现 $x$ 只需要检查 $x$ 理论上能够达到的最大值 $m$ 和 $m-1$。

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

const int N = 1e6 + 7;
int n, p[N], mn, mx;
char s[N];

inline int calc(int o) {
    p[n] = mx = 0;
    for (int i = n; i; i--)
        p[i-1] = max(p[i] + (s[i] == '1' ? 1 : -1), 0);
    for (int i = 1, k = 0; i <= n; mx = max(mx, k), ++i)
        if (s[i] == '?') k += k - 1 - p[i] >= o ? -1 : 1;
        else k += s[i] == '0' ? 1 : -1;
    return mx;
}

int main() {
    rds(s, n);
    for (int i = 1, k = 0; i <= n; i++)
        mn = min(mn, s[i] == '1' ? --k : ++k);
    print(min(calc(mn) - mn, calc(mn - 1) - mn + 1));
    return 0;
}

Range Set

考虑怎样的 $0/1$ 序列不合法,直接给结论:

  • 不妨设 $a \le b$,把所有长度 $\ge a$ 的 $0$ 连续段都变成 $1$ 连续段后,不存在长度 $\ge b$ 的 $1$ 连续段,则不合法。

于是考虑 DP,设 $f_{0/1,i}$ 表示以 $i$ 结尾的 $0/1$ 连续段的方案数,提前处理转移系数后可以做到 $\mathcal O(n^2)$。

注意首尾比较特殊,要特判一下。

const int N = 5e3 + 7;
int n, a, b;

inline modint F(int n, int m) {
    return binom(n + m - 1, m - 1);
}

modint f[N], g[N], h[2][N], w[N];

int main() {
    rd(n, a, b), init(1e6);
    if (a > b) swap(a, b);
    for (int i = 1; i < a; i++) f[i] = 1;
    for (int i = 1; i < b; i++) {
        for (int j = 0; j * (a + 1) < i; j++)
            g[i] += F(i - j * (a + 1) - 1, j * 2 + 1);
        w[i] = g[i];
        for (int j = 0; j * (a + 1) <= i; j++)
            w[i] += F(i - j * (a + 1), j * 2);
    }
    h[0][0] = h[1][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            h[0][i] += h[1][i-j] * f[j], h[1][i] += h[0][i-j] * (i == j ? w[j] : (i == n ? w[j] : g[j]));
    }
    print(((modint)2 ^ n) - h[0][n] - h[1][n]);
    return 0;
}

Lamps and Buttons

最优策略一定是:

  • 从左往右选择一盏尚未操作过的亮着的灯 $x$。
  • 若 $p_x = x$,则 $x$ 不可能再亮起,负。
  • 若 $p_x \ne x$,且 $p_x$ 暗下去了,则可以再次操作 $x$ 使其亮回来。
  • 若 $p_x = x$,且 $p_x$ 亮起来了,则转而操作 $p_x$,将 $x$ 所在的置换环全部点亮。

于是一个排列合法当且仅当:

  • 设 $t$ 是最小的满足 $t \le a$ 且 $p_t = t$ 的位置,若不存在,则 $t = a + 1$。
  • 对于所有 $a + 1 \le x \le n$,$x$ 所在的置换环上存在一个 $\le t – 1$ 的元素。

然后开始推柿子。

枚举 $t \in [2,a+1]$,则相当于我们把这个排列拆成了四段:

  1. $i \in [1,t-1]$,这一段中要求 $p_i \ne i$,个数为 $x = t – 1$。
  2. $i = t$,这一段中要求 $p_i = i$,注意当 $t = a + 1$ 时这一段不存在
  3. $i \in [t+1,a]$,这一段中没有任何要求,注意这一段可能为空,个数为 $y = \max(a-t,0)$。
  4. $i \in [a+1,n]$,这一段中要求 $i$ 所在的置换环上存在至少一个 $\in [1,t-1]$ 的元素,个数为 $z = n – a$。

第二段的限制条件可以直接扔掉,先暂时忽略第一段的限制条件。

先考虑第一段的 $x$ 个数,显然排列的方案数为 $x!$。

再考虑第四段的 $z$ 个数,第 $i$ 个数放入排列中时必须插入某一个置换环中,方案数为 $x+i-1$。

最后考虑第三段的 $y$ 个数,第 $i$ 个数放入排列中时可以插入某一个置换环中,也可以自成一个置换环,方案数为 $x+z+i$。

因此总方案数为 $\frac{x}{x+z}(x+y+z)!$。

再考虑第一段的限制条件,枚举有多少个 $p_i = i$ 然后容斥掉就行了,即:
$$
\sum_{i=0}^x (-1)^x \binom xi \frac{x-i}{x-i+z}(x-i+y+z)!
$$
总时间复杂度 $\mathcal O(n + a^2)$。

int main() {
    int n, a;
    modint ans;
    rd(n, a), init(n);
    for (int t = 2; t <= a + 1; t++) {
        int x = t - 1, y = max(a - t, 0), z = n - a;
        for (int i = 0; i <= x; i++)
            if (i & 1) ans -= binom(x, i) * (x - i) * v[x-i+z] * p[x-i+y+z];
            else ans += binom(x, i) * (x - i) * v[x-i+z] * p[x-i+y+z];
    }
    print(ans);
    return 0;
}

Fragile Balls

设 $p$ 表示 $a_i \ne b_i$ 的球数。

首先考虑所有 $c_i$ 都为 $1$ 的情况,此时答案要么是 $p$ 要么是 $-1$。

考虑对于每个球建边 $a_i \to b_i$,注意题目条件保证了每个点的入度都不为 $0$。

我们可以将每个连通块(忽略边的方向)分为以下三类:

  1. 连通块仅包含一个长度 $=1$ 的环。
  2. 连通块仅包含一个长度 $>1$ 的环。
  3. 其它。

可以发现,若存在第 2 类连通块,则答案为 $-1$,否则由于第 3 类可以直接构造一组合法的方案,所以答案为 $p$。

接下来考虑当 $c_i \ge 1$ 的情况,此时即使存在第 2 类连通块,也可能有解。

设第 2 类的连通块个数为 $x$,我们只需要考虑 $x \ge 1$ 的情况,同时对于每个连通块我们一定会至少需要 $1$ 步去处理,总共需要 $x$ 步,这 $x$ 步先计算上。

我们要处理第 2 类连通块,必须从连通块外移入一个球 $i$ 到连通块内。先假设这个 $i$ 可以移出来,那么这个 $i$ 有以下几种情况:

  • $i$ 在第 1 类连通块内,则此时的操作为,把 $i$ 移到某个第 2 类连通块处理,然后移向下一个第 2 类连通块处理,处理了最多 $c_i – 2$ 个连通块之后再移回去,额外花费了 $2$ 步
  • $i$ 在第 2 类连通块内,则我们可以在 $i$ 所在的连通块被处理时将 $i$ 移出去处理其余的第 2 类连通块,处理最多 $c_i – 1$ 个连通块之后,将 $i$ 移回去处理所在的连通块,额外花费了 $0$ 步
  • $i$ 在第 3 类连通块内,且 $a_i = b_i$,则可以处理最多 $c_i – 1$ 个第 2 类连通块,额外花费了 $1$ 步
  • $i$ 在第 3 类连通块内,且 $a_i \ne b_i$,则可以处理最多 $c_i – 1$ 个第 2 类连通块,额外花费了 $0$ 步

考虑如何满足 $i$ 能移出来,我们只需要先拿一个第 3 类连通块中的 $i$ 来盘活整个局面。

于是问题变成给定若干个代价 $\le 2$ 的物品,要求总价值 $\ge x$ 的最小代价。

显然所有代价为 $0$ 的物品都贪心地拿,对于代价为 $1$ 和 $2$ 的物品排序后 Two Pointers 一下即可。

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

const int N = 1e5 + 7;
int n, m, a[N], b[N], c[N], d[N], f[N], s[N];
bool v[N];
vi p1, p2, p3, p4;
ll ans, cnt, sum, now;

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

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++) f[i] = i, v[i] = 1;
    for (int i = 1; i <= m; i++)
        rd(a[i], b[i], c[i]), ++d[a[i]],
        f[get(a[i])] = get(b[i]), ans += a[i] != b[i];
    for (int i = 1; i <= n; i++) {
        ++s[get(i)];
        if (d[i] != 1) v[get(i)] = 0;
    }
    for (int i = 1; i <= n; i++)
        cnt += get(i) == i && v[i] && s[i] > 1;
    if (!cnt) return print(ans), 0;
    ans += cnt;
    for (int i = 1; i <= m; i++) {
        if (c[i] == 1) continue;
        int x = get(i);
        if (v[x] && s[x] == 1) p1.pb(c[i] - 2);
        if (v[x] && s[x] > 1) p2.pb(c[i] - 1);
        if (!v[x] && a[i] == b[i]) p3.pb(c[i] - 1);
        if (!v[x] && a[i] != b[i]) p4.pb(c[i] - 1);
    }
    for (int x : p1) sum += x;
    for (int x : p2) sum += x;
    for (int x : p3) sum += x;
    for (int x : p4) sum += x;
    if (sum < cnt || (p3.empty() && p4.empty())) return print(-1), 0;
    sort(p1.begin(), p1.end());
    sort(p2.begin(), p2.end());
    sort(p3.begin(), p3.end());
    sort(p4.begin(), p4.end());
    if (p4.size()) cnt -= p4.back(), p4.pop_back();
    else ++ans, cnt -= p3.back(), p3.pop_back();
    for (int x : p2) cnt -= x;
    for (int x : p4) cnt -= x;
    if (cnt <= 0) return print(ans), 0;
    now = ans, ans = 1e18, sum = 0;
    for (int x : p3) sum += x;
    for (int i = p1.size(), j = 0; ~i; i--) {
        if (i < (int)p1.size()) sum += p1[i];
        while (j < (int)p3.size() && sum - p3[j] >= cnt) sum -= p3[j++];
        if (sum >= cnt) ans = min(ans, now + 2 * ((int)p1.size() - i) + ((int)p3.size() - j));
    }
    print(ans);
    return 0;
}

Division into Multiples

咕。

发表评论

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