我们的第一场 CCPC，差点就没拿到金牌的哈尔滨旅游

我们队伍组队以后的第一次外出比赛就是2019年的CCPC哈尔滨赛点。

那一年的哈尔滨赛点是浙江大学负责出题的，题目质量方便还是非常不错的。

一点我们自己比赛过程中的花絮

• Harbin真的不冷昼夜温差真的大。
• 比较遗憾的是相对简单的 A 和 B 被过早放弃或者没有过早开出来吧。
• 上来签到题吃了两发罚时，感觉要凉。
• L 题联想到了上海网络赛的字符串，在 hash 的路上一去不复返。
• B 题其实发现了模数的问题，但并没有发现队友题目理解错的问题。
• 最后是 10 min 卡了两题的时候已经心如死灰。做好了 Ag 的准备。
• 长久的训练还是有效果的，至少在队伍抗压能力上有所体现。最后一个小时在十分压抑的情况下还是挽救了回来，实则不易。
• 热身赛一个队友被我们吐槽bash编译+重定向没有codeblocks f9和复制黏贴输入数据好用，结果正赛样例就粘不上去了。真香
• 热身赛因为多校补题成功捧杯（第一），正式赛没了。

比赛链接

http://codeforces.com/gym/102394

下文有部分题目过于简单就不给出文字题解了。

Problem A

题意：要求给方格染色，需要满足一些要求，要求形如 "区间 [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

赛场上没有过，赛后也懒得补题。

Problem C

大模拟，实现分数类+好好读题。

Problem E

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

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

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

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

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

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

Problem F

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

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

Problem I

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

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

Problem J

温暖的签到题。

Problem K

温暖的签到题。

Problem L

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

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

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

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