2019 CCPC Harbin Onsite

Replay

Xiejiadong:

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

Kilo_5723:

• 热身赛捧杯，正式赛没了。
• “没有达到预期”或成传统艺能。
• 第一次作为嘴巴选手上场 真爽。
• 博弈把游戏玩出来以为有了，其实只是这道题最简单的一部分。
• 跟队友讲了 L 正解，却被两个队友一起叉掉了 超记仇。
• B 题读出了一道意思完全不同的新题，不仅帮周围队伍发现了 $100~000~007$，还抢了最后一小时的大模拟上机时间 深藏功与名。

Weaver_zhu:

• 热身赛队友吐槽bash编译+重定向没有codeblocks f9和复制黏贴输入数据好用，结果正赛样例就粘不上去了。真香
• A 听到了隔壁大嗓门的正解，结果两个队都没搞出来。。
• 看似大模拟实则英语题，至少在三个题意之间反复横跳，最后15min题意可能还有问题，好在正解是最好写的一种，最后5min抢救成功

Problem A

Upsolved by Xiejiadong.

题意：要求给方格染色，需要满足一些要求，要求形如 "区间 $[l,r]$ 内被染色方块数量 $\ge k$" 或者 "区间 $[l,r]$ 以外被染色方块数量 $\ge k$" 求染色的最小方块数量。

题解：显然第一部分要求可以利用前缀和转化成差分约束形式，而对于第二部分，可以通过二分答案确定总的染色数量，那么区间以外可以转换成区间以内，同样可以转换成差分约束。

• "区间 $[l,r]$ 内被染色方块数量 $\ge k$" 转换成 $sum_{l-1}-sum_r\le -k$ ；

• "区间 $[l,r]$ 以外被染色方块数量 $\ge k$" 转换成 ¥sum_{r}-sum_{l-1}\le mid-k¥ 其中 $mid$ 由确定二分答案；

除此以外还需要的一些限制是：

• $0\le sum_i-sum_{i-1}\le 1(1\le i\le n)$ ；

• $mid\le sum_n-sum_0\le mid$ 。

对于差分约束部分用 SPFA 判断是否存在负环即可。

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 (+)

题意：对于一个排列，已知所有前 $i$ 位的最大值和最小值之差，求有多少种可能的不同排列。

题解：如果某一步后最大值最小值之差超过 $n$ 或变小显然无解，否则每一次增加的位置会有 $2$ 种可能，增加上限或者降低下限，同时原限制和当前限制之间的所有数变得可选，之后剩下的位置在剩下的可选数中选一个。

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 $ 这样的初始状态。