CodeForces 随机跳题
随机跳题：CF *1700 ~ *2400.*CF869C The Intriguing Obsession
*1800。combinatorics，dp，math。
因为两个相同颜色的岛屿之间的距离至少为 \(\color{red}\bf{3}\)，所以显然有以下两条：
[*]两个相同颜色的岛屿之间不能连边。
[*]假设一个岛屿颜色为 \(\bf{A}\)，那么它不能同时和两个 \(\bf{B}\) 颜色岛屿有连边。
综上，我们的连边方式只能是 \(\bf{A-B}\)，\(\bf{B-C}\) 或者 \(\bf{C-A}\)。因为三种情况之间没有交集，所以假设它们的方案数分别为 \(ans_1\)，\(ans_2\)，\(ans_3\)，那么根据乘法原理，答案就是 \(ans_1 \times ans_2 \times ans_3\)。现在考虑如何计算 \(ans\)：
以 \(\bf{A-B}\) 举例，我们可以枚举 \(1 \sim \min(a,b)\) 之间的所有 \(j\)。那么，\(j\) 个 \(\bf{A}\) 和 \(j\) 个 \(\bf{B}\) 连接的方案数就是 \(\operatorname{C}_{a}^{j} \times \operatorname{C}_{b}^{j} \times j!\)。注意，\(j=0\) 时恰好有 \(1\) 种方案。那么就有
\
\(ans_2\)，\(ans_3\) 同理。
那么就得到了最终答案。预处理一下组合数，假设 \(a \le b \le c\)，那么时间复杂度为 \(O(c^2)\)，可以通过。提交记录
*CF1931F Chat Screenshots
*1700。combinatorics，dfs and similar，graphs。
刚拿到这道题的第一思路是将所有的 1 都删掉，后来发现假掉了。
你会发现除了开头的这个元素以外，剩下的元素的顺序总是不改变的。那么可以考虑建图：对于所有 \(1 \le i \le k\)，\(1 < j < n\)，我们将 \(a_{i,j}\) 和 \(a_{i,j+1}\) 之间连边。然后，我们跑一遍拓扑排序。如果成功了，那么说明存在这样一种所有元素的顺序；反之，说明无解。
时间复杂度应该是 \(O(nk)\)。由于 \(\sum nk \le 2 \times 10^5\)，所以可以通过。提交记录
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]