【学习笔记】NOIP爆零赛5

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

young

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

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

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

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

simple

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

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

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

f(i)=∑j∣i10jμ(i/j)if(i)=\\frac{\\sum_{j|i}10^j\\mu(i/j)}{i}f(i)=i∑j∣i​10jμ(i/j)​

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

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

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

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

∑10j×j×∑i≤⌊nj⌋(i×μ(i))\\sum 10^j\\times j\\times \\sum_{i\\le \\lfloor\\frac{n}{j}\\rfloor}(i\\times \\mu(i))∑10j×j×∑i≤⌊jn​⌋​(i×μ(i))

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

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

接下来是速成，建议不看

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

对于任意数论函数$g$，必满足 ∑i=1n(f∗g)(i)=∑i=1ng(i)S(⌊ni⌋)\\sum_{i=1}^n(f*g)(i)=\\sum_{i=1}^ng(i)S(\\lfloor\\frac{n}{i}\\rfloor)∑i=1n​(f∗g)(i)=∑i=1n​g(i)S(⌊in​⌋)

那么可以得到递推式S(n)=∑i=1n(f∗g)(i)−∑i=2ng(i)S(⌊ni⌋)S(n)=\\sum_{i=1}^n(f*g)(i)-\\sum_{i=2}^ng(i)S(\\lfloor\\frac{n}{i}\\rfloor)S(n)=∑i=1n​(f∗g)(i)−∑i=2n​g(i)S(⌊in​⌋)

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

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

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

naive

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

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

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

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

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

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