[UESTCPC 2024] 消消乐

Luogu
IDLGP10331
Time1000ms
Memory256MB
DifficultyP5
2024O2优化高校校赛
bjh 有一个长度为 $n$ 的只由字符 ```0``` 和 ```1``` 构成的字符串 $s$。 bjh 的每次操作可以选择一个长度**大于 1** 的极大的只包含一种字符的子串,将这一整个子串修改为与其中字符相反的一个字符(如 $11001$ 一次操作后可以改为 $0001$ 或 $1111$)。 bjh 会一直操作下去,直到字符串无法再被操作,请帮他找到所有操作方案中最大操作次数和最小操作次数的差值。 ## Input 本题包含多组数据。第一行输入一个整数 $T$ $(1\leq T\leq 10^4)$,表示数据组数。 对于每组数据,第一行输入一个整数 $n$ $(1\leq n\leq 10^5)$,表示字符串的长度。 第二行输入一个字符串 $s$,表示初始的字符串。 保证所有数据的 $n$ 之和不超过 $10^6$。 ## Output 对于每组数据,输出一个整数,表示最大操作次数和最小操作次数的差值。 [samples]
Samples
Input #1
2
5
11001
5
11000
Output #1
1
0
API Response (JSON)
{
  "problem": {
    "name": "[UESTCPC 2024] 消消乐",
    "description": {
      "content": "bjh 有一个长度为 $n$ 的只由字符 ```0``` 和 ```1``` 构成的字符串 $s$。 bjh 的每次操作可以选择一个长度**大于 1** 的极大的只包含一种字符的子串,将这一整个子串修改为与其中字符相反的一个字符(如 $11001$ 一次操作后可以改为 $0001$ 或 $1111$)。 bjh 会一直操作下去,直到字符串无法再被操作,请帮他找到所有操作方案中最大操作次数和最小",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10331"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "bjh 有一个长度为 $n$ 的只由字符 ```0``` 和 ```1``` 构成的字符串 $s$。\n\nbjh 的每次操作可以选择一个长度**大于 1** 的极大的只包含一种字符的子串,将这一整个子串修改为与其中字符相反的一个字符(如 $11001$ 一次操作后可以改为 $0001$ 或 $1111$)。\n\nbjh 会一直操作下去,直到字符串无法再被操作,请帮他找到所有操作方案中最大操作次数和最小...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments