写在题解前的话
按照惯例，先背锅。
这次比赛没有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、牛牛的随机数
首先答案为*(r_2-r_2%2B1%5C%20%20)%5C%20%20%7D)
，就是枚举每种情况，然后除以方案总数。
那这个东西怎么算呢？
数位DP
如果不知道数位DP是什么的话我简单介绍一下：https://blog.nowcoder.net/n/ec605c08900140019698e33059b20873
有两种思路，第一种是拆位后直接数位DP。
首先考虑二进制的个位产生的贡献，那么二进制个位产生的贡献有两部分：
做一个二进制位的数位DP，用于统计该数位0与1的个数。
假设
中二进制的个位产生0的数目为
二进制的个位产生1的数目为
那么就产生了
*+*
的贡献。
如果是二进制的十位呢，那么就是(*+*)*2。
那么二进制的第k位的贡献就为*2%5Ek)
。
时间复杂度：%5E2%20%5Cright))
除了上述数位DP以外，也可以考虑把两个数字同时放进来做一个大的数位DP。
但是这种写法很不好写，不推荐初学者使用。
这种写法需要注意limit只能够在同时限制时暴力扩展，否则复杂度将退化为
但是这种写法的复杂度为)
因为省了一个二进制拆位。
但是这种解法肯定不够萌新。
找规律
那么萌新解法是什么呢，我们先观察一下二进制数的规律
把所有的数字从0开始枚举，然后转化成二进制输出，我们发现二进制下个位的规律是010101...循环，十位是001100110011...循环，而百位是0000111100001111...循环。
接下来的话就跟上面差不多。
假设中二进制的个位产生0的数目为二进制的个位产生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(
)
前缀和（树状数组实现）
注意到上一道题目中说的，其实就是要维护一个“前缀和的前缀和”。
时间复杂度：
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) 回帖