UVA - 11920 0 s, 1 s and ? Marks

2024-06-05 21:48

文章标签 uva marks 11920

本文主要是介绍UVA - 11920 0 s, 1 s and ? Marks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

0 s, 1 s and ? Marks

Given a string consisting of 0, 1 and ? only, change all the ? to 0/1, so that the size of the largest group is minimized. A group is a substring that contains either all zeros or all ones.

Consider the following example:

0 1 1 ? 0 1 0 ? ? ?

We can replace the question marks (?) to get

0 1 1 0 0 1 0 1 0 0

The groups are (0) (1 1) (0 0) (1) (0) (1) (0 0) and the corresponding sizes are 1, 2, 2, 1, 1, 1, 2. That means the above replacement would give us a maximum group size of 2. In fact, of all the 2⁴ possible replacements, we won't get any maximum group size that is smaller than 2.

Input

The first line of input is an integer T (T $\le$ 5000) that indicates the number of test cases. Each case is a line consisting of a string that contains 0, 1 and ? only. The length of the string will be in the range [1,1000].

Output

For each case, output the case number first followed by the size of the minimized largest group.

Sample Input

4
011?010???
???
000111
00000000000000

Sample Output

Case 1: 2
Case 2: 1
Case 3: 3
Case 4: 14

题意：给定一个带问号的01串，把每个问号替换成0或1，让最长的“连续的相同数字串”尽量短

思路：最大的最小采用二分，至于判断的时候，每个位置要么是0要么是1，根据情况判断

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;int dp[maxn][2];
char str[maxn];
int n;int check(int len) {dp[0][0] = dp[0][1] = 0;for (int i = 1; i <= n; i++) {dp[i][0] = dp[i][1] = -1;if (str[i] != '0') {if (dp[i-1][0] >= 0)dp[i][1] = 1;if (dp[i-1][1] >= 0 && dp[i-1][1]+1 <= len && dp[i][1] == -1)	dp[i][1] = dp[i-1][1] + 1;}if (str[i] != '1') {if (dp[i-1][1] >= 0)dp[i][0] = 1;if (dp[i-1][0] >= 0 && dp[i-1][0]+1 <= len && dp[i][0] == -1)dp[i][0] = dp[i-1][0] + 1;}if (dp[i][1] == -1 && dp[i][0] == -1)return 0;}return 1;
}int main() {int t, cas = 1;scanf("%d", &t);while (t--) {scanf("%s", str+1);n = strlen(str+1);int l = 1, r = n;while (l <= r) {int m = l + r >> 1;if (check(m))r = m-1;else l = m + 1;}printf("Case %d: %d\n", cas++, l);}return 0;
}

这篇关于UVA - 11920 0 s, 1 s and ? Marks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！