AtCoder Regular Contest 107 选做

D - Number of Multisets

给定两个正整数 \(N, K\),求有多少个可重集满足以下条件:

  • 可重集包含恰好 \(N\) 个元素,且它们的和为 \(K\)。
  • 每一个元素都可以表示为 \(2^{-x}\ (x \in \N)\)。

答案对 \(998244353\) 取模。

\(1 \le K \le N \le 3000\)。

2s, 1GB

用 \(f_{N, K}\) 表示 \(K\) 拆成 \(N\) 个的方案数。

分两种情况考虑:

  • 当前的可重集中不包含 \(1\),那么, 假设我们将可重集中的所有数都翻一倍,就变成了把 \(2K\) 拆成 \(N\) 个的方案数,而且显然这些方案是一一对应的。那么就有 \(f_{N, K} \gets f_{N, 2K}\)。
  • 当前的可重集中包含若干个 \(1\),那么,假设将其中的一个 \(1\) 删去,就变成了把 \(K - 1\) 拆成 \(N - 1\) 个的方案数,而且显然这些方案是一一对应的。那么就有 \(f_{N, K} \gets f_{N-1, K-1}\)。

于是我们得到递推式 \(f_{N,K} = f_{N, 2K} + f_{N-1,K-1}\),根据这个递推即可。

注意到当 \(K > N\) 时,\(f_{N, K} = 0\),所以时间复杂度为 \(O(N^2)\)。

https://atcoder.jp/contests/arc107/submissions/26067671

E - Mex Mat

对于一个 \(N\times N\) 的矩阵,给定 \(a_{1, 1}, a_{1, 2}\cdots, a_{1, N}\) 和 \(a_{2, 1}, \cdots, a_{N,1}\),并给出递推式:

\[a_{i, j} = {\rm mex}(a_{i-1, j}, a_{i,j-1})\ (2 \le i, j \le N) \]

求出这个矩阵中有多少个 \(0\),多少个 \(1\),多少个 \(2\)。

\(1 \le N \le 5 \times 10^5\),\(a_{i, j} \in \{0, 1, 2\}\)。

2s, 1GB

打表找规律,发现只要算出前 \(4\) 行和前 \(4\) 列的值以后,就有:

\[a_{i, j} = a_{i - 1, j-1} \ (i, j \ge 5) \]

时间复杂度 \(O(N)\)。

https://atcoder.jp/contests/arc107/submissions/26082055

F - Sum of Abs

给定一张有 \(N\) 个点 \(M\) 条边的无向图,第 \(i\) 个结点上有两个正整数 \(A_i, B_i\),第 \(i\) 条边连接 \(U_i, V_i\)。

现在可以删去若干个点,删去一个点的代价是 \(A_i\),并且与其相连的边也会被删除。

最终,一张图的得分为每个连通块的 \(|\sum B|\) 之和。

求「得分 \(-\) 代价」的最大值。

\(1 \le N , M \le 300\),\(1 \le A_i \le 10^6\),\(-10^6 \le B_i \le 10^6\),\(1 \le U_i, V_i \le N\),图没有重边和自环。

2s, 1GB

注意到,对于一个连通块,它的价值应该是 \(\max\{\sum B, \sum-B\}\)。

于是等价转化一下这个问题,可以变成给每个点添加一个符号 \(+\) / \(-\) / \(\rm delete\),分别对应给答案的贡献为 \(B_i, -B_i, -A_i\),且两个相邻的点的符号不能一个是 \(+\) 一个是 \(-\)。

首先考虑最理想情况,答案显然为 \(\sum_{i=1}^{N} |B_i|\),然后考虑使用最小割删去不合理的那部分价值。

具体的,将每个点拆成两个点 \(u_1, u_2\),我们的目标是:

  • 当 \(u_1, u_2\) 同属于 \(T\) 侧时,表示 \(+u\)。
  • 当 \(u_1, u_2\) 同属于 \(S\) 侧时,表示 \(-u\)。
  • 当 \(u_1\) 属于 \(S\) 侧,\(u_2\) 属于 \(T\) 侧时,表示 \(\text{delete } u\)。

可以想到如下构造:

  • 对任意 \(1 \le u \le N\),\(u_1 \rightarrow u_2\),边权 \(|B_u| + A_u\)。
  • 对任意 \(1 \le i \le M\),\(U_{i\ 2} \to V_{i \ 1}, V_{i \ 2} \to U_{i \ 1}\),边权均为 \(+\infty\)。
  • 对任意 \(1 \le u \le N\)
    • 如果 \(B_u \ge 0\),则连边 \(u_2 \to T\),边权为 \(2B_u\)。
    • 如果 \(B_u < 0\),则连边 \(S \to u_1\),边权为 \(-2B_u\)。

用 \(\sum_{i=1}^{N} B_i-\) 最小割 即可,使用 Dinic,时间复杂度 \(O(N^2M)\)。

https://atcoder.jp/contests/arc107/submissions/26084176

上一篇:AtCoder Regular Contest 125


下一篇:「atcoder - 214G」Three Permutations