【学习笔记】NOIP爆零赛5

说实话是不想补题的。因为每一道题都贼难写，题解又通篇写着显然，然后自己天天搞竞赛又把注意力搞差了，调一道题又调半天，考试的题又难的要死 不会正解 ，部分分又写挂了 可能心态崩了就是从那场$t1$签到题考高精度数位$dp$容斥开始的吧

young

没错，又是一来第一道题就把你心态搞崩了。

这一看就是一个非常暴力非常玄学的$dp$ ，那么问题来了，机房里只有一个人过了，这是为什么呢

现在来想这个题还是觉得非常抽象。反正确实没啥好办法，就照着出题人的做法学吧。

反正考场上也就只能$30pts$跑路了。

simple

这场唯一能做的题。不过还是需要猜到一个小结论才能做出来。

首先看这道题，和最小表示法很像，但是又不完全是，因为后面那些位填的是$0$。

如果这个串的循环节长度$<n$的话，那么这个串肯定是不合法的，因为最小表示不唯一，而又要求严格大于。然后最小表示唯一了，这里又可以猜这些轮换中合法的恰好对答案的贡献是$1$，于是可以得到：

$f(i)=\frac{{\sum }_{j|i}10^j\mu (i/j)}{i}$

直接暴力算复杂度$O(n\ln n)$。说实话我考场上想到这里的时候脑子都是混乱的，完全想不清楚了 原因如上 ，结果数组开爆直接gg。

说到底还是被$t1$坑了。本来以为$t1$可以切掉的，结果谁知道越想越复杂，越想越觉得不对，直接整出心理阴影了。当然还有一个原因，我对数论函数不是很熟悉，所以考场上完全没往这方面想，就想硬刚数数题

唉，感觉模拟赛的出题人出题风格和atcoder完全不同，做着很难受啊

注意到$10^j$不是积性函数，因此这里要把它提出来计算：

$\sum 10^j\times j\times {\sum }_{i\le \lfloor \frac{n}{j}\rfloor }(i\times \mu (i))$

可以直接计算，复杂度$O(n)$，有$60pts$。

可以用整除分块+杜教筛优化，套两个板子即可。说实话考这种优化挺无聊的，但是出题人要考又有什么办法呢，我还是滚回去复习一下模板吧

接下来是速成，建议不看

对于数论函数$f$，要求我们计算$S(n)={\sum }_{i=1}^{n}f(i)$

对于任意数论函数$g$，必满足 ${\sum }_{i=1}^n(f\ast g)(i)={\sum }_{i=1}^{n}g(i)S(\lfloor \frac{n}{i}\rfloor )$

那么可以得到递推式$S(n)={\sum }_{i=1}^n(f\ast g)(i)-{\sum }_{i=2}^{n}g(i)S(\lfloor \frac{n}{i}\rfloor )$

只要预处理前$n^{\frac{2}{3}}$个值即可，其他可以递归计算。

想必聪明的你应该已经知道该怎么做了吧

代码咕了，我只能说对不起

naive

出题人很友好。写出最无脑的$dp$再找一下规律就有$50pts$。真是谢谢出题人了。

这结论太小，以至于我看不出来

首先还是假设第$0$层存在，并且这一层的状态为$0$，每次相当于猜一个楼层是$0$还是$1$，最后要还原整个状态，设$f_{i,j}$表示楼层高度为$i$，有$j$个记者时的最小次数，根据定义有$f_{i,j}={\min }_{1\le k\le i}\max (f_{i-k,j},f_{k-1,j-1})+1$。

当然这样肯定是找不出来什么规律的，只能尝试一下其他的$dp$方式。

设$g_{i,j}$表示有$i$个记者和$j$次操作时，能得到的楼层最高高度。

剩下的想不动了。所以我咕了。放弃思考