竞赛讨论区 > 【题解】牛客挑战赛34
头像
Jμdge
编辑于 2019-11-22 22:22
+ 关注

【题解】牛客挑战赛34

首先没有想到D题只要会转换距离之后,二维数点的板子这么容易找,然后T3 T4的难度反了,真的非常抱歉

然后如果有舟游玩家就会对这套题倍感亲切,所以 出题人的账号是 官: 晓敏敏QF#4285

好了接下来进入题解部分

A 能天使的愿望

一道非常简单的动态规划的题目,我们可以设为购买把铳的最低花费

那么状态转移方程就是,其中表示在第家店铺购买把铳的花费 (包括邮费)。

对于邮费的处理,你可以在读入的时候就加进花费里,也可以在转移时处理,并没有卡这里的一点常数,两种方法都可以过

时间复杂度,空间复杂度,坑点:本题要开long long

B 罗德岛裁员

本题题目原型是经典的 约瑟夫问题

我们观察题目的数据范围,显然是需要比更优秀的做法,那么我们可以先考虑的做法,也即线性递推

(下面的 表示初始 名参与者的情况下获胜玩家的编号)

如果说知道约瑟夫问题中的递推公式的话可以非常快的想到这一公式:
接下来我们简单的证明,只存在唯一一个符合条件的

然后我们考虑怎么求出这个 ,以便减去它

我们在证明过程已经发现,就是小于的最大的2的幂,即

那么我们可以让 ,这样就可以得到关于

然后原来的式子可以转化为递推式:
我们只需要枚举,然后统计有几个即可 求解本题。

但是很遗憾,的复杂度远远无法通过此题

要想通过本题,我们需要用到优于 的算法,也即,根据做数论题的直觉以及我们在推导做法时出现了 ,所以我们向想,要想做到这个复杂度,我们需要对于解法继续探究

对于 做法而言,该公式不仅可以从前面推向后面,而且可以从后面推至前面,而这正符合我们已知获胜编号求不确定的 的问题

那么尝试把式子倒着推一下:
我们从中可以推出,满足 的个数即为答案

那么我们只要 地去枚举 ,然后把满足条件的 的个数累计入答案即可

至于最大参与人数则是最大的

对于这道题

但是其实可以用打表找 规律 的方法得知答案...

事实上相信大部分玩家都是打表过的此题,因此并没有把这道题放在后三道里面

CD 拉普兰德的愿望

我们发现离一个点曼哈顿距离固定的点形成的图形呈一个菱形,如下图

hanhan

而很难处理,如果做过类似的题目的同学就会想到,将曼哈顿距离转化为切比雪夫距离。

切比雪夫距离:平面上两个点的切比雪夫距离为,其中的绝对值

将曼哈顿距离转换为切比雪夫距离后,我们发现切比雪夫距离固定的点呈正方形

gangan

这样我们就可以先将数据离线,按照的大小对点进行排序,然后用树状数组维护长度为的正方形区域内点的个数即可,这部分代码相对就比较模板了

DC 远山的占卜

这题是一个旋转等价+对角等价的题目,对数学能力要求较高

我们不考虑置换类的运用,在这里,对角的两个点是可以归为一个等价类的,即这两个点可以放在一起考虑,然后对于 n 对点分别考虑完之后再进行整体的旋转置换。

hanpi

通过上图我们可以发现,题目中给出的旋转操作其实就是将半个圆进行旋转

我们发现对角的两个点相对位置不会变,即永远是对角,那么我们可以让这两个点构成的等价类有 种染色方案,然后问题就会变成普通的颜色数为 给 n 个点染色,求染色的方案数,那么就可以上 polya 定理了

关于 polya 定理可以考虑洛谷 【模板】polya 定理?我好像并没有写过题解...不过可以安利一本书叫做数学一本通?里面的群论有讲 polya 定理

polya定理

E 银灰的愿望

这一题乍一看似乎不可做,我们来冷静分析一手

首先把题目转换一下,我们给每个矩阵一个权值,那么题目的询问也就是求给出的矩形有交点的矩形的权值和

想办法无视删除操作的影响,我们发现删除一个矩形,从转换后的题目来看,也就是插入一个权值为的矩形,这样我们就成功无视了删除操作,使得题目只有插入操作

然后我们可以分开考虑,与一个矩形有交点的矩形可以用总矩形个数减去在这个矩形上方的,在这个矩形下方的,在这个矩形左方的,在这个矩形右方的所有矩形

但是这样四个角会被减去两次,所以还要加回来一次

将这些问题分开考虑,四个方向的贡献可以用一维按时间分治解决;四个角的贡献可以用二维按时间分治解决。这样就可以使用分治在的时间复杂度内完成本题(std写的丑自带大常数)

F 红的愿望

这一题就是一个树上的分数规划,难度主要体现在树形背包(的调试)

题目要你求的大概就是这么个式子:
大概就是说选出一些边,然后这些边两个端点值总和 除去 边权总和最大,求出这个值

然后上面没写条件,条件是 E 中所有的边权要大于等于给定的 m 并且任意两条边无公共端点(条件超难表示就没写在公式里)

于是我们 0/1 分数规划 一下就可以得到转换后的问题了:
这样我们只需要对于所有的边的权值重定义一下,等于两个端点点权和减去 ANS 乘上该边的边权就好了

然后我们二分 ANS ,再背包判断是否合法更新答案...

这里不难看出 将 ANS 看做因变量之后式子具有单调性

然后我们发现树形背包的时候更新的顺序很难调整(总会出一些莫名其妙的影响),那么我们直接开个辅助数组辅助转移就行辣

STD:

A :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42314480
B :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42314493
D :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42314495
C :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42314498
E :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42314503
F :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42314512

全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐