Contest Info

date 2017.08.08 12:00-17:00

practice link

Solutions

A. Rikka with Candies

题目大意：给出两个数列 \(\{a_n \}\) 和 \(\{b_m \}\)。 \(q\) 次询问，每次询问给出 \(k\)，要求输出有多少对 \((i, j)\) 满足 \(a_i\equiv k(\text{mod }b_j)\)。保证两个数列内部没有相等的数字。\(1\leq n, m, q, a_i, b_j\leq 50000, 0\leq k< \text{max }b_j\)。每次只用输出答案对 \(2\) 取模。

题解：模 \(2\) 意义下的加法就是异或运算，这提示我们用 bitset。我们用 \(A\) 的各位记录数列 \(\{a_n \}\) 的出现。对于每一个 \(b_j\)，我们把 \(A\) 中的区间 \([0, b_j), [b_j, 2b_j),...\) 全部加（异或）到 \(ans\) 的 \([0, b_j)\) 上去。那么 \(ans\) 的第 \(k\) 位就是询问为 \(k\) 时的答案。

提取区间 \([l, r)\) 的操作我们需要手写 bitset。通过先向左移动右端点使区间长度为 \(32\) 倍数，然后通过预处理的 \(A_i = A << i\) 来快速实现。总的复杂度为 \(\displaystyle \mathcal{O}\left(\sum_{i=1}^m \frac{\text{max }a}{b_i}\times (32 + \frac{b_i}{32})\right)=\mathcal{O}(\frac{m\cdot \text{max }a}{32})\)。

B. Rikka with String

题目大意：给定 \(n\) 个 \(01\) 串 \(\{s_i \}\)。问有多少个长度为 \(2L\) 的反对称串包含给定的 \(n\) 个串为子串。反对称串定义为 \(s_i \neq s_{|s|-i+1}\) 对 \(\forall i \in [1, |s|]\)（下标从 \(1\) 开始）。

题解：我们暴力枚举横跨位置 \(L,L+1\) 的部分，计算出能包含的串的集合。这里的复杂度是 \(\mathcal{O}(\mathrm{max}|s_i|2^{\mathrm{max}|s_i|})\)。然后我们发现，剩余的串在位置 \([L+1, 2L]\) 中匹配，是可以转换到 \([1, L]\) 中去计算的。我们把这些串以及转换之后的串插入到一个 ac 自动机中。

然后对于之前暴力枚举的部分，我们找到它在自动机中的对应结点，初始化 dp 值。然后外层枚举长度转移 dp 值即可。总复杂度 \(\mathcal{O}(\mathrm{max}|s_i|2^{\mathrm{max}|s_i|}+2^nL\sum |s_i|)\)。

D. Rikka with Rock-paper-scissors

题目大意：两个人玩 \(n\) 盘石头剪刀布，设 \(A\) 赢了 \(a\) 盘， \(B\) 赢了 \(b\) 盘，则这一次游戏的得分为 \(gcd(a, b)\) 。问期望得分乘以 \(3^{2n}\) 。

题解：显然答案即为所有情况的得分和。不考虑 \(ab=0\) 的情况：

\[ \begin{aligned}\\ ans&=\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}\frac{n!}{i!j!(n-i-j)!}\cdot3^{i}\cdot3^{j}\cdot3^{n-i-j}gcd(i,j)\\ &=n!3^{n}\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}\frac{gcd(i,j)}{i!j!(n-i-j)!}\\ &=n!3^{n}\sum_{d=1}^{n-1}d\sum_{i=1}^{\lfloor\frac{n-1}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{d}\rfloor-i}\frac{[gcd(i,j)=1]}{(id)!(jd)!(n-id-jd)!}\\ 记 S(d)&=\sum_{i=1}^{\lfloor\frac{n-1}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{d}\rfloor-i}\frac{1}{(id)!(jd)!(n-id-jd)!}\\ 则ans&=n!3^{n}\sum_{d=1}^{n-1}d\sum_{d|u}\mu(\frac{u}{d})S(u)\\ &=n!3^{n}\sum_{u=1}^{n-1}S(u)\sum_{d|u}d\mu(\frac{u}{d})\\ &=n!3^{n}\sum_{u=1}^{n-1}\phi(u)S(u)\\ &注意到S(u)可以写成\\ S(u)&=\sum_{i=1}^{\lfloor\frac{n-1}{u}\rfloor}\frac{1}{(n-iu)!}\sum_{j=1}^{i-1}\frac{1}{(ju)!}\cdot\frac{1}{[(i-j)u]!}\\ \end{aligned}\\ \]

这就是常见的卷积形式了，可以 \(FFT\) 加速，复杂度为 \(\mathcal{O}(\sum_{u=1}^{n-1}\frac{n}{u}\log\frac{n}{u})=\mathcal{O}(n\log^2{n})\) 。 \(ab=0\) 的情况容易特殊处理。

由于本题的质数不是 \(NTT\) 模数，具体实现时需要使用拆系数 \(FFT\) 。

F. Rikka with Graph

题目大意：一个 \(n\) 个点 \(m\) 条边的无向图 \(G\)。\(\text{dist}(i, j)\) 定义为 \(i,j\) 的最短路，如果不连通令 \(\text{dist}(i,j)=n\)。定义 \(w_G=\sum_{i=1}^n\sum_{j=1}^n\text{dist}(i,j)\)。现在给定 \(n,m\)，要你给一个 \(n\) 个点的图连不超过 \(m\) 条无向边，最小化 \(w_G\)。

题解：我们贪心地往里面加边。

如果 \(m\leq n-1\)，那么肯定是连成一个菊花图（这样才能使得尽可能多的点连通，并且内部的距离和尽可能小），然后剩余一些孤立点。那么此时的答案为：

\[ 2m+{m\choose 2}\cdot 2\cdot 2+{n-m-1\choose 2}\cdot 2n + (m+1)(n-m-1)\cdot 2n \]

否则 \(n-1 < m\)。这里有一个 trick，要先把 \(m\) 与 \(n\choose 2\) 取 \(\text{min}\)。那么此时一定是先用 \(n-1\) 条边将图连成一个菊花，然后每加一条边距离减少 \(1\)。此时答案为：

\[ 2(n-1)+{n-1\choose 2}\cdot 2\cdot 2-(m-n+1)\cdot 2 \]

H. Rikka with Subset

题目大意：有一个长度为 \(n\leq50\) 的整数数列 \(\{A_n\}(0\leq A_i \leq m)\)，\(1\leq\sum\limits_{i=1}^{n}A_i=m\leq10^4\)。给出一个长度为 \(m+1\) 的数组 \(B\)，\(B_i\) 表示 \(A\) 的子集中和为 \(i\) 的个数，\(0\leq i\leq m\)，\(0\leq B_i \leq 2^n\)。要求根据 \(B\) 数组还原原来的数列 \(\{A_n\}\)，输出字典序最小的答案。

题解：先处理掉 \(A_i=0\) 的情况，显然 \(2^k=B_0\)，\(k\) 为 \(A\) 中 \(0\) 的个数，之后将 \(B_i\) 都除以 \(B_0\) 就得到了 \(A\) 去掉所有 \(0\) 之后的信息。之后找到 \(B\) 中第一个 \(B_i>0(i>0)\) 的 \(i\)，说明 \(A\) 中有 \(B_i\) 个 \(i\)。然后用这 \(i\) 个 \(B_i\) 做一下背包，从 \(B\) 中减去只由它们组成的子集的信息。然后再找到 \(B\) 中第一个不为零的位置 \(j\)，说明 \(A\) 中有 \(j\) 个 \(B_j\)，再继续做背包，算出只由这些已经确定的数组成的子集的信息，以此类推。最终其实只做了一次完整的背包，时间复杂度为 \(\mathcal{O}(nm)\)。

I. Rikka with Number

题目大意：定义一个 \(d\) 进制数是好的，当且仅当它的各位数字是 \([0, d-1]\) 的一个排列。定义一个十进制数是好的，当且仅当它在某个进制下是好的。求十进制下 \([L,R]\) 中的好数个数。

题解：考虑对 \([0,R]\) 求解，容易发现好数随着进制数增加而增大，所以我们只需要特殊处理 \([0,R]\) 中不能取到全部好数的进制，更小进制的好数则一定能全部取到，且容易计算个数。为寻找这样不能全取的进制，容易发现 \(R\) 在这种进制下的位数一定和进制相等，这时我们可以使用 \(log\) 来大致估计一下进制上限，再暴力地往下找到准确的位数，当然也有可能找不到位数和进制相等的情况，这时显然所有的进制都能完全取到。找到这样的进制以后，就是一个简单的数位 dp 问题了，不用多说。

K. Rikka with Competition

题目大意：\(n\) 个人参加摔 ♂ 跤比赛，力量值分别为 \(a_i\)。如果 \(i,j\) 两人摔 ♂ 跤，结果与 \(|a_i-a_j|\) 相关。如果 \(|a_i - a_j|>K\)，那么力量较大的人获胜。否则双方都有可能获胜。现在不断随意选择两人进行淘汰赛，\(n-1\) 场比赛之后决出圣 ♂ 者。问一共有多少人有机会成为圣 ♂ 者。

题解：从小到大排序。从后往前连续的一段差值不大于 \(K\) 的人都有机会获胜，一旦出现大于 \(K\)，那么更前的人都不可能获胜。

Replay and Summary

Replay

W 倒着读题先看了 K，感觉不会啊。再看了看榜怎么都有人 a 了呢，仔细一读发现排个序瞎搞一下就能做了。

Z 在寻找属于自己的数学题，然后初步感觉 A D I 都是他的，就慢慢开始想。W 和 D 开始讨论 F，画了画图感觉有个最优的加边方案，写出式子也很快过了。

W 和 D 又打开 H，两人讨论了一下觉得是暴力背包，也过了。然后二人开始讨论 B，Z 还是感觉 A 题是一个怎么找到取模性质的数学题，还在继续刚。

比赛从这里开始就陷入江局了。W 和 D 一开始就没有想清楚 B 题的做法，只是有一个大概的思路，然后就开始写。写之前二人还不断甩锅都想对方写，最后 W 决定自己写，然后让 D 在旁辅助。因为没有想清楚 B 题，所以状态函数改了又改，转移也改了又改，边界也没有处理清楚。

Z 也发现 A 题没有什么好的想法，看了看 I 觉得大力暴力就能做，就开始写。接下来的两个小时 B 题不断经历 mle 和 tle，I 题也一直 TLE 和 wa。

终于最后 04:35 的时候 Z 瞎改了一个 I 的参数就 a 了。与此同时 W 做的 B 题也修改了一个小地方提交，也 a 了。看着这两题分别 -11 和 -10，非常感动。最后 24min 一直在优化常数提交 A 题，最后在结束前修改参数提交了 4 发，都 tle 了。

（下来之后 D 把 A 题 tle 的代码一交就过了，应该是比赛最后阶段评测机性能比较慢。 Z 看了一下 D 的题解，发现也想到了题解的最后一步，I 耗时太多，没时间写了。）

coldwater

这场比赛题目难度相较之前几场难，一开始做题的时候就已经感觉到了。做完三道签到题的时候，已经是过去一小时了。而且 H 还因为行末空格 PE 了一次，又看到我校其他队伍领先我们太多，开始出现了一些紧张的情绪。

D 给我讲 B 的时候，我其实有一些拒绝，觉得他自己一个人想就好了，我个人比较想去做过得比较多的 A 题。但是听他讲完之后觉得跟之前做过的题很像，只是多了一个暴力枚举的过程。B 没有想清楚就开始写，卡了整整两个小时。最后我冷静下来从头审视了一遍算法，改了不少地方才过掉。

作为队长没有能调整好大家的情绪，反而是自己很紧张，有点说不过去。希望我们队能尽快地成长起来吧 ( ˘･з･)。

ShinriiTin

大家好，我是锅王，赛后我们来冷静地分析一下锅出现的原因。本场比赛我有两口大锅，A 没 a 掉，以及 B 僵持太久。

先说 B 吧，比赛开始后一小时多，我想到了大概的做法，和字符串专场时 W 过掉，我不停 wa 的某题做法类似。于是我马上给 W 讲，由于我当时没有想的太清楚，而且 W 莫名很慌，转述出现了一些问题，并且在讨论的过程中问题不断积累。又由于我之前一直 wa 字符串专场那题，怂得不敢写，于是甩锅给 W 让他强行开写。这导致了我俩之后浪费了 3h+ 去写加不断修补算法的漏洞，也导致了我们没有太多时间去研究这一场大多数人都 a 掉了的 A。

A 题最后半个小时推了一个 bitset 的做法，但是因为最后阶段 hdu 的评测机状态非常差，而且写出来常数不是特别优秀，直到比赛最后一刻也没能通过。赛后，重新提交了一次就通过了，可能早点去做 A 也是可以卡过去的。

今天的锅，我要承担大部分的责任，我应该多花一点时间思考一下 B 的算法。B 想清楚之后并不难写，而且不需要输出方案写填表式的 dp 我也不会出问题，要大胆去写。而且我一个人来搞 B 的话，可以让 W 去思考其他的题，W 比我更加熟悉 bitset，加上比赛前期和中期 hdu 的评测机还不算很爆炸， W 也应该能过掉 A 。这次比赛还让我明白了，在比赛中，有意义的讨论是值得的，但是像这样越来越跑偏的讨论就是单纯的浪费时间，应该及时停下来分别重新整理思路。弊队在算 rating 的比赛中总是会莫名其妙的在比赛开始的时候就异常紧张，以后必须得要调整好心态，才能避免锅的出现。

zhongzihao

这场比赛让人感觉很亏， A 题开始一直搞错了方向，以为是一个式子题，结果是 bitset 压位，就很江硬。然后看题解发现题解的方法也是想过的，开始没想到 bitset 觉得没法做，之后队友狂 t 的时候也没能及时想到之前的方法，结果成为为数不多的没过 A 题的队，很惨。 A 题想不出来以后就开始刚 I ，发现算法非常非常水，虽然已经预感到了实现起来很麻烦，不过我还是勇敢地去写了。然后就一直 wa 和 tle ，还好最后 a 掉了，总算没有 0a。赛后看了看 D 的题解，发现式子也推的差不多了，比赛时实在没时间写了。

总体来说最大的问题是在 A 题上浪费了太多时间，其次是 I 题写的时候没有想清楚，开始二分常数太大，最后 a 的也很玄学。还有比赛大约一个小时就一直处于很慌的状态，觉得签到题罚时落后了，这样是很没有必要的（毕竟最后半小时还 a 了两道题）。比赛经验还不够，以后还要锻炼好自己的心脏。