AtCoder Grand Contest 035 题解

作者: xht37 分类: 题解 发布时间: 2020-07-03 04:28

点击数:92

AtCoder Grand Contest 035

XOR Circle

随便判一下。

const int N = 1e5 + 7;
int n, a[N];

int main() {
    rd(n), rda(a, n);
    map<int, int> c;
    for (int i = 1; i <= n; i++) ++c[a[i]];
    if (c[0] == n) return prints("Yes"), 0;
    if (n % 3) return prints("No"), 0;
    for (pi o : c)
        if (o.se % (n / 3)) return prints("No"), 0;
    int k = 0;
    for (pi o : c) {
        int t = o.se / (n / 3);
        while (t--) k ^= o.fi;
    }
    if (k) return prints("No"), 0;
    prints("Yes");
    return 0;
}

Even Degrees

随便定向之后,若有偶数个奇点,则每次找到两个奇点之间的一条路径,对路径上的边取反即可消掉这两个奇点。

奇点个数的奇偶性等于 $m$ 的奇偶性,直接判。

考虑如何构造方案,找出图的一棵生成树,在树上让所有奇点与根之间的路径上的边取反即可。

const int N = 1e5 + 7;
int n, m, x[N], y[N];
bool d[N], v[N];
vector<pi> e[N];

bool dfs(int x) {
    v[x] = 1;
    bool s = d[x];
    for (pi o : e[x]) {
        int y = o.fi, i = o.se;
        if (v[y]) continue;
        bool k = dfs(y);
        if (k) swap(::x[i], ::y[i]);
        s ^= k;
    }
    return s;
}

int main() {
    rd(n, m);
    if (m & 1) return print(-1), 0;
    for (int i = 1; i <= m; i++)
        rd(x[i], y[i]), d[x[i]] ^= 1,
        e[x[i]].pb(mp(y[i], i)), e[y[i]].pb(mp(x[i], i));
    dfs(1);
    for (int i = 1; i <= m; i++) print(x[i], y[i]); 
    return 0;
}

Skolem XOR Tree

题意

  • 构造一棵 $2n$ 个点的树,满足:
    • 对于 $i \in [1,n]$,将 $i$ 和 $i+n$ 的点权设为 $i$。
    • $i$ 与 $i+n$ 在树上的路径上经过的所有点的点权异或和为 $i$。
  • $n \le 10^5$。

题解

若 $n$ 为 $2^i$ 则无解。

否则,若 $n$ 为奇数,则对于 $i$ 为偶数,连边 $(i,i+1),(i+1,n+1),(n+1,i+n),(i+n,i+1+n)$,最后连边 $(1,2)$。

若 $n$ 为偶数,在上面的图的基础上挂上 $n$ 和 $2n$ 即可,随便构造。

代码

int main() {
    int n;
    rd(n);
    if (n - (n & -n) == 0) return prints("No"), 0;
    prints("Yes");
    print(1, 2);
    for (int i = 2; i < n - !(n & 1); i += 2)
        print(i, i + 1), print(i + 1, n + 1), print(n + 1, i + n), print(i + n, i + 1 + n);
    if (!(n & 1)) {
        int x = n & -n, y = n - x;
        print(n, x + 1), print(n * 2, y + n);
    }
    return 0;
}

Add and Remove

题意

  • 给定 $n$ 个数 $a_{1\dots n}$。
  • 你需要进行若干次下列操作,直到只剩下两个数:
    • 选择三个连续的数 $a_{i-1},a_i,a_{i+1}$。
    • 将 $a_{i-1},a_{i+1}$ 都加上 $a_i$,然后删掉 $a_i$。
  • 要求最小化最终剩下的两个数的和。
  • $n \le 18$。

题解

显然答案是对于每个 $a_i$ 乘上一个系数 $x_i$。

倒序考虑整个过程,一开始只有两个元素 $a_1,a_n$,这两个元素的系数 $x_1 = x_n$ 都为 $1$。若在 $a_i$ 和 $a_j$ 中插入了一个元素,其中 $a_i$ 的系数为 $x_i$,$a_j$ 的系数为 $x_j$,则可以发现插入的元素系数为 $x_i + x_j$。

考虑 DP,我们设 $f(i,j,l,r)$ 表示对于区间 $[i,j]$,$x_i = l$,$x_j = r$ 时 $(i,j)$ 对答案的最小贡献,转移时枚举断点 $d \in (i,j)$ 即可。

状态数的上界为 $\mathcal O(n^22^n)$。

代码

const int N = 19;
int n, a[N];

ll f(int i, int j, int l, int r) {
    ll ans = 1e18;
    if (j - i <= 1) return 0;
    for (int d = i + 1; d < j; d++)
        ans = min(ans, f(i, d, l, l + r) + f(d, j, l + r, r) + 1ll * a[d] * (l + r));
    return ans;
}

int main() {
    rd(n), rda(a, n);
    print(f(1, n, 1, 1) + a[1] + a[n]);
    return 0;
}

Develop

题意

  • 给定 $n,k$。
  • 设 $S$ 为整数的全集,求通过若干次下列操作可以得到多少个不同的集合:
    • 选择 $x \in S \cap [1,n]$,将 $x$ 从 $S$ 中去掉。
    • 对于 $x-2$ 和 $x+k$,若不在 $S$ 中,则加进 $S$。
  • $1 \le k \le n \le 150$,答案对 $P$ 取模。

题解

考虑一个编号为 $1 \sim n$ 的有向图,连边 $(x,x-2)$ 和 $(x,x+k)$(如果存在)。

则每次操作相当于将一个点染黑,将其后继染白,其中初始时所有点都是白的,问最终形成的图有多少种方案。

显然黑点不能构成环,所以黑点一定是个 DAG,那么按照拓扑序选择黑点即可,于是问题等价于求给定图不存在黑环的方案数。

对 $k$ 分奇偶考虑然后简单 DP 一下即可。

代码

const int N = 157;
int n, K;
modint f[N][N], g[N][N][N], ans, ans0, ans1;

int main() {
    rd(n, K, P);
    if (K & 1) {
        g[0][0][0] = 1;
        int m = (K >> 1) + ((n + 1) >> 1);
        for (int i = 0; i < m; i++)
            for (int j = 0; j <= n >> 1; j++)
                for (int k = 0; k <= K + 1; k++) {
                    g[i+1][0][0] += g[i][j][k];
                    if (i < n >> 1) g[i+1][j+1][0] += g[i][j][k];
                    if (i >= K >> 1) g[i+1][0][k?k+1:0] += g[i][j][k];
                    if (i >= (K >> 1) && i < (n >> 1)) g[i+1][j+1][max(j+2,k+1)] += g[i][j][k];
                }
        for (int j = 0; j <= n >> 1; j++)
            for (int k = 0; k <= K + 1; k++)
                ans += g[m][j][k];
        print(ans);
    } else {
        f[0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= min(i, K >> 1); j++)
                f[i+1][j+1] += f[i][j], f[i+1][0] += f[i][j];
        for (int j = 0; j <= K >> 1; j++)
            ans0 += f[n>>1][j], ans1 += f[(n+1)>>1][j];
        print(ans0 * ans1);
    }
    return 0;
}

Two Histograms

题意

  • 对于一个 $n \times m$ 的矩阵,一开始每个位置上都是 $0$。
  • 对于每一行,选择最左边的 $0 \sim m$ 个位置 $+1$;对于每一列,选择最上边的 $0 \sim n$ 个位置 $+1$。
  • 求最后能形成的矩阵方案数。
  • $n,m \le 5 \times 10^5$,答案对 $998244353$ 取模。

题解

注意到只有 $k_x = y$,$l_y = x – 1$ 和 $k_x = y – 1$,$l_y = x$ 才会形成一样的矩阵,那么枚举满足条件的 $(x,y)$ 对数容斥:
$$
ans = \sum_{i=0}^{\min(n,m)} (-1)^i \binom ni \binom mi i!(m+1)^{n-i}(n+1)^{m-i}
$$
时间复杂度 $\mathcal O(n)$。

代码

int main() {
    int n, m;
    rd(n, m), init(max(n, m) + 1);
    modint a = (modint)(m + 1) ^ n, b = (modint)(n + 1) ^ m, w = 1, ans;
    for (int i = 0; i <= min(n, m); i++, a *= v[m+1], b *= v[n+1], w = -w)
        ans += w * binom(n, i) * binom(m, i) * p[i] * a * b; 
    print(ans);
    return 0;
}

发表评论

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