【题解】牛客OI周赛10-提高组

风雨无阻 题解

这道题目显然是手速题,就是要注意当的时候会爆类型,记得开)就好了(带有恶意地问一下:那些83分的是不是都没注意到啊?开long long是个好习惯)

Taeyeon的困惑 题解

这道题目一开始由于出题人脑子抽到了导致题面出错了……该题出题人真的被关进小黑屋了!(其他出题者备注)

30分的巧妙想法

如何获得呢?在上30分也是非常重要的……

的想法就是从左到右扫一遍,然后每次按照区间说的使用***中的nth_element()就可以了,不然给每个区间排序然后取大也行,然后把每次的答案累加起来就可以了。

100分的巧妙想法

请注意,这题数据保证纯随机!读题是很重要的!

我们知道每次移动这个区间只会对两个数造成改变,那么可以用计数的方法维护两个指针,每次移动指针就可以了。而且数据纯随机,左右,所以每次移动指针的复杂度可以看成常数。

移动指针的代码如下:

hsh[a[i-m]]--,hsh[a[i]]++;
Num+=(a[i-m]>Now?0:-1)+(a[i]>Now?0:1);
if(a[i-m]<=Now) Sum-=a[i-m];
if(a[i]<=Now) Sum+=a[i];
while(Num-hsh[Now]>K) Num-=hsh[Now],Sum-=(LL)hsh[Now]*Now,Now--;
while(Num<K) Num+=hsh[++Now],Sum+=(LL)hsh[Now]*Now;

逃离幻想乡 题解

这种OEIS上找不到的数论题我最喜欢了

这道题目其实分为两个小题:

​ 1.求[0..n]区间中有多少个的首位数字为(其中),对于这道题目,我表示也没什么好的办法,我可以想到的最好的办法就是:分块打表对于都去找一遍规律然后总结,我这里给出当的时候的方法规律以及方法:

​ 如果,那么恰好就会有个这样的,因为对于每个恰好有一个这样的为数字的幂,因此答案是

​ 将结论推广到,那么可以证明答案是

​ 特别地,由于结论的特殊性,对于的情况需要特判(即若那么需要)。

​ 2.双色单柱汉诺塔问题,我们秉承着从易到难得原则,我们假设没有“颜色顺序必须一样”这个规则,那么最优方案就是:

​ 移动一个双重次大圆盘,接着移动(将次序反过来)双重最大圆盘,然后再次移动双重次大圆盘(相当于是把大圆盘抽出来),从而我们有递推式:,归纳得:,这个解我们是每次都交换了最大和次大的圆盘,然后其余的个圆盘都是以原来的次序放回,可以证明,这个是最优解。

​ 我们就会发现双重汉诺塔在移动的过程中,由于上面的圆盘是先被移动的,所以会产生黑白颠倒的问题,所以在处理有颜色的情况的时候,我们需要重新将双重圆盘顺序颠倒,即将所有的个方块归位的时候,我们需要将这两个方块交换顺序。可以证明:当的时候,任何策略的步数都无法少于该策略的步数,其中,即,同时,我们会发现

std

A题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40699894
B题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40699947
C题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40699971

全部评论
C题第二小题在具体数学上有写
点赞 回复
分享
发布于 2019-05-25 21:57
A题std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40699894 B题std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40699947 C题std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40699971
点赞 回复
分享
发布于 2019-05-25 14:13
阿里巴巴
校招火热招聘中
官网直投
A题备用std:https://paste.ubuntu.com/p/2ZxKvDQX2B/ B题备用std:https://paste.ubuntu.com/p/p8b4MY4JrR/ C题备用std:https://pastebin.com/HDX6bLUt
点赞 回复
分享
发布于 2019-05-25 14:21
可以解释一下  样例 吗 我估计理解错题意了
点赞 回复
分享
发布于 2019-05-25 22:53
这B题的代码毫无可读性啊...
点赞 回复
分享
发布于 2019-05-28 21:13

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务