竞赛讨论区 > 【题解】2020牛客寒假算法基础集训营第三场

【题解】2020牛客寒假算法基础集训营第三场

头像
四糸智乃
编辑于 2020-02-12 01:32:33 APP内打开
赞 54 | 收藏 37 | 回复40 | 浏览12458

写在题解前的话

按照惯例,先背锅。
这次比赛没有Hello World或者A+b problem这样的“签到题”。
也没有能直接贴过来的那种,能够AC的话都不错。
爆0的话也不用担心,后面的场都比我这场简单(大概)。
然后锅嘛...
B题spj写锅了,可以判题但是不能统计罚时(WA了算内部错误没有罚时)
题目描述上面有点小锅。
这场比赛我每个题都写了很多不同的程序,会公开给大家看一下(选手可能只会被题目恶心一次,但是出题人可能要被自己出的题恶心死...做个10遍8遍的,还得出数据)。

A、牛牛的DRB迷宫I

这个题是所有题里面最简单的题,是经典的走格子DP(棋盘型DP)。
然后就是只要从左上角开始for,如果是D就往下累加,如果是R就往右累加,如果是B就同时累加。
转移方程:


然后有两种写法一种是递推的,另一种是递归的。
时空复杂度

B、牛牛的DRB迷宫II

构造A题中的迷宫,要求方案数整好等于给定的k,可以构造一个二进制编码器,斜对角线上的方案数恰好是1,2,3,4,8,16,32...,用二进制可以拼出所有的数字,所以一定能造的出来。


如图所示,斜对角线的R对应位置是二进制数,然后只要这一位有的话就可以直接把他变成B。

C、牛牛的数组越位

模拟题,按题目要求模拟即可,只要是注意别真RE了。

D、牛牛与二叉树的数组存储

跟上一道题一样,注意别真RE了。

E、牛牛的随机数

首先答案为 ,就是枚举每种情况,然后除以方案总数。
那这个东西怎么算呢?

数位DP

如果不知道数位DP是什么的话我简单介绍一下: https://blog.nowcoder.net/n/ec605c08900140019698e33059b20873
有两种思路,第一种是拆位后直接数位DP。
首先考虑二进制的个位产生的贡献,那么二进制个位产生的贡献有两部分:
区间内个位为0的数字乘以 区间内个位为1的数字。
区间内个位为1的数字乘以区间内个位为0的数字。
做一个二进制位的数位DP,用于统计该数位0与1的个数。
假设中二进制的个位产生0的数目为cntx_0二进制的个位产生1的数目为cntx_1
中二进制的个位产生0的数目为cnty_0二进制的个位产生1的数目为cnty_1
那么就产生了cnty_0*cntx_1+ cntx_0* cnty_1的贡献。
如果是二进制的十位呢,那么就是( cnty_0*cntx_1+ cntx_0 * cnty_1)*2。
那么二进制的第k位的贡献就为
时间复杂度:
除了上述数位DP以外,也可以考虑把两个数字同时放进来做一个大的数位DP。
但是这种写法很不好写,不推荐初学者使用。
这种写法需要注意limit只能够在同时限制时暴力扩展,否则复杂度将退化为
但是这种写法的复杂度为 因为省了一个二进制拆位。
但是这种解法肯定不够萌新。

找规律

那么萌新解法是什么呢,我们先观察一下二进制数的规律

把所有的数字从0开始枚举,然后转化成二进制输出,我们发现二进制下个位的规律是010101...循环,十位是001100110011...循环,而百位是0000111100001111...循环。
接下来的话就跟上面差不多。
假设 中二进制的个位产生0的数目为 cntx_0二进制的个位产生1的数目为 cntx_1
中二进制的个位产生0的数目为 cnty_0二进制的个位产生1的数目为 cnty_1
那么就产生了 cnty_0* cntx_1+ cntx_0* cnty_1的贡献。
如果是二进制的十位呢,那么就是( cnty_0* cntx_1+ cntx_0* cnty_1)*2。
那么二进制的第k位的贡献就为
当然这个容斥算贡献的部分也可以使用类似二维前缀和一样的容斥。
这种算法只有二进制拆位和容斥,所以时间复杂度为

F牛牛的Link Power I

对于前缀和的相关知识,可以到我的博客里面看一下

昨天临时写的,因为感觉展开来讲的话题解里面写不下

前缀和是一个比较基础的算法,但是它可以扩展出很多很杂的算法,包括可以跟多项式卷积结合来出题

直接计算

记录cnt与sum,cnt表示当前经过了多少个1,sum表示当前的贡献总和。
这个也是最直观最好想到,最有效的算法
因为他时间复杂度为 空间复杂度甚至可以

前缀和

就我们发现每个“1”对于它本身位置产生的影响贡献为0,而往后面依次产生了0,1,2,3,4,5...的贡献。
然后你可以利用静态维护区间加等差数列的技巧 https://blog.nowcoder.net/n/1c3504ca9e3f40d2a37376cd1b76ddec
那当然,这个东西特殊,不用这么一般性的技巧。
对于每个位置的1",假设它的位置为pos,那么直接对a[pos+1]加上1的贡献。
全部做完以后,做两次前缀和操作,对于每个位置的“1”直接查询数组中的值加起来即可。
时空复杂度为

分治法

分治算法计算贡献,对于每一个区间 ,它的中点为mid,该区间的贡献可以分解为以下三部分
1、左侧区间产生的贡献。
2、右侧区间产生的贡献。
3、过中点mid产生的新贡献。
那么对于1,2,我们可以使用递归求解,由于区间越分越小,所以最终复杂度总和为
考虑3,只需要暴力for左侧区间,统计左侧区间"1"的数目,以及它们到中点的和。
时空复杂度为
这个方法虽然不够优秀,但是它可以扩展到线段树上面维护动态问题(也就是解决第二问),线段树其实就是保留了每次分治的结果。
如果学分治的话建议写一写。

G牛牛的Link Power II

分块法

分块法可以看做是上一题中直接计算这种思路的扩展。对于每个修改,真就暴力再for一遍计算,那么可以将数组切断切成若干块,对于每个块提前储存好延伸到左右两侧的sum与cnt信息。
由于每次修改只是修改一个位置,所以只用暴力一个块的块内,这部分贡献只要暴力for过去计算即可,而对块外的贡献则能够通过每个块储存的信息直接求的。
时间复杂度O( )

前缀和(树状数组实现)

注意到上一道题目中说的,其实就是要维护一个“前缀和的前缀和”。
那么可以直接使用这个技巧: https://blog.nowcoder.net/n/bb352f0f59ea4509b0a7fc15b11fa5a8

时间复杂度:

solution:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42886740

前缀和(线段树实现)(最好写)

由于要维护的是“前缀和的前缀和”所以可以升一阶,直接维护前缀和,这样单点修改就变成了区间修改,然后区间查询即可。
这个算法是最好写的...好写到什么程度呢...好写到我是个真·萌新,前天做第二场牛客比赛的时候刚听说过线段树,然后学了一下,只会线段树的区间加数,区间求和,别的都不会,也不会改板子。
在这种情况下你也能AC。
开两颗线段树,一颗叫pre树,一颗叫suf树,然后对于每个位置为pos的"1",都在pre树的 这个区间加上1,在suf树中的 这个区间加上1
然后对于每个1,他跟别人产生的贡献就是pre树的 +suf 树的
对,没错,没有任何花里胡哨的操作,只有区间+1,区间求和,你甚至都可以把它当成是线段树的模板题。
时间复杂度:

solution:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42886744

动态分治(线段树实现)

时间复杂度:
这种写法就是靠魔改线段树来实现,初学线段树的话就不要尝试了,建议初学者写上面那种算法
那其实也算是比较直观的印象,你让我维护啥,我就维护啥呗,那我就维护“左区间的贡献”,“右区间的贡献”,线段树兄弟节点之间产生的贡献,不就好了。

DLC:牛牛的Link Power III

额...这里插几句话...原本这个题目是一道树上问题,然后吧...太难了,所以削弱变成两道题,一道是数组上直接计算,一道是数组上带修改。
对于树上的这种情况,可以使用动态树分治(点分树)来实现。

这里只是让大家扩展一下思路和视野,看一下如果是树上的情况该怎么考虑
时间复杂度:


H牛牛的k合因子数

埃式筛筛出质数,然后对于合数再筛一遍,然后统计每个数字被筛到的次数。桶排序一下即可。
时间复杂度:

I牛牛的汉诺塔

记忆化

这个的话还是有两种思路,第一种是记忆化搜索,就直接在递归函数里面写记忆化就可以。
时间复杂度:

递推

第二种思路就是递推,这个其实是一个类似斐波那契数列一样的东西,所以也可以递推或者使用矩阵快速幂直接求一个n很大的情况。
这个递推的解法我并没有写程序,如果有写了的同学欢迎在讨论区补充
时间复杂度:
这是来自评论区14楼 我不会玩锐雯 同学的补充
dp[i][j][k]表示在第i种情况下n层汉诺塔产生第k中操作的次数
这是来自评论区27楼 1838641320同学的补充
I题的递推这样应该更符合萌新。
A->B=(上一次)A->C->B
B->C=(上一次)B->A->C
C->A=(上一次)C->B->A

J牛牛的宝可梦Go

这个题首先先求一遍最短路,这个求最短路的过程可以用flord实现。
接下来类似最长上升子序列,但是显然这个好像不太好优化,考虑暴力 转移,由于地图的大小只有200,所以200步以后可以转移到任意位置,用这个性质可以优化 ->200k。
也就是说每次转移只暴力往前for200个,多余200个以上的时候记录一个前缀max,直接从这个前缀中转移。
时间复杂度:

40条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐