最速输入问题(上)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

屏幕上有一个字符, 如果只用全选复制粘贴, 要达到$n$个字符最少要多少次按键?

要想达到$N$个字符

  • 如果$N$是个素数,玩完了

只能一个一个复制了, ACVVVVVVVVVV...

也就是 N+2 次.

  • 如果N可以分解

那么我们找出他的一个因子 $\mathrm{i}$ ,另一个因子记为$ \mathrm{ j=N/i}$

也就是达到 $\mathrm{dp[i]}$ 之后粘贴 $j+1$ 次

要不就达到 $\mathrm{dp[j]}$ 之后粘贴$ i+1$ 次

$$\mathtt{dp[i] =Min[dp[j] + i/j + 2, dp[i/j] + j + 2]}$$

我们比较三种路径那个更小就行了.

当然所有路线一起比是一样的...

Read More

分式函数迭代

Aster 理宅异闻录 Leave a Comment

有这样一种填空题:

已知$f(1)=1,f(x + 1) = \frac{{1 + f(x)}}{{1 - f(x)}}$,求$f(2017)$

老师第一次讲这个的时候说了个迭代倍增法,先再加个1,然后加个2,然后加4,加到变回$f(x)$为止...

下面一片懵逼...为毛这么搞能做出来啊,为毛这样一定有周期性啊,有没有可能有的题不是2的幂的周期啊...


考虑如下一般情况:

\[f(x + \lambda ) = \frac{af(x) + b}{cf(x) + d}\quad \lambda  \ne 0\]

Read More