2019 CCPC Harbin Onsite

Replay

Xiejiadong:

• Harbin 真的不冷 昼夜温差真的大。
• 延续了出题人一贯卡常的风格吧。
• 比较遗憾的是相对简单的 A 和 B 被过早放弃或者没有过早开出来吧。
• 上来签到题吃了两发罚时，感觉要凉。
• L 题联想到了上海网络赛的字符串，在 hash 的路上一去不复返。
• B 题其实发现了模数的问题，但并没有发现队友题目理解错的问题。
• 最后是 $10$ min 卡了两题的时候已经心如死灰。做好了 Ag 的准备。
• 这个赛季的第一场比赛，没有达到预期。拿到了 Au 也算是有一个交代吧。

Kilo_5723:

Weaver_zhu:

Problem A

Unsolved.

Problem B

Unsolved. (-3)

Problem C

Solved by Weaver_zhu. 04:54:25 (+1)

Problem D

Unsolved.

Problem E

Solved by Xiejiadong && Kilo_5723. 01:54:35 (+1)

题意：每个人手上有一种礼物，每次可以让任意两个人交换礼物，最大化和一开始手上礼物不同的人数量。每个人手上礼物的方式通过给出一些数列以及不断连接他们得到。

题解：给出一些数列以及不断连接他们，可以通过求出每一个数列在最终数列中出现的次数得到每一种礼物在最后的数列中出现的次数。

设 $f[x]$ 表示第 $x$ 个数列在 $s_n$ 中的出现次数，显然 $f[n]=1$ ；

对于第二个操作，由 $x$ 数列和 $y$ 数列连接得到 $i$ 显然，$f[x]+=f[i],f[y]+=f[i]$ 。

而对于第二部分，让任意两个人交换礼物，最大化和一开始手上礼物不同的人数量。

显然如果最多数量的礼物的总数不超过总人数的一般，一定有方案使得每个人获得不同的礼物，而超过一般的只需要通过最多礼物的数量计算就可以得到。

Problem F

Solved by Xiejiadong. 00:26:59 (+1)

题意：从六个字符串中每个字符串各取出一个字母，能不能组成 `harbin` 。

题解：直接统计出每个字符串中每个字母是否出现， $O(6!)$ 枚举每个字母的位置是否成立即可。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 00:34:20 (+)

Problem J

Solved by Weaver_zhu. 00:07:54 (+1)

Problem K

Solved by Kilo_5723. 00:14:44 (+)

Problem L

Solved by Xiejiadong && Kilo_5723. 04:10:11 (+2)

题意：给出每次需要获取的信息， Cache 用 LRU 算法处理，询问对于给定大小的 Cache 是否存在某个状态。

题解：如果把 Cache 的大小设为无穷大。那么可以发现某一个时刻对于特定大小的一个 Cache 的状态，其实就是当前状态的一个前缀。

于是，对于所有的询问建立 Trie ，每次暴力获取每一个状态，在 Trie 上对于所有的状态进行标记就行了。

注意状态可能会重复，可能会有 $0,0,0,\cdots $ 这样的初始状态。