第十四届蓝桥杯省赛真题——填充（AC）

短命女 2024-04-20 11:57 92阅读 0赞

#### 目录 ####

*  1. 填充
 *   *  1. 问题描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 样例输入
     *  5. 样例输出
     *  6. 样例说明
     *  7. 评测用例规模与约定
     *  8. 原题链接
 *  2. 解题思路
 *  3. AC\_Code

## 1. 填充 ##

前置知识点：动态规划、贪心

### 1. 问题描述 ###

有一个长度为  n n n 的  01 01 01 串，其中有一些位置标记为  ? ? ?，这些位置上可以任意填充  0 0 0 或者  1 1 1，请问如何填充这些位置使得这个  01 01 01 串中出现互不重叠的  00 00 00 和  11 11 11 子串最多，输出子串个数。

### 2. 输入格式 ###

输入一行包含一个字符串。

### 3. 输出格式 ###

输出一行包含一个整数表示答案。

### 4. 样例输入 ###

1110?0

### 5. 样例输出 ###

### 6. 样例说明 ###

如果在问号处填  0 0 0 ，则最多出现一个  00 00 00 和一个  11 11 11： 111000 111000 111000。

### 7. 评测用例规模与约定 ###

对于所有评测用例， 1 ≤ n ≤ 1 0 6 1 \\leq n \\leq 10^6 1≤n≤106。

### 8. 原题链接 ###

[填充][Link 1]

## 2. 解题思路 ##

考虑使用动态规划解决问题。定义  f i f\_i fi 表示只考虑  S S S 的前  i i i 个字符时可凑出的最多  00 00 00 或  11 11 11 子串。

首先，对于状态初始化有： f 0 = f 1 = 0 f\_0=f\_1=0 f0=f1=0，因为长度不足  2 2 2 所以一定无法凑出  00 00 00 或  11 11 11。

接下来考虑状态转移方程，当  i ≥ 2 i \\ge 2 i≥2 时我们讨论  S i S\_i Si 和  S i − 1 S\_\{i-1\} Si−1 的关系：

*  若  S i S\_i Si 与  S i − 1 S\_\{i-1\} Si−1 其中一个等于 `?` 或者  S i = S i − 1 S\_i=S\_\{i-1\} Si=Si−1，此时  S i S\_i Si 和  S i − 1 S\_\{i-1\} Si−1 可以凑成一对，即可以得到转移方程：  
     f i = f i − 2 + 1 f\_i=f\_\{i-2\}+1 fi=fi−2\+1
 *  若  S i S\_i Si 与  S i − 1 S\_\{i-1\} Si−1 的关系不满足上述条件，则说明无法凑成一对，即有转移方程：  
     f i = f i − 1 f\_i=f\_\{i-1\} fi=fi−1

最终答案即为  f n f\_n fn，时间复杂度： O ( n ) O(n) O(n)。

本题也可以通过贪心思路，从左往右两个两个字符进行考虑，若可凑成一对即凑成一对，最终可凑出的最大对数即为答案。

## 3. AC\_Code ##

*  C++

#include<bits/stdc++.h>
    using namespace std;
    
    string s;
    int main()
    {
        
    	cin >> s;
    	int n = (int)s.size();
    	s = '?' + s;
    	vector<int> f(n + 1);
    	for (int i = 2; i <= n; ++i) {
        
    		if (s[i - 1] == '?' || s[i] == '?' || (s[i] == s[i - 1])) {
        
    			f[i] =  f[i - 2] + 1;
    		} else {
        
    			f[i] = f[i - 1];
    		}
    	}
    	cout << f[n] << '\n';
    	return 0;
    }

*  Java

import java.util.Scanner;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.next();
            int n = s.length();
            s = "?" + s;
            int[] f = new int[n + 1];
            for (int i = 2; i <= n; ++i) {
        
                if (s.charAt(i - 1) == '?' || s.charAt(i) == '?' || (s.charAt(i) == s.charAt(i - 1))) {
        
                    f[i] = f[i - 2] + 1;
                } else {
        
                    f[i] = f[i - 1];
                }
            }
            System.out.println(f[n]);
        }
    }

*  Python

s = input()
    n = len(s)
    s = '?' + s
    f = [0] * (n + 1)
    for i in range(2, n + 1):
        if s[i - 1] == '?' or s[i] == '?' or (s[i] == s[i - 1]):
            f[i] = f[i - 2] + 1
        else:
            f[i] = f[i - 1]
    print(f[n])

[Link 1]: https://www.lanqiao.cn/problems/3519/learning/