题目链接
题目描述
给定一个命令行格式的模板字符串，该模板由关键字、抉择结构 { A | B | ... } 和可选结构 [ C ] 构成。任务是：
- 找出所有在顶层（不被任何括号包裹）定义的“固定关键字”。
- 计算每个固定关键字在任何合法命令中都保证会出现的最小次数。
保证出现次数的计算规则是递归的：
- 一个关键字的保证次数，首先是它作为固定关键字出现的次数。
- 如果一个抉择结构
{ A | B | ... }的每一个选项中，该关键字都保证会出现（即递归计算次数），那么这个抉择结构会为该关键字的保证次数贡献
+1。 - 可选结构
[ C ]内部的任何内容都不被视为保证出现。
解题思路
这是一个典型的递归结构字符串解析问题。我们可以设计一个递归函数，通过“分治”的思想来解决。该函数负责解析一个给定的模板（或子模板）字符串，并计算其中各个关键字的保证出现次数。
核心算法：递归解析与记忆化搜索
-
定义递归函数： 设计一个函数，例如
solve(substring)，它的功能是接收一个模板字符串substring，返回一个哈希表（map），记录该子串中每个关键字保证出现的次数。 -
顶层元素切分： 在
solve函数内部，首先需要将substring切分成顶层的、互不相关的几个部分。例如，对于"a { b | c } [d]"，顶层部分就是"a"、"{ b | c }"和"[d]"。这需要一个辅助函数，通过扫描字符串并维护一个嵌套层级计数器来实现，只在层级为0时进行切分。 -
递归计算： 遍历切分出的顶层部分：
- 如果是关键字：直接在结果哈希表中为该关键字的计数值
+1。 - 如果是抉择结构
{...}： a. 提取括号内的内容，并根据|符号（同样只在顶层）将其切分成多个选项。 b. 对每一个选项字符串，递归调用solve函数，得到每个选项的保证次数哈希表。 c. 现在，要找出哪些关键字在所有选项中都“保证出现”。遍历第一个选项结果中的所有关键字，检查它是否存在于所有其他选项的结果中（即保证次数solve函数的结果哈希表中为其计数值+1。 - 如果是可选结构
[...]：直接忽略，因为它对保证出现次数没有贡献。
- 如果是关键字：直接在结果哈希表中为该关键字的计数值
-
记忆化： 为了避免对相同的子模板重复计算，使用一个哈希表作为缓存（记忆化）。在
solve函数的入口处，检查当前子串是否已经计算过，如果计算过，则直接返回缓存的结果。这能将时间复杂度从指数级显著降低到多项式级。 -
主流程： a. 找出固定关键字：首先独立地遍历一遍输入字符串，通过记录嵌套层级，找出所有层级为0的关键字，按顺序存储起来。 b. 计算总次数：调用
solve(完整输入字符串)得到全局的保证次数哈希表。 c. 输出结果：按顺序输出固定关键字，并从全局哈希表中查找它们对应的保证次数进行输出。
通过这种方式，我们可以清晰地处理复杂的嵌套结构，并高效地得出最终结果。
代码
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
using namespace std;
map<string, map<string, int>> memo;
// 查找匹配的括号
int find_closing_bracket(const string& s, int start, char open, char close) {
int level = 0;
for (int i = start; i < s.length(); ++i) {
if (s[i] == open) level++;
if (s[i] == close) level--;
if (level == 0) return i;
}
return -1;
}
// 递归解析函数
map<string, int> solve(string s) {
if (memo.count(s)) {
return memo[s];
}
map<string, int> counts;
int i = 0;
while (i < s.length()) {
if (isspace(s[i])) {
i++;
continue;
}
if (isalpha(s[i])) {
string keyword;
while (i < s.length() && isalpha(s[i])) {
keyword += s[i];
i++;
}
counts[keyword]++;
} else if (s[i] == '{') {
int end = find_closing_bracket(s, i, '{', '}');
string content = s.substr(i + 1, end - i - 1);
vector<string> options;
int start = 0;
int level = 0;
for(int j = 0; j < content.length(); ++j) {
if(content[j] == '{' || content[j] == '[') level++;
else if(content[j] == '}' || content[j] == ']') level--;
else if(content[j] == '|' && level == 0) {
options.push_back(content.substr(start, j - start));
start = j + 1;
}
}
options.push_back(content.substr(start));
if (!options.empty()) {
vector<map<string, int>> option_counts;
for (const auto& opt : options) {
option_counts.push_back(solve(opt));
}
for (auto const& [key, val] : option_counts[0]) {
if (val > 0) {
bool in_all = true;
for (size_t k = 1; k < option_counts.size(); ++k) {
if (option_counts[k].find(key) == option_counts[k].end() || option_counts[k][key] == 0) {
in_all = false;
break;
}
}
if (in_all) {
counts[key]++;
}
}
}
}
i = end + 1;
} else if (s[i] == '[') {
i = find_closing_bracket(s, i, '[', ']') + 1;
} else {
i++;
}
}
return memo[s] = counts;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
string line;
getline(cin, line);
vector<string> fixed_keywords;
int level = 0;
for (int i = 0; i < line.length(); ) {
if (isspace(line[i])) {
i++;
continue;
}
if (line[i] == '{' || line[i] == '[') {
level++; i++;
} else if (line[i] == '}' || line[i] == ']') {
level--; i++;
} else if (isalpha(line[i]) && level == 0) {
string keyword;
while(i < line.length() && isalpha(line[i])) {
keyword += line[i];
i++;
}
fixed_keywords.push_back(keyword);
} else {
i++;
}
}
map<string, int> total_counts = solve(line);
for (size_t i = 0; i < fixed_keywords.size(); ++i) {
cout << fixed_keywords[i] << (i == fixed_keywords.size() - 1 ? "" : " ");
}
cout << "\n";
for (size_t i = 0; i < fixed_keywords.size(); ++i) {
cout << (total_counts.count(fixed_keywords[i]) ? total_counts[fixed_keywords[i]] : 0) << (i == fixed_keywords.size() - 1 ? "" : " ");
}
cout << "\n";
return 0;
}
import java.util.*;
public class Main {
// 记忆化缓存，存储已计算过的子串及其结果
private static Map<String, Map<String, Integer>> memo = new HashMap<>();
// 查找匹配的括号
private static int findClosingBracket(String s, int start, char open, char close) {
int level = 0;
for (int i = start; i < s.length(); i++) {
if (s.charAt(i) == open) level++;
if (s.charAt(i) == close) level--;
if (level == 0) return i;
}
return -1;
}
// 递归解析函数
private static Map<String, Integer> solve(String s) {
s = s.trim();
if (memo.containsKey(s)) {
return memo.get(s);
}
Map<String, Integer> counts = new HashMap<>();
int i = 0;
while (i < s.length()) {
char ch = s.charAt(i);
if (Character.isWhitespace(ch)) {
i++;
continue;
}
if (Character.isLetter(ch)) {
StringBuilder keyword = new StringBuilder();
while (i < s.length() && Character.isLetter(s.charAt(i))) {
keyword.append(s.charAt(i));
i++;
}
String kw = keyword.toString();
counts.put(kw, counts.getOrDefault(kw, 0) + 1);
} else if (ch == '{') {
int end = findClosingBracket(s, i, '{', '}');
String content = s.substring(i + 1, end).trim();
List<String> options = new ArrayList<>();
int start = 0;
int level = 0;
for (int j = 0; j < content.length(); j++) {
char c = content.charAt(j);
if (c == '{' || c == '[') level++;
else if (c == '}' || c == ']') level--;
else if (c == '|' && level == 0) {
options.add(content.substring(start, j).trim());
start = j + 1;
}
}
options.add(content.substring(start).trim());
if (!options.isEmpty()) {
List<Map<String, Integer>> optionCounts = new ArrayList<>();
for (String opt : options) {
optionCounts.add(solve(opt));
}
for (String key : optionCounts.get(0).keySet()) {
if (optionCounts.get(0).get(key) > 0) {
boolean inAll = true;
for (int k = 1; k < optionCounts.size(); k++) {
if (optionCounts.get(k).getOrDefault(key, 0) == 0) {
inAll = false;
break;
}
}
if (inAll) {
counts.put(key, counts.getOrDefault(key, 0) + 1);
}
}
}
}
i = end + 1;
} else if (ch == '[') {
i = findClosingBracket(s, i, '[', ']') + 1;
} else {
i++;
}
}
memo.put(s, counts);
return counts;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
List<String> fixedKeywords = new ArrayList<>();
int level = 0;
for (int i = 0; i < line.length(); ) {
char ch = line.charAt(i);
if (Character.isWhitespace(ch)) {
i++; continue;
}
if (ch == '{' || ch == '[') {
level++; i++;
} else if (ch == '}' || ch == ']') {
level--; i++;
} else if (Character.isLetter(ch) && level == 0) {
StringBuilder keyword = new StringBuilder();
while (i < line.length() && Character.isLetter(line.charAt(i))) {
keyword.append(line.charAt(i));
i++;
}
String kw = keyword.toString();
fixedKeywords.add(kw);
} else {
i++;
}
}
Map<String, Integer> totalCounts = solve(line);
System.out.println(String.join(" ", fixedKeywords));
List<String> resultCounts = new ArrayList<>();
for (String kw : fixedKeywords) {
resultCounts.add(String.valueOf(totalCounts.getOrDefault(kw, 0)));
}
System.out.println(String.join(" ", resultCounts));
}
}
import sys
# 记忆化缓存
memo = {}
def solve(s: str) -> dict:
# 递归解析函数
s = s.strip()
if s in memo:
return memo[s]
if not s:
return {}
counts = {}
i = 0
while i < len(s):
if s[i].isspace():
i += 1
continue
if s[i].isalpha():
start = i
while i < len(s) and s[i].isalpha():
i += 1
keyword = s[start:i]
counts[keyword] = counts.get(keyword, 0) + 1
elif s[i] == '{':
start = i
level = 1
i += 1
while i < len(s) and level > 0:
if s[i] == '{': level += 1
elif s[i] == '}': level -= 1
i += 1
content = s[start+1:i-1].strip()
# 按顶层的 '|' 分割选项
options = []
opt_start = 0
level = 0
for j, char in enumerate(content):
if char in '{[': level += 1
elif char in '}]': level -= 1
elif char == '|' and level == 0:
options.append(content[opt_start:j])
opt_start = j + 1
options.append(content[opt_start:])
if options:
option_counts = [solve(opt) for opt in options]
first_option_keywords = option_counts[0].keys()
for kw in first_option_keywords:
if all(opt_map.get(kw, 0) > 0 for opt_map in option_counts):
counts[kw] = counts.get(kw, 0) + 1
elif s[i] == '[':
level = 1
i += 1
while i < len(s) and level > 0:
if s[i] == '[': level += 1
elif s[i] == ']': level -= 1
i += 1
else:
i += 1
memo[s] = counts
return counts
def main():
line = input()
fixed_keywords = []
level = 0
i = 0
while i < len(line):
if line[i].isspace():
i += 1
continue
if line[i] in '{[':
level += 1
i += 1
elif line[i] in '}]':
level -= 1
i += 1
elif line[i].isalpha() and level == 0:
start = i
while i < len(line) and line[i].isalpha():
i += 1
keyword = line[start:i]
fixed_keywords.append(keyword)
else:
i += 1
total_counts = solve(line)
print(' '.join(fixed_keywords))
result_counts = [str(total_counts.get(kw, 0)) for kw in fixed_keywords]
print(' '.join(result_counts))
if __name__ == "__main__":
main()
算法及复杂度
- 算法：递归下降解析 (Recursive Descent Parsing) + 记忆化搜索 (Memoization)
- 时间复杂度：
，其中
是输入模板字符串的长度。状态数（不同子串的数量）为
。在每个状态中，我们需要对子串进行一次扫描和切分，这需要
的时间。因此，总体时间复杂度约为
。由于记忆化的存在，每个子问题的解只会被计算一次。
- 空间复杂度：
京公网安备 11010502036488号