了解宿迁建设网站,外国人做那个视频网站,网上信息发布平台,深圳建设网站个人说实话是不想补题的。因为每一道题都贼难写#xff0c;题解又通篇写着显然#xff0c;然后自己天天搞竞赛又把注意力搞差了#xff0c;调一道题又调半天#xff0c;考试的题又难的要死 不会正解 #xff0c;部分分又写挂了 可能心态崩了就是从那场t1t1t1签到题考高精度数位…说实话是不想补题的。因为每一道题都贼难写题解又通篇写着显然然后自己天天搞竞赛又把注意力搞差了调一道题又调半天考试的题又难的要死 不会正解 部分分又写挂了 可能心态崩了就是从那场t1t1t1签到题考高精度数位dpdpdp容斥开始的吧
young
没错又是一来第一道题就把你心态搞崩了。
这一看就是一个非常暴力非常玄学的dpdpdp 那么问题来了机房里只有一个人过了这是为什么呢
现在来想这个题还是觉得非常抽象。反正确实没啥好办法就照着出题人的做法学吧。
反正考场上也就只能30pts30pts30pts跑路了。 simple
这场唯一能做的题。不过还是需要猜到一个小结论才能做出来。
首先看这道题和最小表示法很像但是又不完全是因为后面那些位填的是000。
如果这个串的循环节长度nnn的话那么这个串肯定是不合法的因为最小表示不唯一而又要求严格大于。然后最小表示唯一了这里又可以猜这些轮换中合法的恰好对答案的贡献是111于是可以得到
f(i)∑j∣i10jμ(i/j)if(i)\frac{\sum_{j|i}10^j\mu(i/j)}{i}f(i)i∑j∣i10jμ(i/j)
直接暴力算复杂度O(nlnn)O(n\ln n)O(nlnn)。说实话我考场上想到这里的时候脑子都是混乱的完全想不清楚了 原因如上 结果数组开爆直接gg。
说到底还是被t1t1t1坑了。本来以为t1t1t1可以切掉的结果谁知道越想越复杂越想越觉得不对直接整出心理阴影了。当然还有一个原因我对数论函数不是很熟悉所以考场上完全没往这方面想就想硬刚数数题
唉感觉模拟赛的出题人出题风格和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)O(n)O(n)有60pts60pts60pts。
可以用整除分块杜教筛优化套两个板子即可。说实话考这种优化挺无聊的但是出题人要考又有什么办法呢我还是滚回去复习一下模板吧
接下来是速成建议不看
对于数论函数fff要求我们计算S(n)∑i1nf(i)S(n)\sum_{i1}^n f(i)S(n)∑i1nf(i)
对于任意数论函数ggg必满足 ∑i1n(f∗g)(i)∑i1ng(i)S(⌊ni⌋)\sum_{i1}^n(f*g)(i)\sum_{i1}^ng(i)S(\lfloor\frac{n}{i}\rfloor)∑i1n(f∗g)(i)∑i1ng(i)S(⌊in⌋)
那么可以得到递推式S(n)∑i1n(f∗g)(i)−∑i2ng(i)S(⌊ni⌋)S(n)\sum_{i1}^n(f*g)(i)-\sum_{i2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)S(n)∑i1n(f∗g)(i)−∑i2ng(i)S(⌊in⌋)
只要预处理前n23n^{\frac{2}{3}}n32个值即可其他可以递归计算。
想必聪明的你应该已经知道该怎么做了吧
代码咕了我只能说对不起 naive
出题人很友好。写出最无脑的dpdpdp再找一下规律就有50pts50pts50pts。真是谢谢出题人了。
这结论太小以至于我看不出来
首先还是假设第000层存在并且这一层的状态为000每次相当于猜一个楼层是000还是111最后要还原整个状态设fi,jf_{i,j}fi,j表示楼层高度为iii有jjj个记者时的最小次数根据定义有fi,jmin1≤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,jmin1≤k≤imax(fi−k,j,fk−1,j−1)1。
当然这样肯定是找不出来什么规律的只能尝试一下其他的dpdpdp方式。
设gi,jg_{i,j}gi,j表示有iii个记者和jjj次操作时能得到的楼层最高高度。
剩下的想不动了。所以我咕了。放弃思考
