[PA 2021] Pandemia

Luogu
IDLGP9046
Time2000ms
Memory512MB
DifficultyP3
2021PA(波兰)
某国有 $n$ 座城市,其中 $\forall 1 \leq i < n$,城市 $i$ 与城市 $i + 1$ 有**双向**道路相连。 该国发生了疫情,一个城市要么无人感染,要么全体感染。具体地,一个城市初始时被感染当且仅当 $s_i = 1$。 疫情会扩散,每一天上午,你可以为一个未感染的城市的居民接种疫苗,下午,每个被感染的城市会向相邻的城市扩散,如果相邻的城市未接种疫苗,它将立即全员感染。 你作为城市管理者,想要知道执行最优策略的情况下,最少会有几个城市的所有人都被感染。 ## Input **本题有多组测试数据。** 第一行一个整数 $T$,表示数据组数。 对于每组数据: 第一行,一个整数 $n$; 第二行,一个长度为 $n$ 的字符串 $s$。 ## Output 对于每组数据: 一行,一个整数,表示所求的值。 [samples] ## Note #### 样例 #1 解释 测试点一:第一天接种城市 $7$,第二天接种城市 $1$。 测试点二:第一天接种城市 $5$,第二天接种城市 $7$。 测试点三:初始不存在疫情,因此不需要接种。 #### 数据范围 对于 $100\%$ 的数据,$1 \leq n, T \leq 10^5$,$1 \leq \sum n \leq 10^6$。
Samples
Input #1
3
8
00110100
10
1001000010
4
0000
Output #1
5
7
0
API Response (JSON)
{
  "problem": {
    "name": "[PA 2021] Pandemia",
    "description": {
      "content": "某国有 $n$ 座城市,其中 $\\forall 1 \\leq i < n$,城市 $i$ 与城市 $i + 1$ 有**双向**道路相连。 该国发生了疫情,一个城市要么无人感染,要么全体感染。具体地,一个城市初始时被感染当且仅当 $s_i = 1$。 疫情会扩散,每一天上午,你可以为一个未感染的城市的居民接种疫苗,下午,每个被感染的城市会向相邻的城市扩散,如果相邻的城市未接种疫苗,它将立即全员",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9046"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "某国有 $n$ 座城市,其中 $\\forall 1 \\leq i < n$,城市 $i$ 与城市 $i + 1$ 有**双向**道路相连。\n\n该国发生了疫情,一个城市要么无人感染,要么全体感染。具体地,一个城市初始时被感染当且仅当 $s_i = 1$。\n\n疫情会扩散,每一天上午,你可以为一个未感染的城市的居民接种疫苗,下午,每个被感染的城市会向相邻的城市扩散,如果相邻的城市未接种疫苗,它将立即全员...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments