EOJ Monthly 2017.12 题解

ultmaster edited 7 年，4 月前

A.

Prepared by kblack.

计算每一个点数模 $p$ 能达到的概率，直接暴力比较即可。

B.

Prepared by kblack.

虽然限制只能走马步，但我们很容易意识到在足够大的棋盘（例如象棋棋盘）上，马可以达到任何位置。事实上通过简单的验证，可以发现这一大小的下界是 $3\times 4$。

于是对于所有 $\ge 3\times 4$ 的棋盘，我们可以断言所有砖之间可以互相到达，此时答案为 $(\genfrac{}{}{0ex}{}{nm}{2})$。

当棋盘大小为 $3\times 3$ 时，通过简单的模拟可以发现外围的 $8$ 块砖可以互相到达，此时答案为 $(\genfrac{}{}{0ex}{}{8}{2})$。

当棋盘大小为 $2\times n$ 时，我们发现不同奇偶不同的行/列交替可达，此时有 2 组 $\lfloor n/2\rfloor$ 的联通块与两组 $n-\lfloor n/2\rfloor$ 的联通块，答案为 $2\times (\genfrac{}{}{0ex}{}{\lfloor n/2\rfloor }{2})+2\times (\genfrac{}{}{0ex}{}{n-\lfloor n/2\rfloor }{2})$。

当棋盘大小为 $1\times n$ 时，没有合法的马步，此时答案为 $0$。

注意答案可能超过 $2147483647$，需要使用 long long 类型。

C.

Prepared by ultmaster.

我们可以先考虑字符串有序的情况，比如是 aaabcc，我们只要将字符串右移 3 位，变成 bccaaa，就做完了。那么对于无序的情况，我们可以通过排序让它有序，做完之后再排回去。

显然最多的字母出现次数大于一半的情况是不行的。否则就将每个字母的位置和字母绑定一下，按字母序对结构体进行排序。然后右移「出现最多的字母出现次数」位，再排回来就可以了。时间复杂度 $O(n\log n)$。

也可以对 26 个字母进行遍历，把每个字母填到合适的位置。具体细节留给读者思考。

D.

Prepared by infiniteee.

又到了喜闻乐见的套路题时刻。

一个很显然的想法是对左边的 $n$ 轮和右边个质因数之间建边，便是一个二分图，就是做匹配。但是很遗憾，朴素的匹配是错误的，因为存在一个顺序问题。正确的做法是有一次如果不能找到匹配，就直接跳出。这是一个非常经典的问题，具体证明可以自行搜索 BZOJ 锦囊问题。

求素数可以使用朴素的 $O(\sqrt{n})$ 做法，用素数筛筛过头了可能反而会超时。因为素数不多，但素数的范围比较大，如果直接照抄板子每次都 memset 可能会超时，可以打时间戳，或者直接对质数进行离散化。

也可以二分答案直接跑二分图，姿势好一点也能过。

E.

Prepared by kblack.

Easy 部分可以简单的用 $dp[i][j][k]$: 买个 $i$ 根，最后一天买 $j$ 根，买 $j$ 根已经 $k$ 天来实现。朴素转移时间复杂度 $O(n^4)$ 足够通过，可是没人做。

可以发现，购买棒棒糖，相当于是在做最大容量为 $n$，物品大小为 $x,x+1,\dots ,n$ 的 $k$ 重背包，恰好使用 $m$ 元的方案数即是背包容量为 $m$ 的方案数，多重背包 $O(n^{2}k)$ 的复杂度明显是我们无法接受的，考虑使用生成函数优化背包。

$\prod _{i=x}^n(1+x^i+x^{2i}+\dots +x^{(k-1)i})$
$=\prod _{i=x}^n\frac{1-x^{ki}}{1-x^i}$
$=\prod _{i=x}^n(1-x^{ki})\cdot \prod _{i=x}^n\frac{1}{1-x^i}$
$=\prod _{i=x}^n(1-x^{ki})\cdot \prod _{i=x}^n(1+x^i+x^{2i}+x^{3i}+\dots )$

答案即是这个生成多项式的 $x^1$ 到 $x^n$ 的系数之和。

注意到第一部分可以由一次简单的 01 背包实现，复杂度 $O(n^2)$，第二部分可以由一次简单的无限制多重背包实现，复杂度 $O(n^2)$。

F.

Prepared by ???.

不知道什么地方挖出来的一道题目，稍微改了下。可能是原题啊。如果有人知道来源的话不妨透露下啊？

Easy 可以简单地跑一遍 Floyd，然后发现是一个线性方程组，然后跑一下 Gauss Elimination。Done！

注意 printf("%.0f") 是不对的！会输出 -0！

我们不难留意到一个事实，对于一条边上的两个点，我们做一次减法，得到的就是这条边所连的两个连通块的和的差值。假设该树以 1 为根，我们记第 $i$ 个节点的子树和与除了这个子树外其余节点的和的差为 $t_i$，假如说我们知道整棵树的和 $S$，那么 $S+t_i$ 就是两倍的子树和（可以自行验证）。

那么我们怎么求 $S$ 呢？可以发现，$\sum _{i=2}^n\frac{S+t_i}{2}$ 恰好等于 $p_1$，因为距离为 $1$ 的点恰好累积了一次，距离为 $i$ 的点恰好被累积了 $i$ 次。（也可以自行验证）。

那么利用这一个方程我们就可以解出 $S$，然后再跑一遍 dfs 求每个节点上的值就做好了。时间复杂度 $O(n)$。

有一个坑点是，本题数据范围没有给，需要从答案的范围反推数据范围，很显然要开 64 位整数。

G.

Prepared by BelowLuminous.

考虑离线处理。将所有查询和母串相连建后缀数组。对于每一个查询，在排好序的后缀数组中恰好有一段相对应，可以二分求得 $L,R$。问题就转换为在 $L,R$ 区间内有多少后缀的下标在查询区间范围内的。这是一个非常经典的区间问题。继续考虑离线处理，从大往小将数插入，然后使用树状数组轻松解决。时间复杂度 $O(n\log n)$。

事实上本题的做法非常套路，所以过得人也比 F 多（？？？）。

据验题人说暴力加疯狂特判也能过，而且玄学优化不可卡。暴力姿势太大，比不来。

Comments

zerol

7 年，4 月前

题目质量不错（至少所有题目都有人过，是吧？）。

出题人之一 (ultmaster) 遗憾地表示：

这届水平不行啊。。。

回复 9 0

BelowLuminous

7 年，4 月前

我国选手的植物学水高超啊?

回复 1 0

ECUST_LiXiang

7 年，4 月前

学到了，不错的题
出题组辛苦了

回复 1 0

ECUST_LiXiang

7 年，4 月前

g题出处？谢谢

回复 1 0

ultmaster

7 年，4 月前

原创。

回复 2 0

kblack

7 年，4 月前

如有雷同，那也没有办法，毕竟比较裸。

回复 1 0

StupidTurtle

7 年，4 月前

说实话D没百度到 bzoj 锦囊问题 2333

回复 1 0

ultmaster

7 年，4 月前

BZOJ 1191.

回复 1 0

Challenge1996

7 年，4 月前

D题如何套路啊？萌新不会啊

回复 0 0

ultmaster

7 年，4 月前

这个模型挺经典的啊。可以自己搜索「BZOJ锦囊」。

回复 0 0

oubayashi

7 年，4 月前

c题为啥是nlogn啊

回复 0 0

ultmaster

7 年，4 月前

因为要排序啊？

回复 0 0

BelowLuminous

7 年，4 月前

（甚至不开，逃）

回复 0 0

BelowLuminous

7 年，4 月前

O(n)也行的，可以开26倍内存存位置

回复 0 0

zerol

7 年，4 月前

显然 $O(n)$ 也是可以的。

回复 0 0

16110501005

7 年，4 月前

F题每个点与其他点的差值ti怎么求啊

回复 0 0

ultmaster

7 年，4 月前

其实就是相连的两个点的 $p_i$ 的差啊。

回复 0 0

16110501005

7 年，4 月前

@ultmaster E2 比昨天更多的棒棒糖 (Hard) 数组开不下怎么办

回复 0 0

ultmaster

7 年，4 月前

有这种事？讲道理是开得下的啊？（善良的我把内存加到了 1GB）

回复 0 0

Master X

7 年，4 月前

讲真，题目不错。大一萌新表示虽然没学过数据结构，但算法确实可以想得出来。

回复 0 0

maggch

7 年，4 月前

学到了(#^.^#)

回复 0 0

Fish_Li

7 年，4 月前

C题网络流可以过吗？

回复 0 0

ultmaster

7 年，4 月前

应该可以。

回复 0 0

帕秋莉_诺蕾姬

7 年，4 月前

C题再排回来是啥意思？？？

回复 0 0

ultmaster

7 年，4 月前

就是把字符串排成有序的做，做完以后每一个字符都有一个对应的新字符了。然后这时在按照原来的下标顺序进行排序。

回复 1 0

pPPArco

7 年，4 月前

E题生成函数中连乘符号∏i=1-n应该是算i=x-n吧？

回复 0 0

kblack

7 年，4 月前

不好意思，手滑了。。。已修正

回复 0 0