2020-2021:teams:intrepidsword:2020-nowcoder-multi-5

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020-nowcoder-multi-5 [2020/07/29 01:09]
admin add titles
+++ 2020-2021:teams:intrepidsword:2020-nowcoder-multi-5 [2020/07/29 01:13] (当前版本)
admin [K. Git Merge]
@@ 行 9: / 行 9: @@
 ===== B. Graph =====
+**题目大意**：给你一棵带边权的树，你可以任意加边或删边，但是要保证每次操作后图连通、任意环的边权异或和为 $0$。求可能的最小边权和。
+**题解**：设 $d[u]$ 为每个点到根的边权的异或和。每加一条边，边权只能是 $d[u]\oplus d[v]$。这样把它补成一个完全图，由于每个欧拉子图都可以被 ''%%cycle basis%%'' 表示，因而仍然是合法的。显然不论如何加边和删边，所得的图都是该完全图的生成子图。因而原问题就是求它的最小生成树。
+考虑 ''%%kruskal%%''，首先将所有相同的 $d[u]$ 合并，然后把 $d[u]$ 插入 ''%%trie%%''，显然每棵子树内部会完全合并，因而对于一个点的两棵子树，只会找最小的异或和合并一次。那么对于左子树的每个点在右子树中查询一次即可，每个点只会问 $\log$ 次。
+时间复杂度 $\mathcal{O}(n\log^{2}A)$。
 ===== C. Easy =====
+**题目大意**：给定 $n,m,k$，设长为 $k$ 的正整数数列 $a,b$ 满足 $\sum_{i=1}^{k}a_{i}=n$，$\sum_{i=1}^{k}=m$，求所有 $\prod_{i=1}^{k}\min(a_{i},b_{i})$ 的和。
+**题解**：我一定是个傻子…
+$\prod_{i=1}^{k}\min(a_{i},b_{i})$ 相当于所有满足 $c_{i}\le a_{i}\land c_{i}\le b_{i}$ 的 $c$ 数量。那么我们枚举 $c$ 的和 $t$，不同 $c$ 的方案数是个组合数，然后要使得 $a,b$ 分别大于 $c$，就要将多余的 $n-t$ 和 $m-t$ 分配到各个位置，还是组合数。
 ===== E. Bogo Sort =====
+签到题。
 ===== I. Hard Math Problem =====
+**题目大意**：在无限大的网格上放 ''%%GHE%%''，其中 ''%%H%%'' 必须至少与一个 ''%%G%%'' 和一个 ''%%E%%''相邻（四连通）。求最大的 ''%%H%%'' 比例。
+**题解**：每个 ''%%G%%'' 和 ''%%E%%'' 最多给 $4$ 个 ''%%H%%'' 贡献，因而每个 ''%%H%%'' 至少需要 $1+\frac{1}{2}$ 个位置，答案最多是 $\frac{2}{3}$。按照对角线，两排 ''%%H%%''，一排 ''%%GEGE...%%'' 即可。
 ===== K. Git Merge =====
+**题目大意**：给你一段 ''%%git merge%%'' 后的冲突代码，要求你用 ''%%#ifdef%%''，''%%#else%%''，''%%#endif%%'' 来改写，使得行数最小。具体请看题面。
+**题解**：简单 $dp$。$dp[i][j][S]$ 表示第一段代码已经用了 $i$ 行，第二段代码已经用了 $j$ 行，当前在 ''%%#ifdef%%'' 中，在 ''%%#else%%'' 中或在宏外面。随便转移就好了。因为牛客太缺内存，可能需要用 ''%%short%%''。

2020-2021/teams/intrepidsword/2020-nowcoder-multi-5.1595956177.txt.gz · 最后更改: 2020/07/29 01:09 由 admin