AtCoder Regular Contest 107 选做
2021/9/25 6:41:14
本文主要是介绍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 107 选做的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升