BestCoder Solution

BestCoder Solution

1001 Fxx and string

枚举$\:i\:$和等比数列公比$\:q\:$，但考虑到$\:q\:$有可能是$\:1/t\:$的形式，所以倒过来枚举一遍就可以了。

1002 Fxx and game

设$\:F_i\:$表示将$\:i\:$变为$\:1\:$的最少步骤，如果$\:k|i,F_i=min{F_j,F_{\frac{i}{k}}}$，否则$\:F_i=min{F_j}$，其中$\:i-t\leq j\leq i-1$。

用单调队列维护一下就好了。

时间复杂度$\:O(n)$。

1003 Fxx and tree

考虑从上往下贪心，要将整棵树翻白，有唯一的方案。于是我们只考虑翻了多少个正确的点。

设$\:f_x\:$表示还有$\:n-x\:$个正确的点没有翻需要的期望步数。注意到翻到一个错误的点后，必须要再翻一次这个点才能挽回。于是我们可以列出一个方程。

$$f_0=f_1+1,f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1,f_n=0$$

用高斯消元求出解就行了。每组数据复杂度$\:O(n^3)$。

1004 Fxx and factory

假设经过一轮操作后本来从左到右第$\:i\:$个桶变为了第$\:p_i\:$个，我们将$\:n\:$个桶抽象为$\:n\:$个点，并在所有的$\:i\:$和$\:p_i\:$中连一条边，那么我们一定会得到若干个环（包括自环）。

由第一类斯特林数可以证明当$\:3\:$操作无限时，环的数量是$\:log(n)\:$级别的。又由于$\:3\:$操作数量对于$\:n\:$的数量是很大的且数据随机，所以我们可以得到在本题中环的数量是$\:log\:$级别的。

对于每条$\:i->p_i\:$的边，这条边上有若干$\:1,2\:$操作，对于每条边我们记录两个量$\:flag,val$，$flag=0\:$表示这条边有没有$\:2\:$操作，否则表示有，$val\:$ 表示这条边最后一个$\:2\:$操作后所有$\:1\:$操作的加数的和。

现在来考虑每一个桶，经过$\:k\:$轮后的值，其实就是在图上的一个点经过$\:k\:$条边，如果这$\:k\:$条边的$\:flag\:$都为0，那么我们直接把这$\:k\:$条边的$\:val\:$相加即可，否则我们把最后一个$\:flag=0\:$的边之后的$\:val\:$相加即可。

那么我们现在就可以对每一个环预处理出经过$\:1-len\:$轮后的最大值，$len\:$为环的长度，这个直接用数组记录就好了，当$\:k>len\:$时，我们可以由$\:k\%len\:$和$\:\frac{k}{len}\:$得出来。

查询的话直接扫每一个环就行了，总复杂度$\:O(n^2+Qlogn)\:$

Read full article from BestCoder Solution