Znzryb's Blog
0%

Starters-234-Swapping Operations

Posted on

题目大意

题意总结

给定长度为 N 的字符串 S，字符只可能是 0、1、?。

把所有 ? 分别替换成 0 或 1 后，会得到一个二进制串。

定义“好串”为：所有 1 必须恰好出现在一个连续子串中（可以没有 1，也可以全是 1）。

对一个确定的二进制串，定义 f(S) 为把它变成“好串”的最少操作次数。

一次操作是：选 1 ≤ i < j ≤ N，交换 S[i] 和 S[j]。

每个测试用例要求输出两件事：

  • 在所有可能替换方案里，f(S) 的最小可能值

  • 在所有可能替换方案里，f(S) 的最大可能值

输入格式

  • 第一行：整数 T，表示测试用例数。

  • 每个测试用例两行：

    • 第一行：整数 N
    • 第二行：长度为 N 的字符串 S

输出格式

每个测试用例输出一行两个整数：min_f max_f，分别表示最小和最大可能的 f(S)。

数据范围

  • 1 ≤ T ≤ 100

  • 2 ≤ N ≤ 2000

  • S[i] ∈ {0,1,?}

  • 所有测试用例的 N 之和不超过 2000

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Input
6
3
1?1
5
1?0?1
7
1?0101?
9
?????????
8
11010101
6
??011?

Output
0 1
1 1
1 2
0 3
2 2
0 1

样例说明（按测试点）

  • 第 1 组：1?1

    • 最小值：取 111，已经是好串，f=0
    • 最大值：取 101，最少交换 1 次变好串，f=1
    • 所以输出 0 1

  • 第 2 组：1?0?1

    • 无论怎么填，f 的最小和最大都为 1
    • 输出 1 1

  • 第 3 组：1?0101?

    • 可构造到 f=1（如 1101010）
    • 也可构造到 f=2（如 1101011）
    • 输出 1 2

  • 第 4 组：?????????

    • 最小可到 0（如全 0 或全 1）
    • 最大可到 3（如 111000111）
    • 输出 0 3

  • 第 5 组：11010101

    • 没有 ?，串固定，f 唯一为 2
    • 输出 2 2

  • 第 6 组：??011?

    • 最小可到 0
    • 最大可到 1
    • 输出 0 1

思路讲解

AC代码

心路历程（WA，TLE，MLE……）