[DTCPC 2024] Ultra

Luogu
IDLGP10160
Time1000ms
Memory512MB
DifficultyP4
2024洛谷月赛
Tony2 的操作可以看作下冲和跳跃的组合。 称一个 $\text{Ultra}$ 为一段连续的操作,以下冲开头,然后跳跃和下冲交替,并以下冲结束。由于是 $\text{Ultra}$,所以至少要有一次跳跃。 小 C 每次可以将一个 $\text{Ultra}$ 变成 $\text{uLTRA}$,也就是将这个 $\text{Ultra}$ 的每个下冲变成跳跃,将每个跳跃变成下冲。 小 C 不喜欢 $\text{Ultra}$,所以想要使得下冲次数尽量少。 **形式化题意** 给你一个 $01$ 序列,你可以进行如下操作若干次(或零次): - 将序列中形如 $101\cdots01$ 的一个子串(即 $1(01)^k$,$k\ge 1$)替换成**等长**的 $010\cdots10$(即 $0(10)^k$)。 你要操作使得 $1$ 的个数尽可能少,输出最少的 $1$ 的个数。 ## Input 一行一个长度为 $n$($n\le 10^6$) 的字符串表示这个 $01$ 序列。 ## Output 输出一个数表示最少的 $1$ 的个数。 [samples] ## Background Tony2 喜欢玩某二字游戏,这一天他在小 C 面前展示他的 $\text{Ultra}$。 但是小 C 不会 $\text{Ultra}$,所以他跑去图图酱一去了。 ~~然后图图失败了~~ 于是小 C 趁 Tony2 不在的时候偷偷地把他的跳跃键和下冲键交换了( ## Note 样例 $1$ 解释:选中该串的前三个字符 $101$,对其操作后该串变为 $0100011$,仅包含 $3$ 个 $1$。容易证明这是最优的。
Samples
Input #1
1010011
Output #1
3
API Response (JSON)
{
  "problem": {
    "name": "[DTCPC 2024] Ultra",
    "description": {
      "content": "Tony2 的操作可以看作下冲和跳跃的组合。 称一个 $\\text{Ultra}$ 为一段连续的操作,以下冲开头,然后跳跃和下冲交替,并以下冲结束。由于是 $\\text{Ultra}$,所以至少要有一次跳跃。 小 C 每次可以将一个 $\\text{Ultra}$ 变成 $\\text{uLTRA}$,也就是将这个 $\\text{Ultra}$ 的每个下冲变成跳跃,将每个跳跃变成下冲。 小 C ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10160"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tony2 的操作可以看作下冲和跳跃的组合。\n\n称一个 $\\text{Ultra}$ 为一段连续的操作,以下冲开头,然后跳跃和下冲交替,并以下冲结束。由于是 $\\text{Ultra}$,所以至少要有一次跳跃。\n\n小 C 每次可以将一个 $\\text{Ultra}$ 变成 $\\text{uLTRA}$,也就是将这个 $\\text{Ultra}$ 的每个下冲变成跳跃,将每个跳跃变成下冲。\n\n小 C ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments