题目描述给定一个由字符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序列初始need1\textit{need} 1need1表示我们还需要一棵完整的树。从左到右扫描每个字符遇到0完成一个叶子need←need−1\textit{need} \leftarrow \textit{need} - 1need←need−1。遇到1消耗一个位置作为内部节点该节点需要两个子树因此need←need1\textit{need} \leftarrow \textit{need} 1need←need1。过程中必须始终保持need≥1\textit{need} \ge 1need≥1因为不能有多余的未完成子树最终need\textit{need}need必须等于000。例如对于串11000初始need1\textit{need} 1need11→need2\textit{need} 2need21→need3\textit{need} 3need30→need2\textit{need} 2need20→need1\textit{need} 1need10→need0\textit{need} 0need0合法。对于带通配符的串我们需要判断是否存在一种填充方式使得上述过程成立。由于要最大化分割段数一个自然的想法是当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值均为正整数并单独判断need0\textit{need} 0need0是否可达。扫描子串时根据当前字符更新状态若字符为1所有need\textit{need}need值都增加111因为1会使需求增加。若字符为0所有need\textit{need}need值都减少111但need1\textit{need} 1need1会变成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。对于每个起始位置iii0≤in0 \le i n0≤in如果dp[i]≥0\textit{dp}[i] \ge 0dp[i]≥0则从iii开始向右扩展子串同时维护状态区间。每当need0\textit{need} 0need0可达时说明子串s[i…j]s[i \ldots j]s[i…j]可以成为一个hhh序列此时更新dp[j1]max⁡(dp[j1],dp[i]1) \textit{dp}[j1] \max(\textit{dp}[j1], \textit{dp}[i] 1)dp[j1]max(dp[j1],dp[i]1)继续扩展以考虑更长的子串。如果状态区间变为空即没有任何正整数的need\textit{need}need可行则停止扩展因为更长的子串不可能再成为hhh序列。最终答案为dp[n]\textit{dp}[n]dp[n]若为−1-1−1则输出000。复杂度分析枚举所有起始位置iiiO(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ödels Dream// UVa ID: 12638// Verdict: Accepted// Submission Date: 2026-06-17// UVa Run Time: 0.210s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF1e9;intmain(){ios::sync_with_stdio(false);cin.tie(0);string s;while(cins){intn(int)s.size();vectorintdp(n1,-1);dp[0]0;for(inti0;in;i){if(dp[i]-1)continue;intL1,R1;// 当前可能的 need 值区间 [L, R]for(intji;jn;j){charchs[j];boolcanZerofalse;intnewL,newR;if(ch1){// 遇到 1need 增加 1newLL1;newRR1;canZerofalse;}elseif(ch0){// 遇到 0need 减少 1if(L1)canZerotrue;// need1 减 1 得 0elsecanZerofalse;if(L1){// need1 会变成 0只有 need2 才能保留为正整数if(R2){newL1;newRR-1;}else{newLINF;newR-INF;// 空状态}}else{newLL-1;newRR-1;}}else{// ch ?// ? 可以选择变成 0 或 1canZero(L1);// 若 need1选择 0 可得 0// 计算选择 0减 1的部分intleft1,right1;if(L2){left1L-1;right1R-1;}else{// L 1need1 减 1 得 0不保留if(R2){left11;right1R-1;}else{left1INF;right1-INF;}}// 计算选择 1加 1的部分intleft2L1;intright2R1;// 合并两个区间if(left1right1){newLmin(left1,left2);newRmax(right1,right2);}else{newLleft2;newRright2;}}// 如果 0 可达说明当前子串 s[i..j] 可以成为一个 h 序列if(canZero){dp[j1]max(dp[j1],dp[i]1);}LnewL;RnewR;// 状态为空无法继续扩展if(LR)break;}}cout(dp[n]-1?0:dp[n])\n;}return0;}总结本题的关键点在于理解文法结构将hhh序列转化为完全二叉树的先序遍历并用“需求计数器”need\textit{need}need来判定合法性。区间状态表示由于通配符?的存在我们无法确定唯一的need\textit{need}need值因此需要维护一个可能的need\textit{need}need值区间并单独标记need0\textit{need} 0need0是否可达。动态规划采用区间DP\texttt{DP}DP枚举所有可能的子串并利用dp\textit{dp}dp数组记录前缀的最优分割数从而得到全局最优解。复杂度控制O(n2)O(n^2)O(n2)的复杂度在n104n 10^4n104时可通过但需要常数优化。本题融合了形式语言、自动机思想和动态规划是一道综合性较强的字符串题目。掌握区间状态压缩的技巧对于处理带有通配符的字符串匹配问题具有普适性的参考价值。