The 2019 China Collegiate Programming Contest Harbin Site

就是说,永远不会博弈枯了枯了。

来写点一套题的题解吧(如果我会的话。

#### A - Artful Paintings

场A(-6)。

考虑染球个数的前缀和,会发现满足一些不等式: $s_i-s_{i-1} \ge 0,s_i-s_{i-1} \le 1,s_{r_i}-s_{l_i-1} \ge k_i,s_{n}-(s_{r_i}-s_{l_i-1}) \ge k_i$ 。然后会发现有个s_n的东西弄不掉,我们就想办法把它变成常数。

发现可以二分 $s_n$ ,于是它就变成常数了,并且要满足 $s_n-s_0=mid$ ,然后就是差分约束,跑个 $\text{spfa}$ 即可。

效率: $O(nm\log n)$ 。

要剪枝,不然会T。

#### B - Binary Numbers

场A(-4)。

$F()$ 相当于求两个数写成二进制形式下的 $\text{lcp}$ 。

显然,对于 $(i,j)$ 且 $i<j$ ,如果固定 $i$ ,那么 $j$ 越大的话它们的 $\text{lcp}$ 会越小。

因此,我们其实只需要考虑对于 $i-1$ 和 $i$ 区间,要满足 $F(a_{i-1},r_{i-1}) \ge F(a_i,r_{i-1}),F(a_{i-1},l_i) \le F(a_i,l_i)$ 。

因此我们考虑 $\text{dp}$ : $f_i$ 表示以 $i$ 为结尾的答案,那么对于 $i$ ,能够转移到它的点一定是一段区间,而且 $i$ 越大,区间只会往左移。因此记个前缀和就好了。

效率:$O(m2^m)$ 。

注意模数是 $1e8+7$ ...

#### C - Competition in Swiss-system

场未A。

模拟,题目太长,没时间打。

#### D - Driverless Car

场未A,乍一眼看应该是计算几何,不会。

#### E - Exchanging Gifts

场A(-4)。

考虑如果知道了最后一个串怎么求答案。那就只要看颜色最多的数量是否达到总长的一半即可,如果没达到就是总长,否则就是去掉最多颜色数的两倍。

因此我们其实只要知道每个颜色在最后一个串出现多少次即可,那其实也就是要知道每个操作为 $1$ 的串对于最后一个串的贡献。

因此做个 $\text{dp}$ 即可。 $f_i$ 表示第 $i$ 个串在最后一个串中出现多少次,然后把它传递给那两个合并串即可。

效率: $O(nlogn)$ 。

场上需要写 $\text{fread}$ 才能过...大受震撼。

#### F - Fixing Banners

场1A。

直接 $6!$ 判断就好了。

效率: $O(6!\times length)$ 。

#### G - Game Store

场未A。以下口胡。

是我不会的 $\text{nim-k}$ 游戏了。

如果二进制下,每一位 $1$ 的个数都是 $k+1$ 的倍数(这题是 $3$ 的倍数),那么先手必败,否则必胜。

因此, `A` 如果选择了一些 $\text{set}$ ,那么这些 $\text{set}$ 里的石堆可以看成向量 $a_i$ , `B` 要移除一些石堆来确保自己能赢,也就是说,每个 $a_i$ 最后会剩下 $0/1/2$ 堆,那其实 `B` 要做的就是在模 $3$ 意义下,使得 $\sum k_i a_i=0$ 。

因此, `A` 要选的就是 $a_i$ 的最大权线性无关组。用线性基维护,这里的线性基是对 $3$ 取模的。具体就是每次到非零位,如果当前位的值比自己小,那就交换并且消高位往下走即可。

然后听说模 $3$ 很慢,要用 $4$ 进制来优化常数。

#### H - Highway Buses

场未A,以下口胡。

最优解只可能在 $T=1$ 和 $T=T_{max}$ 取,因此做两遍就好了。

搞出一棵生成树,非树边最多 $51$ 条。

考虑如果只走树边,那么就考虑在i点的答案为 $g_i$ ,然后我们维护一个堆,按照 $g_i+c_i$ 从小到大排序,然后每次用堆顶去更新别的点答案。

假设堆顶为 $i$ ,那么我们要更新的点 $j$ 要满足树上 $\text{dis}(i,j) \le f_i$ 且还没有被更新过。因此我们考虑建出点分树,从i往上走,对于每个点分中心维护一个队列,按照 $\text{dis}$ 排序,因此我们每次更新队列中的前面一部分的点即可。

现在考虑非树边,如果经过了非树边 $(u,v)$ ,那么一定会经过 $u$ 点,那么我们最多有 $51$ 个这样的点,因此现在原图上跑 $51$ 次单源最短路。然后在原本的基础上考虑如果 $i$ 要更新到 $j$ 并且走了非树边,那么我们就枚举关键点,那么能够更新那个 $j$ 的要求就是 $dis(i,u)+dis(u,j) \le f_i$ ,因此也维护一个队列即可。

打标记使得每个点只进入堆一次,那么效率就是 $O(nlogn+51n)$ 。

#### I - Interesting Permutation

场A(-1)。

先判掉一些非法情况,比如 $h_i!=0,h_n!=n-1,h_i>h_{i+1}$。

然后我们设前i的答案为 $f_i$ 。

如果 $h_i>h_{i-1}$ 的话,那么第 $i$ 个数肯定是前 $i$ 个数中的最大值或者最小值,因此 $f_i=f_{i-1}\times 2$ 。

如果 $h_i=h_{i-1}$ 的话,那第 $i$ 个数就是选择了最大值和最小值中的一个数,因此我们再维护最大值和最小值中还有多少数没有被选择即可。

效率: $O(n)$ 。

-1是因为 $(s+=f_i)\%=P$ 写成了 $\%P$ ...枯了枯了。

#### J - Justifying the Conjecture

场1A。

$n<6$ 无解,否则 $n$ 是奇数就是 $3,n-3$ ,偶数就是 $2,n-2$ 。

#### K - Keeping Rabbits

场1A。

有生之年我没有被卡精度。

兔子重量的比例不会变,所以每次增加的重量不会变,所以直接加上 $k \times \frac{w_i}{s}$ 即可。

#### L - LRU Algorithm

场1A。

发现 $B=793999$ 和 $P=1e9+7$ 没有被卡过,以后都用这个。

求出每次加入一个数之后,新的串前缀的 $\text{hash}$ 值即可。

效率: $O(n^2)$ 。

原本想写 $\text{trie}$ 树,但是感觉要用 $\text{map}$ 存下一个节点就是 $n^2log$ 的了,于是还是 $\text{hash}$ 吧。

All in all,打得其实还不错,但是要注意一些细节的东西,而且其实长的题目也不一定就是很难的题目,所以还是最好把题目全读一遍更好。

上一篇:CCPC2019 Harbin Site B.Binary Numbers


下一篇:HBase启动RegionServer时报UnknownHostException错误的解决方法