2292 . 字串修改
TopCoder
Tags
Description
給定一個長度為 $N$ 的 0/1 字串，並定義一次操作為進行下列兩種操作之一：
- 修改任意一個字元的值
- 把任意前綴全部取反（0 變 1、1 變 0）
請問最少需要多少次操作才能把這個字串改變為全部為 1 的字串呢？
Input Format
輸入只有一行包含一個 0/1 字串。
對於所有測資，$N\leq 1.5\times 10^ 9$。
對於 100 分的測資，$N\leq 5\times 10^ 7$。
Output Format
請輸出一行包含一個非負整數，代表最少需要的操作次數。
對於所有測資，若你的程式執行時間為時限的 $x$ 倍（$0\leq x\leq 1$），該筆測資的分數為 $A\times (p+qf(x))$，其中 $A$ 為該筆測資標示的分數、$p,q$ 為各測資敘述上標示的常數，並給定常數 $a=1.5,b=0.15$，
\[f(x)=\left(s(x) \frac{(b x)^ a - b^ a}{(b x)^ a - 1.1x^ a}+\big(1-s(x)\big)\left(1-\frac{x^ 2}{2}\right)\right)\]
\[s(x)=\begin{cases}x, & x\in\{0,1\} \\ \frac{1}{1+\exp\left(\frac{8a}{b}\cot\left(\pi x^ {-\frac{\ln2}{0.1+\ln b}}\right)\right)}, & \text{otherwise}\end{cases}\]
你只需要知道 $f(0)=1,f(1)=0$，且 $f(x)$ 嚴格遞減就可以了。不過如果想要詳細了解這些函數在幹嘛的話，可以參考這個連結。
Sample Input 1
100011011
Sample Output 1
3
Hints
Problem Source
TIOJ 1853 / TIOJ 終極壓常數大賽 pA
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | $p=1,q=0.2$ | 50 |
| 2 | 1 | $p=1,q=0.2$ | 50 |
| 3 | 2 | $p=0,q=1$ | 25 |
| 4 | 3 | $p=0,q=1$ | 120 |
| 5 | 4 | $p=0,q=1$ | 75 |
| 6 | 5 | $p=0,q=1$ | 75 |
| 7 | 6 | $p=0,q=1$ | 90 |
| 8 | 7 | $p=q=0.5$ | 40 |
| 9 | 8 | $p=q=0.5$ | 50 |