Contest Info

date 2017.08.17 12:00-17:00

practice link

Solutions

A. Army Formations

题目大意：给出一棵 \(n\leq10^5\) 个点的二叉树，每个点有一个权值 。对于每个点 \(u\)，求 \(ans_u = \sum\limits_{i = 1}^{sz_u}\sum\limits_{j=1}^i v_j\)，也即前缀和的前缀和。其中，\(\{v_j \}\) 是以 \(u\) 为根的子树的所有权值升序排列的序列。

题解：用 splay 启发式合并自下向上计算 \(ans_u\)，那么就只用考虑插入一个 \(a\) 对这个集合的答案的影响：会使得答案增加 \((a+\sum\limits_{x\in S\land x\leq a}x+\sum\limits_{x\in S\land x>a}a)\)。然后就只用维护一下 splay 的子树和与子树大小就行了。启发式合并的时候需要简单的写一下内存回收，就中序遍历一下较小的 splay，把指针扔到一个 vector 里即可。

B. Battlestation Operational

题目大意：算个式子。

题解：

\[ \begin{aligned}\\ &\sum_{i=1}^{n}\sum_{j=1}^{i}\lceil\frac{i}{j}\rceil[\gcd(i,j)=1]\\ =&\sum_{i=1}^{n}\sum_{d|i}\mu(d)\sum_{j=1}^{\frac{i}{d}}\lceil\frac{\frac{i}{d}}{j}\rceil\\ =&\sum_{i=1}^{n}\sum_{d|i}\mu(d)(\frac{i}{d}+\sum_{j=1}^{\frac{i}{d}-1}\sigma(j)) \end{aligned}\\ \]

其中 \(\mu(d)\) 和 \(\sigma(j)\) 可以 \(\mathcal{O}(n)\) 预处理，复杂度 \(\mathcal{O}(n\log n)\) 。

coldwater’s comment

令 \(f(i)=\sum\limits_{j=1}^i\lceil \frac{i}{j} \rceil[\gcd(i,j)=1]\)，令 \(g(i)=\sum\limits_{d|i}f(d)\)，那么有：

\[ \begin{aligned} g(i)&=\sum_{d|i}\sum_{j=1}^d\lceil \frac{d}{j}\rceil [\gcd(d, j)=1]\\ &=\sum_{j=1}^i \lceil\frac{i}{j} \rceil \end{aligned} \]

第二个等号是因为对每个 \(\lceil\frac{i}{j} \rceil\)，令 \(d=\frac{i}{\gcd(i,j)}, j'=\frac{j}{\gcd(i,j)}\)，有 \(\lceil \frac{d}{j'}\rceil\) 作贡献。再由莫比乌斯反演得到，\(f(i)=\sum\limits_{d|i}\mu(d)g(\frac{i}{d})\)。

另外，\(\sum\limits_{i=1}^n\lfloor \frac{n}{i} \rfloor=\sum\limits_{i=1}^n \sigma(i)\)，并且 \(\lfloor \frac{n}{i} \rfloor = \lceil \frac{n-1}{i}\rceil +1\)。

D. Death Podracing

题目大意：长度为 \(L\) 的环上有 \(n\) 个人赛跑，每个人初始位置为 \(d_i(0\leq d_i < L)\)，速度为 \(v_i(|v_i|\leq 10^9)\)。每个人的位置互不相同，速度也互不相同。第 \(i\) 个人的力量值为 \(i\)，当两个人相遇的时候，力量值较小的人会被淘汰。问经过多长时间最后剩下一个人。

题解：我们将这 \(n\) 个人按照 \(d_i\) 排序，用双向链表维护。显然每次相遇只可能发生在相邻的两人之间。我们用一个优先队列维护相邻两人相遇的时间（相对于时刻 \(0\)），每次取出一个事件，然后删除掉一个点即可。

E. Engineering of the Clones

题目大意：给你一个 \(A=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{n}^{r_{n}}\) ，且 \(|r_{i}-r_{j}|\le 1(\forall i, j\in[1,n])\) ，求 \(\frac{1}{A-1}\) 在 \(\prod_{i=1}^{n}p_{i}\) 进制下小数点后的第 \(k\) 位数。

题解：比赛摸鱼害死人，明明想到了的。

记 \(\text{base}=\prod_{i=1}^{n}p_{i},\max=\max\limits_{i=1}^n\{r_i\}\) ，显然有 \(\frac{1}{A-1}=\frac{1}{1-\frac{1}{A}}-1=\sum_{i=1}^{\infty}\frac{1}{A^{i}}\) 。而 \(\displaystyle \frac{1}{A}=\frac{\prod_{i=1}^{n}p_{i}^{[r_{i}<\max]}}{\text{base}^{\max}}\) ，显然有 \(t=\prod_{i=1}^{n}p_{i}^{[r_{i}<\max]}<\text{base}\)，所以 \(\frac{1}{A}\) 在 \(\text{base}\) 进制下为 \(0.\underbrace{0\cdots 0}_{\max-1}t\)。由于题目保证了 \(k<\max^{2}\) ，所以 \(\sum\limits_{i=\max+1}^{\infty}\frac{1}{A^i}\) 对第 \(k\) 位无影响，下证：

显然有 \(\prod_{i=1}^{n}p_{i}^{[r_{i}<\max]}\leq\frac{\text{base}}{2}\) ，故 \[ \begin{aligned} \sum_{i=\max+1}^{\infty}\frac{1}{A^{i}}=&\frac{1}{A^{\max+1}}\cdot\frac{1}{1-\frac{1}{A}}\\ =&\frac{(\prod_{i=1}^{n}p_{i}^{[r_{i}<\max]})^{\max+1}}{\text{base}^{\max(\max+1)}}\cdot\frac{\text{base}^{\max}}{\text{base}^{\max}-\prod_{i=1}^{n}p_{i}^{[r_{i}<\max]}}\\ \le&\frac{1}{2^{\max}\text{base}^{\max^{2}-1}}\\ <&\frac{1}{\text{base}^{\max^{2}-1}}\\ \end{aligned} \]

而观察容易知道， \(\forall i\in[1,\max]\) 的 \(\frac{1}{A^{i}}\) 的各个非零位置是互不相同的，也即每个位置最多只有一个 \(\frac{1}{A^i}\) 有贡献。于是在第 \(k\) 位非零的就只有 \(\displaystyle \frac{1}{A^{\displaystyle \lceil\frac{k}{\max}\rceil}}\) 。所以答案就是 \(\displaystyle \left(\prod_{i=1}^{n}p_{i}^{[r_{i}<\max]}\right)^{\displaystyle \lceil\frac{k}{\max}\rceil}\) 在 \(\text{base}\) 进制下的第 \(\lceil\frac{k}{\max}\rceil\cdot \max-k\) 位。

然后快速幂加上 NTT+CRT 或者拆系数 FFT 就行了。复杂度 \(\mathcal{O}(\max\log \max)\) 。

F. Fleet of the Eternal Throne

题目大意：给你 \(n(n\leq 10^5)\) 个长度总和不超过 \(10^5\) 的字符串 \(\{s_i \}\)。再给你 \(m(1\leq m\leq 100)\) 次询问，每次询问 \((x,y)\)，要求找到串 \(s_x, s_y\) 的最长公共子串 \(sub\)，并且 \(sub\) 是某个 \(s_i\) 的前缀。输出最长长度。

题解：我们对每个串 \(s_i\) 跑一遍 kmp 算法，求出 fail 数组。每次询问的时候，我们对 \(\forall i\in [1, n]\)，都求出 \(f_i[x], f_i[y]\)。其中，\(f_i[j]\) 表示以串 \(s_j\) 作为母串，\(s_i\) 作为模式串，能匹配到的最长的长度。那么当前的答案即为：\(\max\limits_{i=1}^n \min\{f_i[x], f_i[y]\}\)。对于已经求得的 \(f_i[j]\)，我们用 map 存一下即可（其实不存复杂度差不多）。复杂度 \(\mathcal{O}\left(m(|S| + \log m) \right)\)。

（题解的做法）建一个 ac 自动机，然后每次询问两个串 \(s_x, s_y\)，找到它们所有的前缀在自动机上的对应结点所构成的集合，分别设为 \(X, Y\)。答案即为： \(\max\limits_{p\in X, q\in Y} dep[lca_{p, q}]\)。其中，\(lca\) 指的是在 fail 树上的最近公共祖先。也就是求最长的树链的交，类似虚树的构造，我们将所有点按照 dfs 序排序，然后只考虑相邻的属于不同集合的点即可。

（tls 队的做法）广义后缀自动机，然后离线。

G. Galaxy at War

题目大意：略略略

题解：手动打表每个格子 sg 值即可发现整个游戏的 \(sg\) 值为 \(\bigoplus\limits_{x=1}^{n}\bigoplus\limits_{y=1}^{m}[(n+m-x-y)\text{ mod }2=1]w_{x,y}\) ，污染源和冥想都是没有用的。

看了题解才想起来是阶梯博弈，要是早发现了连打表都不用了。

H. Hybrid Crystals

题目大意：略略略

题解：注意到在题目限制下答案是一个区间即可。

I. I am your Father!

题目大意：给出一个\(n\leq10^3\) 个点 \(m\leq10^4\) 条边的边带权的有向图，求以点\(1\) 为根的最大树形图的边权之和，并且要求点 \(n\) 的父亲编号尽可能小。

题解：我们将所有的边权乘以 \(10^4\)，然后将所有从 \(x\) 到 \(n\) 的边的边权再加上 \(10^4-x\)，然后直接跑最大树形图的朱刘算法就行了。得到朱刘算法的结果\(res\)，则最大树形图的边权和为 \(\lfloor\frac{res}{10^4}\rfloor\)，最小的 \(n\) 的父亲编号为 \(10^4-(res\text{ mod }10^4)\)。

K. Killer Names

题目大意：每个人的名字是两个长度为 \(n\) 的串，字符集 \(\mid \Sigma\mid=m\)。要求每个人的名字满足两个串中没有相同的字符。问最多能给多少人命名。

题解：令 \(f_i(1\leq i\leq m)\) 表示恰用 \(i\) 种字符组成一个长度为 \(n\) 的串的方案数。\(f_i = i^n - \sum\limits_{j=1}^{i-1}{i\choose j}\cdot f_j\)，那么答案为：

\[ \sum\limits_{i=1}^m \left(\sum\limits_{j=1}^{m-i} {{m-i}\choose j}\cdot f_j \right)\cdot {m\choose i}\cdot f_i \]

直接 \(\mathcal{O}(nm)\) 计算即可。

Replay and Summary

Replay

W 倒着读题发现题目都好长啊，最后一道题感觉是个推推式子就能做的题，让 Z 去做，Z 说不取模抄板很麻烦待会去写。然后 Z 就开始写 B。写完 B 交了一发 wa 了，再刷新题面发现 zz 的出题人加上了取模，改了之后过了。W 也刷新了一下最后一题的题面，也加上了取模，于是就交给 Z 去做了。

Z 做完 K 交了一发 wa 掉了。W 自己也推了一个式子，上来写，也 wa 掉了。D 和 W 讨论了 A 的做法，觉得就是一个启发式合并平衡树，D 对 splay 比较熟，就接过去写。W 开始静态查 K 的错。一会儿发现忘记乘 1ll，加上之后过了。

D 写完 splay 之后直接 a 了，W 让 Z 读 H 的题意，读完之后两人交流了一下，弄清楚了限制，Z 和 W 都发现类似的题之前做过不止一次，Z 马上写了就过了。W 持续想 F 题，W 和 D 讨论了讨论什么广义后缀自动机、ac 自动机的做法，W 最后决定写一个 kmp，然后 map 记录一下。wa 了一次之后，把动态分配内存改了，然后莫名其妙就过了。

D 发现 I 题就是一个最小树形图，然后第二个限制条件的话通过编码可以实现，然后写了之后 wa 了好几次。Z 本来在做 D，写了一句话就发现算法错了。W 想了想 D 觉得直接用优先队列和链表模拟就好了，开始写。写完之后样例跑不过，就改了代码 ce 了一发，换台电脑看代码（结果 hdu 的 ce 算罚时，下降一名有点亏）。

静态查错找不到错误的 W 决定帮 D 看看 I 的代码，改了改 long long 的输入和一些很细节的东西，随便交了一发莫名其妙的过了。W 开始调试 D 题，调了一会儿找到错改了，也过了。W 和 D 开始摸鱼，Z 看了看 G 题，打了打表，发现是个逗你玩题。W 看着 Z 把这题写了，改了点小错误直接交就过了。

最后还剩一个多小时，剩的三道题中 B 没有什么想法，E 题 Z 觉得可以怎么卷积一下但是复杂度不对，W 和 D 看了 J 题觉得多半是个网络流，然后一直尝试建图，最后也没建出来。

coldwater

这场比赛比较顺，开的题基本上都做出来了。不过最后一个小时没有能够有效利用起来，而且这次的最小割又双叒叕没做出来，还是得系统复习一下网络流和匹配还有分数规划那一块了。

ShinriiTin

这场的题面又臭又长。一开始没有读懂 A 题是什么意思，拿样例画了一下猜到了，然后就想了一下实现的细节，很快就写完 ac 了。然后和 W 讨论了一会儿 F 和 I，我想出了 I 题，然后就开始写。写完 wa 掉了，觉得可能是我瞎改板子的问题，于是权值取负改成求最小，还是 wa。然后 W 提醒我 long long 的输入输出即使在 int 范围内也要 %I64d，否则有的 oj 会出问题，改了交，a掉了。下来之后改了一下一开始的版本，确实有瞎改板子改错的地方，但是改完之后依然不能 ac，再把 long long 的输入输出改掉，求最大树形图的方法也是可以 ac 的。以后一定要注意这个问题。之后就再没有有用的输出了，一直在摸鱼。网络流最小割的建图我们还是很不熟悉，需要加强。

zhongzihao

zzh 擅长想出错解之后写出错误的代码然后发现想错了（不过还好这场最后都 a 掉了）。感觉这段时间写各种数学题收获还是很大， b 题是做过一万遍的莫比乌斯反演很容易就想出来了（不过出题人很坑）， h 也是 51nod 一道原题的弱化版， g 题手动打表 sg 值大概感觉到了出题人在逗比，然后说着“我不敢写啊”就 1a 了。最后 e 题想到了是个卷积，不过我写的式子没法算，还要看看题解是怎么处理的。感觉今天打的还不错。

update: 看题解发现 e 其实比赛时就已经想出来了，但是发神经以为没法算就开始摸鱼了，以后千万不能这样。