风雨无阻 题解

这道题目显然是手速题，就是要注意当的时候会爆类型，记得开（为）就好了（带有恶意地问一下：那些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