EOJ Monthly 2017.12 题解

ultmaster edited 2 年,1 月前

A.

Prepared by kblack.

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

B.

Prepared by kblack.

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

于是对于所有 的棋盘,我们可以断言所有砖之间可以互相到达,此时答案为

当棋盘大小为 时,通过简单的模拟可以发现外围的 块砖可以互相到达,此时答案为

当棋盘大小为 时,我们发现不同奇偶不同的行/列交替可达,此时有 2 组 的联通块与两组 的联通块,答案为

当棋盘大小为 时,没有合法的马步,此时答案为

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

C.

Prepared by ultmaster.

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

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

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

D.

Prepared by infiniteee.

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

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

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

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

E.

Prepared by kblack.

Easy 部分可以简单的用 : 买个 根,最后一天买 根,买 根已经 天来实现。朴素转移时间复杂度 足够通过,可是没人做。

可以发现,购买棒棒糖,相当于是在做最大容量为 ,物品大小为 重背包,恰好使用 元的方案数即是背包容量为 的方案数,多重背包 的复杂度明显是我们无法接受的,考虑使用生成函数优化背包。




答案即是这个生成多项式的 的系数之和。

注意到第一部分可以由一次简单的 01 背包实现,复杂度 ,第二部分可以由一次简单的无限制多重背包实现,复杂度

F.

Prepared by ???.

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

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

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

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

那么我们怎么求 呢?可以发现, 恰好等于 ,因为距离为 的点恰好累积了一次,距离为 的点恰好被累积了 次。(也可以自行验证)。

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

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

G.

Prepared by BelowLuminous.

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

事实上本题的做法非常套路,所以过得人也比 F 多(???)。

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

Comments

zerol

题目质量不错(至少所有题目都有人过,是吧?)。

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

这届水平不行啊。。。

BelowLuminous

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

ECUST_LiXiang

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

ECUST_LiXiang

g题出处?谢谢

ultmaster

原创。

kblack

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

StupidTurtle

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

ultmaster

BZOJ 1191.

maggch

学到了(#^.^#)

Fish_Li

C题网络流可以过吗?

ultmaster

应该可以。

帕秋莉_诺蕾姬

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

ultmaster

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

pPPArco

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

kblack

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

Challenge1996

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

ultmaster

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

oubayashi

c题为啥是nlogn啊

zerol

显然 也是可以的。

ultmaster

因为要排序啊?

BelowLuminous

(甚至不开,逃)

BelowLuminous

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

16110501005

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

ultmaster

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

16110501005

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

ultmaster

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

Master X

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

你当前正在回复 博客/题目
存在问题!