企业官网建设流程全解析

题目描述

给定一个由字符'0'、'1'和'?'组成的字符串sss，长度在111到10410^4104之间。其中'?'表示该位置可以任意替换为'0'或'1'。

定义hhh序列为满足以下文法的字符串：

⟨hseq⟩::=0∣1 ⟨hseq⟩ ⟨hseq⟩ \langle hseq \rangle ::= 0 \quad \mid \quad 1 \; \langle hseq \rangle \; \langle hseq \rangle⟨hseq⟩::=0∣1⟨hseq⟩⟨hseq⟩

也就是说，一个hhh序列要么是单个字符'0'，要么是字符'1'后紧跟两个hhh序列。

给定一个带有通配符的模式串sss，我们可以将每个'?'独立地替换为'0'或'1'，得到一个具体的二进制串。然后，我们将这个二进制串切分成若干个连续的hhh序列。要求计算在所有可能的替换方式中，能够切分出的最大hhh序列数量。

输入格式

输入包含多个测试用例，每个测试用例占一行，包含一个由字符'0'、'1'和'?'组成的字符串sss，长度在111到10410^4104之间（含）。输入以EOF\texttt{EOF}EOF结束。

输出格式

对于每个测试用例，输出一行一个整数，表示能够得到的最大hhh序列数量。

样例

输入

0 10100 ??1?? ??1?? 17010100 ??1????

输出

1 1 0 2 2 6

题目分析

本题的核心是：给定一个带有通配符的模式串，我们要选择一种通配符的填充方式，使得填充后的串能够被分割成尽可能多的hhh序列。

首先需要理解hhh序列的结构。根据文法：

⟨hseq⟩::=0∣1 ⟨hseq⟩ ⟨hseq⟩ \langle hseq \rangle ::= 0 \mid 1 \; \langle hseq \rangle \; \langle hseq \rangle⟨hseq⟩::=0∣1⟨hseq⟩⟨hseq⟩

这实际上定义了一种完全二叉树的先序遍历编码：'0'表示一个叶子节点，'1'表示一个内部节点，该内部节点后面紧跟两个子树（即两个hhh序列）。因此，一个二进制串是hhh序列当且仅当它可以被解析为一棵完全二叉树。

我们可以用一个“需求”计数器need\textit{need}need来判定一个具体二进制串是否为hhh序列：

• 初始need=1\textit{need} = 1need=1，表示我们还需要一棵完整的树。
• 从左到右扫描每个字符：
  • 遇到'0'：完成一个叶子，need←need−1\textit{need} \leftarrow \textit{need} - 1need←need−1。
  • 遇到'1'：消耗一个位置作为内部节点，该节点需要两个子树，因此need←need+1\textit{need} \leftarrow \textit{need} + 1need←need+1。
• 过程中必须始终保持need≥1\textit{need} \ge 1need≥1（因为不能有多余的未完成子树），最终need\textit{need}need必须等于000。

例如，对于串"11000"：

• 初始need=1\textit{need} = 1need=1
• '1'→need=2\textit{need} = 2need=2
• '1'→need=3\textit{need} = 3need=3
• '0'→need=2\textit{need} = 2need=2
• '0'→need=1\textit{need} = 1need=1
• '0'→need=0\textit{need} = 0need=0，合法。

对于带通配符的串，我们需要判断是否存在一种填充方式，使得上述过程成立。

由于要最大化分割段数，一个自然的想法是：当need\textit{need}need可以变成000时，我们就结束当前段，因为越早结束，段数越多。但直接贪心可能会失败，因为过早结束可能导致剩余部分无法被完全分割。因此，我们需要动态规划来确定所有可行的分割方案。

解题思路

子串可匹配性判定

对于任意子串s[l…r]s[l \ldots r]s[l…r]，我们希望判断它是否能够被填充为一个hhh序列。我们可以用一个区间[L,R][L, R][L,R]来表示当前所有可能的need\textit{need}need值（均为正整数），并单独判断need=0\textit{need} = 0need=0是否可达。

扫描子串时，根据当前字符更新状态：

• 若字符为'1'：所有need\textit{need}need值都增加111，因为'1'会使需求增加。
• 若字符为'0'：所有need\textit{need}need值都减少111，但need=1\textit{need} = 1need=1会变成000，此时000可达，表示可以结束该段。
• 若字符为'?'：可以选择将其视为'0'或'1'，因此need\textit{need}need可以减111或加111，状态区间会相应扩展。

通过维护这个区间，我们可以在O(1)O(1)O(1)时间内判断任意子串是否可匹配为hhh序列。

动态规划分割

设dp[i]\textit{dp}[i]dp[i]表示前缀s[0…i−1]s[0 \ldots i-1]s[0…i−1]能够分割出的最大hhh序列数量。如果该前缀无法被完全分割，则dp[i]=−1\textit{dp}[i] = -1dp[i]=−1。

初始化dp[0]=0\textit{dp}[0] = 0dp[0]=0。

对于每个起始位置iii（0≤i<n0 \le i < n0≤i<n），如果dp[i]≥0\textit{dp}[i] \ge 0dp[i]≥0，则从iii开始向右扩展子串，同时维护状态区间。每当need=0\textit{need} = 0need=0可达时，说明子串s[i…j]s[i \ldots j]s[i…j]可以成为一个hhh序列，此时更新：

dp[j+1]=max⁡(dp[j+1],dp[i]+1) \textit{dp}[j+1] = \max(\textit{dp}[j+1], \textit{dp}[i] + 1)dp[j+1]=max(dp[j+1],dp[i]+1)

继续扩展以考虑更长的子串。如果状态区间变为空（即没有任何正整数的need\textit{need}need可行），则停止扩展，因为更长的子串不可能再成为hhh序列。

最终答案为dp[n]\textit{dp}[n]dp[n]，若为−1-1−1则输出000。

复杂度分析

• 枚举所有起始位置iii：O(n)O(n)O(n)。
• 每个起始位置最多扩展n−in-in−i次，总扩展次数为O(n2)O(n^2)O(n2)。
• 每次扩展只进行常数次整数运算。
• 总时间复杂度：O(n2)O(n^2)O(n2)，其中n≤104n \le 10^4n≤104，最坏情况下约10810^8108次操作，在合理优化下可通过。
• 空间复杂度：O(n)O(n)O(n)，用于存储dp\textit{dp}dp数组。

代码实现

// Gödel's Dream// UVa ID: 12638// Verdict: Accepted// Submission Date: 2026-06-17// UVa Run Time: 0.210s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintINF=1e9;intmain(){ios::sync_with_stdio(false);cin.tie(0);string s;while(cin>>s){intn=(int)s.size();vector<int>dp(n+1,-1);dp[0]=0;for(inti=0;i<n;++i){if(dp[i]==-1)continue;intL=1,R=1;// 当前可能的 need 值区间 [L, R]for(intj=i;j<n;++j){charch=s[j];boolcanZero=false;intnewL,newR;if(ch=='1'){// 遇到 '1'：need 增加 1newL=L+1;newR=R+1;canZero=false;}elseif(ch=='0'){// 遇到 '0'：need 减少 1if(L==1)canZero=true;// need=1 减 1 得 0elsecanZero=false;if(L<=1){// need=1 会变成 0，只有 need>=2 才能保留为正整数if(R>=2){newL=1;newR=R-1;}else{newL=INF;newR=-INF;// 空状态}}else{newL=L-1;newR=R-1;}}else{// ch == '?'// '?' 可以选择变成 '0' 或 '1'canZero=(L==1);// 若 need=1，选择 '0' 可得 0// 计算选择 '0'（减 1）的部分intleft1,right1;if(L>=2){left1=L-1;right1=R-1;}else{// L == 1，need=1 减 1 得 0，不保留if(R>=2){left1=1;right1=R-1;}else{left1=INF;right1=-INF;}}// 计算选择 '1'（加 1）的部分intleft2=L+1;intright2=R+1;// 合并两个区间if(left1<=right1){newL=min(left1,left2);newR=max(right1,right2);}else{newL=left2;newR=right2;}}// 如果 0 可达，说明当前子串 s[i..j] 可以成为一个 h 序列if(canZero){dp[j+1]=max(dp[j+1],dp[i]+1);}L=newL;R=newR;// 状态为空，无法继续扩展if(L>R)break;}}cout<<(dp[n]==-1?0:dp[n])<<'\n';}return0;}

总结

本题的关键点在于：

1. 理解文法结构：将hhh序列转化为完全二叉树的先序遍历，并用“需求计数器”need\textit{need}need来判定合法性。
2. 区间状态表示：由于通配符'?'的存在，我们无法确定唯一的need\textit{need}need值，因此需要维护一个可能的need\textit{need}need值区间，并单独标记need=0\textit{need} = 0need=0是否可达。
3. 动态规划：采用区间DP\texttt{DP}DP枚举所有可能的子串，并利用dp\textit{dp}dp数组记录前缀的最优分割数，从而得到全局最优解。
4. 复杂度控制：O(n2)O(n^2)O(n2)的复杂度在n=104n = 10^4n=104时可通过，但需要常数优化。

本题融合了形式语言、自动机思想和动态规划，是一道综合性较强的字符串题目。掌握区间状态压缩的技巧，对于处理带有通配符的字符串匹配问题具有普适性的参考价值。