2017 Multi-University Training Contest - Team 4

Contest Info

date: 2017.08.03 12:00-17:00

practice link

Solutions

A. Big Integer

upsolved by skywalkert


skywalkert’s solution

所求即选出一些数字凑成可重集排列的方案数,可以直接使用指数型生成函数进行乘积。

最终数字的长度在 \(1\)\((k - 1) n\) 之间,由于模数的欧拉函数是 \(2^{17}\) 的倍数,故可以使用 Number Theoretic Transform 求得相应生成函数的点值(频谱),否则需要使用 Fast Fourier Transform 。

每次操作会修改乘积中的某个生成函数,可以直接根据 Discrete Fourier Transform 的公式修改,不同采样点之间互不影响,对于每个采样点需要维护所有生成函数的点值之积,为了能够在模意义下增删数字,需要统计 \(0\) 的数量和非 \(0\) 的乘积。

最终要计算的贡献可以在 Inverse Discrete Fourier Transform 之前求和,再 Inverse Discrete Fourier Transform ,总时间复杂度 \(\mathcal{O}(k L \log L + m L)\) ,其中 \(L\) 表示序列的长度(采样点的数量), \(L\) 为大于 \((k - 1) n\) 的最小 \(2\) 的幂次。

B. Classic Quotation

solved by braveTester, upsolved by none


braveTester’s solution

首先期望是唬人的,期望后面的两个因子其实就是概率,所以只要求所有情况的出现次数之和。

\(T\)\(S'\) 中的匹配有两种情况,一种是本来就出现在 \(S\) 中,另一种是因为拼接后出现在 \(S'\) 中。

考虑 \(L\) 左边,且本来出现在 \(S\) 中的匹配会对该次询问答案造成多少贡献。设其右端点下标为 \(i\),容易发现贡献为 \((L - i + 1) \times (N - R + 1) = (N - i + 1 - (N - L)) \times (N - R + 1)\)

因此令 \(\text{leftSum}[i] := \sum_{1 \le j \le i} (N - j + 1)[S[j - |T| + 1\dots j] = T]\)\(\text{leftCnt}[i] := \sum_{1 \le j \le i} [S[j - |T| + 1\dots j] = T]\),则 \(L\) 左边本来出现在 \(S\) 中的匹配对答案的总贡献为 \((\text{leftSum}[L] - (N - L)\text{leftCnt}[L]) \times (N - R + 1)\)

用 KMP 扫一遍就可以得出 \(\text{letSum}\)\(\text{leftCnt}\)。将 \(S\)\(T\) 反转得到 \(S^\sim\)\(T^\sim\),对其做同样事情可以得到 \(\text{rightSum}\)\(\text{rightCnt}\),这里 \(\text{rightSum}[i] := \sum_{1 \le j \le i} (N - j + 1)[S^\sim[j - |T^\sim| + 1\dots j] = T^\sim]\)\(\text{rightCnt}\) 类似。

对于跨越的部分,枚举 \(S[1\dots L]\) 经过 \(T\) 的 KMP 所处的位置 \(i\),以及 \(S^\sim[1\dots N + 1 - R]\) 经过 \(T^\sim\) 的 KMP 所处的位置 \(j\),每次用 \(O(|T|)\) 的时间将跨越的匹配数填入矩阵 \(A[i][j]\)。该部分复杂度 \(O(|T|^3)\)

\(\text{leftPos}[i]\)\(S[1\dots i]\) 在经过 \(T\) 的 KMP 后所处的位置,\(\text{rightPos}[j]\) 同理,则跨越的部分对答案的贡献可以写为 \[ \sum_{i \le L\\j \ge R} A[\text{leftPos}[i]][\text{rightPos}[j]] = \text{leftVec}[L] \times (A \times \text{rightVec}[R])。 \]

所以只要预处理 \(\text{leftVec}\)\(A \times \text{rightVec}\) 即可做到每次查询复杂度 \(O(|T|)\)

总复杂度 \(O(mk + m^3)\)

赛后轩哥告诉我不用把矩阵算出来…直接对每个位置用 \(O(|T|)\) 的时间预处理以其为右/左端点所能达到的前缀/后缀向量,求个前缀/后缀和,询问的时候 \(O(|T|)\)\(L\) 的前缀和向量和 \(R\) 的后缀和向量卷一下就行了…复杂度 \(O(mk)\)

C. Counting Divisors

solved by skywalkert, upsolved by none


skywalkert’s solution

采用线性筛并行化的技巧,先将不超过 \(\sqrt{\max(R)}\) 的质数预处理出来,枚举每个质数在 \([L, R]\) 中的倍数进行质因数分解,最后再检查大质因子即可,复杂度与 \([L, R]\) 中质因子数量之和有关,当近似认为相同质因子不多次统计时利用不等式放缩的技巧可以估计单次求解的复杂度约为 \(\mathcal{O}\left(\frac{\sqrt{R}}{\log R} + (R - L) \log \log R\right)\)

D. Dirt Ratio

solved by skywalkert, upsolved by none


skywalker’s solution

二分答案,检查答案是否小于等于 \(k\) ,则有 \(\frac{\text{size}}{\text{length}} \leq k\) ,也即 \(\text{size} - k \cdot \text{length} \leq 0\) ,将贡献分布到每个元素上即每种数字最后一个出现位置贡献 \(1 - k\) ,其他位置贡献 \(-k\) ,枚举右端点,维护对应左端点的答案,拿个数据结构完成前缀区间修改、前缀区间最小值查询即可。

E. Lazy Running

solved by skywalkert, upsolved by none


skywalkert’s solution

找一个必然可以经过的环,例如起点的邻边来回各走一次,设长度为 \(m\) ,则对于任意一种长度为 \(k\) 的路径,都可以构造出长度为 \(k, k + m, k + 2 m, \cdots\) 的路径,这些路径长度在模 \(m\) 意义下同余,对于路径长度同余的路径,显然只需要知道最短的长度即可构造出所有对应长度的路径。

考虑从起点出发到达某个点的路径,枚举接下来走到哪即可完成模意义下路径到路径的转移,可以使用最短路实现相应长度的求解,最后枚举答案在模 \(m\) 意义下的长度是多少即可。

F. Logical Chain

upsolved by skywalkert


skywalkert’s solution

用 bitset 维护图的连通性以及检测强连通分量时已经走过的点集,则可以跳跃过无用后继边的枚举,从而使检测强连通分量的算法做到 \(\mathcal{O}\left(n + \frac{n^2}{w}\right)\) ,其中 \(w\) 是评测机的位长。

不需要进一步优化,对于每个询问直接暴力即可通过此题。

G. Matching In Multiplication

solved by skywalkert, upsolved by none


skywalkert’s solution

如果存在度数不为 \(2\) 的点,但是存在完美匹配,那么一定存在度数为 \(1\) 的点,点一定来自右部点集,其直连的点度数恰好为 \(2\) 并且要与该点匹配,另外一条边同时也失去效用。按照上述方法剔除无用边,当图中不存在度数为 \(1\) 的点时,所有点的度数一定均为 \(2\) ,这意味着整个图是许多个环,每个环只有两种可能的完美匹配,遍历一下即可。

H. Phone Call

solved by skywalkert, upsolved by none


skywalkert’s solution

沿用 Kruskal 算法思想,将边按权值排序后依次加入,所需要加的边至多只有两条路径上的边与一条连接这两条路径的边,维护点集连通性的同时可以维护最小生成树的权值。为了避免重复枚举一条树边,使用另外一个并查集进行树上缩点的操作,便于在每条跳往根的路径上快速跨越过已经枚举过的边。

I. Questionnaire

solved by braveTester, upsolved by none


braveTester’s solution

签到题。

\(2\) 分组一定有解,选多的那边即可,一样多的话随意。

J. Security Check

upsolved by skywalkert


skywalkert’s solution

\(f(i, j)\) 表示检查 \(A_1, A_2, \cdots, A_i\)\(B_1, B_2, \cdots, B_j\) 的最小代价,对于 \(|A_i - B_j| > k\) 的情况,一定尽量同时检查,即 \(f(i, j) = f(i - 1, j - 1) + 1\) ,否则从未检查的人中选一个代价最小的,即 \(f(i, j) = \min(f(i - 1, j), f(i, j - 1)) + 1\) ,其中 \(f(0, 0) = 0, f(0, i) = f(i, 0) = i\)

考虑到 \(|A_i - B_j| > k\) 的状态比较多,而且都能规约到某个满足 \(|A_{i'} - B_{j'}| \leq k\) 的状态 \(f(i', j')\) 上,故考虑只维护满足 \(|A_i - B_j| \leq k\)\(f(i, j)\)

为了便于查找 \(|A_i - B_j| > k\) 的状态值,维护每个斜线上最近一次被维护的状态值及其位置,不妨设为 \(f(x, y) = v\) ,则有 \(f(x + p, y + p) = v + p\) ,也可以直接在斜线上记录 \(f(x, y) - x\) 的值。

时间复杂度 \(\mathcal{O}(n k)\) 。这里不需要将同一行的状态基数排序,而是枚举每一行后对状态进行记忆化搜索,这样还是可以保证维护的信息是最近一次的内容。

K. Time To Get Up

solved by chitanda, upsolved by none


chitanda’s solution

根据特征判断一下数字即可。

L. Wavel Sequence

solved by chitanda, upsolved by none


chitanda’s solution

\(f[0/1][i][j]\) 表示子序列最后两个数分别是 \(a[i]\)\(b[j]\) ,并且当前是上升/下降阶段。

那么若 \(a[i]=b[j]\)\(f[0/1][i][j]=\sum_{i'<i} \sum_{j'<j} f[1/0][i'][j']\),其中 \(a[i']\)\(a[i]\) 的关系满足上升/下降关系。

\(g[0/1][i][j]=\sum_{k=1}^{j}f[0/1][i][k]\) ,那么 \(f[0/1][i][j]=\sum_{i'<i} g[1/0][i'][j-1]\) 并且 \(a[i']\)\(a[i]\) 的关系满足上升/下降关系。

\(c[0/1][j][a[i]]=g[0/1][i][j]\) ,并用树状数组维护,那么 \(f[0/1][i][j]\) 的值可以通过查询树状数组来得到。这样复杂度是 \(O(nm\log 2000)\)

题解的做法是 \(O(nm)\) 的。

考虑最初始的 dp 方程:\(f[0/1][i][j]=\sum_{i'<i} \sum_{j'<j} f[1/0][i'][j']\),其中 \(b[j']\)\(a[i]\) 的关系满足上升/下降关系。

那么,令 \(g[0/1][i][j] = \sum_{k=1}^{i}f[0/1][k][j]\) ,在依次计算 \(f[0/1][i][j]\) 的时候,累加所有 \(b[j]\)\(a[i]\) 的关系满足上升/下降关系的 \(g[1/0][i-1][j]\)

M. Yuno And Claris

upsolved by chitanda, skywalkert


chitanda’s solution

对序列和权值分别分块,b[i][j] 表示前 j 块序列里权值在第 i 块里的数量,c[i][j] 表示前 j 块里权值为 i 的数量。

对于同一个块内的序列,用并查集维护相等的值,并用个数组将权值映射到集合。考虑修改,两个边界区间可以直接重构,而对于中间的区间,将 x 和 y 两个并查集合并即可。修改 b 和 c 数组也很容易。

对于询问,对于边界区间,用一个打标记的数组 tb 和 tc 维护,tb[i] 表示权值在第 i 块里的数量,tc[i] 表示权值为 i 的数量。

然后枚举答案所在权值块,找到块后,枚举块内权值,即可找到答案。

标解如果要合并两个集合,直接暴力重构整个块,可以证明重构次数为 \(O(n+m)\) ,这样可以不用并查集,复杂度更优。

Replay and Summary

Replay

这次终于没人迟到了。

L 发现 09 是签到题,H 发现 11 是签到题,相继过了。

大家开始看别的题,T 和 H 讨论了一下 13,之后 T 发现 03 是水题,马上就切了。

(L 注:今天 H 和 T 开场十分兴奋,不时发出迷 ♂ 之声音。)

然后是罪恶的开端:H 开始敲 13。期间 L 一直在读题发现看上去都是糖题,并向 T 传达题意。L 和 T 说了下 05 后 T 秒会,并上来切了。

H 继续敲 13,距开始敲过了一个半小时后终于写完,提交后 TLE 了,遂弃。

期间 L 和 T 发现 08 是个并查集 + Kruskal 最小生成树,L 最开始还不会并查集维护,T 一语道破天机,于是握了个题。

L 发现 02 是个字符串水题,为了不至于上场挂,于是开始在纸上想架构。

T 上来敲 08,先是 TLE 了,L 提示如果并查集连的不对自己成环了就会 TLE(因为前几天 L 自己补题的时候刚犯过这个错误…)。T 改了一会后过了。期间 H 开始想 04 和 12。

L 架构想的差不多了,于是开始敲 02。期间 T 发现 07 稍微推一推也是个水题。

L 敲完了之后不太有把握,决定静态读一遍,于是 T 开始敲 07。期间 L 发现了几处小错。

T 的 07 没交过,L 继续写 02,把错改了编译过后一发入魂,十分开心。T 上来改了改 07 后也过了。

H 开始敲 12,很快写完后 TLE 了,又优化了下常数还是 TLE。

在这个漫长的过程中,L 看着被板刷的 04 十分焦心,于是尝试二分乱搞,不一会儿搞出了个动态维护序列的做法,跟 T 说了之后,T 提示只要线段树。

此时时间还剩大概 40min,L 怕自己写不出来,于是跟 T 详细说了下 04 的思路,然后借口去修空调遁走。T 看了看想了想,果然中计,认为是个水题,遂撸起袖子自己上。

T 上来写 04,TLE 了几发之后不负众望过了。最后 15min T 开始帮 H 继续优化 12 的常数,优化了几次,在 L 某次刷榜 ??? 的发现敝队突然多了一题时候,偶然发现终于卡过了。

最后十分钟 H 开始疯狂小改然后提交 13,最终没有通过。

braveTester

今天的贡献非常少,只写了一个签到题和一个水字符串题,赛后还发现自己最后一步想麻烦了…

身为读题小能手,前 50min 一直读题并向队友翻译,最后成功助攻 04,比赛节奏还是可以的。

队友们都好强啊…自己什么时候能做个有用的腿部挂件啊…

chitanda

今天的贡献非常少,只写了一个签到题和一个复杂度不对最后靠 tls 才卡过去的 DP。

一开始写 13 是一个非常严重的决策失误,浪费的一个多小时机时和想题时间导致做题节奏开始崩,还好 TLE 之后就放弃了。

之后想 04 也是想了很久没想出来,12 只想到了带 \(\log\) 的做法,说明自己的水平还差得远。

skywalkert

不该坑队友做 13 ,卡 04 很尴尬 ԾㅂԾ ,搞 07 之前大概推了下 01 ,没想清楚后面也没继续想(还好没做,有个小 trick ), 06 一眼 bitset ,还以为出题人有什么高端技巧所以准备放后面想想,要不是有一堆套路题续命今天就要被踩啦 /(ㄒoㄒ)/~~