差别

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

--- 2020-2021:teams:intrepidsword:2020-nowcoder-multi-4 [2020/07/24 08:26]
chielo 创建
+++ 2020-2021:teams:intrepidsword:2020-nowcoder-multi-4 [2020/07/28 22:56] (当前版本)
admin [I. Investigating Legions]
@@ 行 9: / 行 9: @@
 ===== A. Ancient Distance =====
-**题目大意**：
+**题目大意**：给个树，要你给这个树的 $K$ 个节点打个标记，每个点算一下到祖先中最近的被标记的点的距离（没有就是无穷大），取最大值作为费用。问你最小费用是多少。对每个 $K \in [1, n]$ 都求一下。
 **题解**：
-===== B. Basic Gcd Problem =====
+考虑已经知道最后的费用是 $h$，想想有没有办法尽可能少地去标节点。会发现标节点的过程就是切子树的过程。
-**题目大意**：
+想一下从根开始，切掉所有距离为 $h$ 的，嗯，不对。那就只能从最深的叶子开始，搞掉第 $h$ 个祖先，直到搞完。这样贪心正确性比较明显，因为只要有一个最优的方案，你总有办法调整成这样贪心构造出来的样子。
-**题解**：
+然后我们队，傻兮兮地在维护叶子的情况，需要用 set 来维护 DFS 顺序的叶子；每次切出来一个子树相当于切走了一段区间；然后如果弄出来一个新的叶子，又得加回去。为了能快速地初始化，对于没有并过的叶子还得单独弄成一类特殊的区间。做法诡异极了。
+那么正常的做法，考虑一下被切掉的子树，那肯定也就是 DFS 序上的一段区间的所有节点，既然切走了，全部赋值成 0 就好；需要维护的是区间最大值，也就是最深的节点，那也必然是叶子。初始化的话，你可以在标记区间赋值成某个特殊值时，就将该线段树节点的信息恢复成初始的情况，就没了。
+===== B. Basic Gcd Problem =====
+签到题。
 ===== C. Count New String =====
@@ 行 27: / 行 32: @@
 ===== D. Dividing Strings =====
-**题目大意**：
+**题目大意**：给你一个数字串，让你分割成若干段，使得极差最小。不允许前导 $0$。$n\le10^{5}$，$\sum n\le10^{6}$。
-**题解**：
+**题解**：首先可以一位一位分割，因而答案最大是 $9$。各个部分的位数至多相差一位。
+对于所有部分位数相同的情况，可以枚举 $n$ 的约数，至多 $128$ 个，由于常数小，可以通过。考虑更快一点的做法，由于答案不超过 $9$，因而每个部分一定是这样的形式：一段 ''%%lcp%%''，一位数字至多相差 $1$，若干个 $0$（对应前一位大 $1$ 的情况）或若干个 $9$（对应前一位小 $1$ 的情况），最后一个数字可任取。那么用后缀数组即可实现。甚至你可以不用后缀数组，因为约数和是小于调和级数的，所以也可以暴力 ''%%check%%'' 前两段然后再搞搞。不过总而言之，后面两种方法都是很麻烦的。
+对于至多相差一位的情况，则只能是 $10000\cdots$ 和 $9999\cdots$。与上面类似判断即可。
 ===== E. Eliminate++ =====
@@ 行 39: / 行 47: @@
 ===== F. Finding the Order =====
-**题目大意**：
+签到题。
-**题解**：
 ===== G. Geometry Challenge =====
-**题目大意**：
+补补补，补个啥啊补
-**题解**：
 ===== H. Harder Gcd Problem =====
-**题目大意**：
+**题目大意**：求 $1\sim n$ 的最大匹配，其中不互质的两个数之间连边。
-**题解**：
+**题解**：注意到 $1$ 及所有 $>\frac{n}{2}$ 的质数是孤立点，不管它们。我们证明剩下的点总能剩最多一个。首先以所有的奇质数为下标设置桶，将每个奇数随意扔进它某个质因子代表的桶里。这样，每个桶内两两匹配后，至多剩余一个数，我们把它和 $2p$ 匹配。这样就只剩若干偶数了，显然至多有一个不能匹配。
 ===== I. Investigating Legions =====
-**题目大意**：
+**题目大意**：有 $n$ 个点，$m$ 种类型，现在告诉你两两点对是否属于同一连通块，但是有至多 $5\%$ 的概率反转。让你求出每个点的类型。其中，$30\le n\le300,1\le m\le\lfloor\frac{n}{30}\rfloor$。每个点随机一种类型，出错也是随机的。
-**题解**：
+**题解**：对于每个点，考虑剩下的点哪些和它属于一个连通块。对于同一连通块的点，它们共同的邻点应当很多，反之则应当很少。对于同一连通块的，大致计算一下期望应当是 $\frac{n}{m}-\frac{2n}{20m}$，反之则大致是 $\frac{2n}{20m}$。经过本地测试，取最大值的 $\frac{2}{3}$ 为阈值可正确判断，并且 ''%%ac is ok%%''。
 ===== J. Jumping on the Graph =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具