2019-2020 ICPC Asia Hong Kong Regional Contest

2019-2020 ICPC亚洲香港区比赛

B - Binary Tree

噗，标题是什么？

考虑到每次取的子树的大小一定是奇数。

因此，判断\(n\)的奇偶性就足够了。

C - Constructing Ranches

首先，考虑一个简单的必要条件，一个列数\(a_{1\sim n}\)可以形成一个简单的多边形：\(2\cdot \max_i a_i \sum_i a_i\)。

然后，一般的做法比较清晰，合法路径的数量是按点分而治之来统计的。

两条路径的最大值为\(x_1，x_2\)，路径之和为\(y_1，y_2\)。然后，通过简单的推导，贡献条件为：\(\ begin { cases } x _ 2x _ 1 \ \ y _ 22x _ 1-y _ 1 \ end { cases } \)(其中\(x_2x_1\)可以确定最大值)。

很明显，它是一个二维偏序问题，利用包含统计量可以化为静态问题，用扫描线树阵列求解。计算分而治之的时间复杂度\ (o (n \ log 2 n) \)。

一个细节是，然后处理两条路径对接时分而治之中心的影响(单说，就是因为没想清楚，卡了很久)。第一种方法不是一开始就处理根，而是在后面的统计中加入，但是这样会影响最大值和两个指标，非常麻烦。还有一种方法是一开始就加，这样后期只需要从总和中减去重复统计的中心，而最大值就不需要了，会方便很多。

D - Defining Labels

寻找规律。对于一个\(10-\textit{based}\)数\(X_kX_{k-1}\cdots X_1X_0\)，其对应的十进制真值为\ (\ sum _ {i=0} k (x _ i 1)。

要从类比到\(k-\textit{based}\)的数字，只需进行正常的二进制转换，只需将\(X\)减1，再加上\(10-k\)即可进入递归。

E - Erasing Numbers

这是另一个神奇的结论。又是一个我做不到的。

首先发现\(n\le 5000\)，近似推测解是对每个数判断一次\(O(n)\)。在判断每个数字\(x\)时，我们可以发现在考虑其他数字时，只能考虑它们与当前数字\(x\)的大小关系。因此，小于标记为\(0\)，大于标记为\(1\)。

然后得出结论：如果序列中\(0\)的个数等于\(1\)，那么只有\(x\)可以消除。可以发现，如果两者都在\(x\)的每一侧，那么可以操作0x1或1x0，直到\(x\)保留。如果是混合的，绝对可以找一个位置\(0，1\)相邻，然后互相减去一。

当然，他们不可能都是平等的，所以考虑去掉多余的一个。请注意，如果要消除冗余\(0\)，那么只有000才是可靠的。如果没有联系，我们可以消除中间分开的01来达到目的。

所以有这样一个算法：每次一个子段\(0\)比\(1\)多三个，就可以直接减少两个\(0\)。\(x\)两边都可以执行一次，直到数量相等才判定成功。

复杂性(o (n 2) \)？感觉不是这么简单的问题。你为什么通过了这么多题？

G - Game Design

结构简单。首先根是有用的。我们使它的点权重\(10 ^ 9 \)，因此它对解的数量没有影响。

考虑到这个\(K\)一定是几个数相乘的结果，我们考虑在根上挂几条链，每条链的长度(点数)为\(l\)，并且让链上的点权重为\(1\)，这样就是\(l\)方案。

因此，不难想到素因子分解：\ (k=\ prod _ I k p _ I {c _ I} \)？然后乘以一个\(p\)并在根上挂一串\(p\)点。

注意我们受到点数的限制，素因子分解就是把乘法变成加法，这样点数就是\ (\ sum _ I k c _ IP _ I \)？规模。但如果\(K\)有——的巨大质因数或大质数(如\(998244353\))，点数还是太多了。

想想微操：我们试着放\(K\)？减一。可以发现它的分解会有很大的变化，定轮后不会有过多的品质因子。获取已处理的\(K'=K- t\)？之后，相应的，在根目录下构建\(t\)？一个新点，哪些链连接到这个新点而不是根，新点的权重就是链的个数。请注意，这些链用\(K'\)表示？出口。显然，点还在\ (o (\ log k) \ sim o (\ log 2k) \)附近，可以通过。

H - Hold the Line

单点连接(从头开始)，间隔查询在前面和后面。在线上，需要维护动态的二维信息，所以很明显线段树设置了一个大的常量\ (\ log 2 \)集合。那样地

而 \(n\le 5\cdot 10^5\) 这么大的数据肯定过不了，但由于这动态的二维信息摆在哪里，正解应该是离线小常数的 \(O(n\log ^2 n)\)。

扫描线。我们固定右端点 \(R\)，这时 \(\le R\) 的插入操作就已更新。考虑维护用一个以权值为下标的线段树，我们要求前驱或后继，可以直接在线段树上二分求解。每个线段树结点保存的是二维点集 \((t,p)\)：插入时间 \(t\) 以及位置 \(p\)。

于是，判断一个线段树结点是否包含可行点，只要查询每个点左上区域是否存在点即可。然后就是一个 trick：若存在 \(A,B\) 两点满足 \(A\) 在 \(B\) 的左上方，那么 \(B\) 就完全没用了。删去所有这样的 \(B\)，余下的点按 \(t\) 排序，\(p\) 也是单调的。这样就变成一维问题了！判断存在只要在单调点列上二分查找即可。

然而我们要支持动态插入，好像又要用 set 了！但注意到，我们有一维是位置，而推进扫描线使得加入的点在位置上就是天然单调的，仔细一想其实只要 vector 就行了。

最后复杂度是 \(O(n\log ^2n)\)。

I - Incoming Asteroids

跟着这题学了个新 trick /se

考虑每个任务的 \(k\) 都很小，那么对这 \(k\) 个位置都设一个 \(\lfloor y/k \rfloor\) 的阈值。每当 \(k\) 个位置的其中一个达到了这个阈值就重构这个任务并重新放置。（要说这怎么想到的……只能说 \(k\) 个位置都地位相等，自然阈值都相等；而要保证所设的阈值不能出现“完成了却不知道”，最大的可行阈值就是 \(\lfloor y/k \rfloor\)）。

复杂度不难证明，由于一次重构意味着减小 \(1/k\)，那么复杂度就是 \(O(n\log n\log y)\)。其中 \(\log n\) 是维护需要的数据结构的时间。

J - Junior Mathematician

摆明了是数位 dp。复习一下。

考虑我们记搜时要记录那些信息到状态里面：位数，是否有上界（基础信息，这里似乎不需要判前导零），\(x\bmod m\)，\(f(x)\bmod m\) 以及数位和。

但是这样维度有点多，冷静分析可以发现 \(x\bmod m,f(x)\bmod m\) 这两个我们可以用一个 \(f(x)-x \bmod m\)? 代替。

然后在转移注意下细节和卡常就好啦。写了个小丑 map 被卡爆了

本文来自博客园，作者：-Wallace-，转载请注明原文链接：https://www.cnblogs.com/-Wallace-/p/icpc2020-hk-rc.html