古代咒语共鸣匹配
题目描述
给定一段卷轴文本和若干条咒语，计算每条咒语与卷轴文本的共鸣分数。
共鸣分数 = 匹配度 × 总位置能量，截断到 4 位小数（向下取整，不四舍五入）。
匹配度按优先级判断：
| 等级 | 条件 | 得分 |
|---|---|---|
| 完美谐振 | 咒语所有符文在卷轴中以相同顺序出现（可不相邻） | |
| 部分谐振 | 咒语所有符文都能在卷轴中找到，但顺序不一致 | |
| 微弱回响 | 只有部分符文能找到 | |
| 静默 | 无任何匹配 |
其中 为咒语符文总数（含重复），
为咒语中能在卷轴找到的符文数（含重复）。
位置能量：对于在卷轴中（长度 ）匹配到的每个唯一符文，取其第一次出现的位置
（0-索引），贡献
。当
时
。
匹配过程忽略大小写，符文需要去除非字母数字字符后再比较。
思路分析
这道题没有复杂的算法，但细节很多，属于模拟实现类题目。关键是把每个步骤拆清楚。
第一步：预处理卷轴文本。 按空格拆分成单词数组，对每个单词去掉非字母数字字符并转小写。用哈希表记录每个单词第一次出现的位置，同时维护一个集合方便快速查找。
第二步：对每条咒语做三件事。
- 判断匹配类型。 先看咒语的所有唯一单词是否都在卷轴集合中。如果不全在，再看是否一个都没有——区分「微弱回响」和「静默」。如果全部都在，做子序列检查：用双指针扫描卷轴数组，看咒语的完整单词序列（含重复）是否是卷轴的子序列，从而区分「完美谐振」和「部分谐振」。
- 计算位置能量。 只对咒语中出现在卷轴里的那些唯一单词，取它们在卷轴中第一次出现的位置，套公式求和。
- 算最终分数。 匹配度乘以位置能量，乘 10000 后取整再除以 10000，保证是截断而非四舍五入。
一个容易踩的坑：微弱回响中的 和
要按咒语原始单词数计算（含重复），而不是去重后的数量。比如咒语是 "A A B"，A 在卷轴中而 B 不在，那么
，
。
代码
[sol-C++]
#include <bits/stdc++.h>
using namespace std;
string normalize(const string& s) {
string res;
for (char c : s) {
if (isalnum(c)) res += tolower(c);
}
return res;
}
vector<string> splitWords(const string& s) {
vector<string> words;
istringstream iss(s);
string w;
while (iss >> w) {
string nw = normalize(w);
if (!nw.empty()) words.push_back(nw);
}
return words;
}
int main() {
string line;
getline(cin, line);
vector<string> parts;
{
size_t pos = 0;
while (true) {
size_t p = line.find('|', pos);
if (p == string::npos) {
parts.push_back(line.substr(pos));
break;
}
parts.push_back(line.substr(pos, p - pos));
pos = p + 1;
}
}
vector<string> scrollWords = splitWords(parts[0]);
int L = scrollWords.size();
unordered_map<string, int> posMap;
unordered_set<string> scrollSet;
for (int i = 0; i < L; i++) {
scrollSet.insert(scrollWords[i]);
if (posMap.find(scrollWords[i]) == posMap.end()) {
posMap[scrollWords[i]] = i;
}
}
for (int idx = 1; idx < (int)parts.size(); idx++) {
if (idx > 1) cout << "|";
vector<string> incWords = splitWords(parts[idx]);
int k = incWords.size();
if (k == 0) {
cout << "0.0000";
continue;
}
vector<string> incUnique;
unordered_set<string> seen;
for (auto& w : incWords) {
if (seen.find(w) == seen.end()) {
seen.insert(w);
incUnique.push_back(w);
}
}
vector<string> found;
for (auto& w : incUnique) {
if (scrollSet.count(w)) found.push_back(w);
}
bool allFound = (found.size() == incUnique.size());
bool noneFound = found.empty();
double matchScore;
if (noneFound) {
matchScore = 0.0;
} else if (allFound) {
int j = 0;
for (int i = 0; i < L && j < k; i++) {
if (scrollWords[i] == incWords[j]) j++;
}
matchScore = (j == k) ? 1.0 : 0.8;
} else {
int iCount = 0;
for (auto& w : incWords) {
if (scrollSet.count(w)) iCount++;
}
matchScore = 0.6 * (double)iCount / (double)k;
}
double totalPE = 0.0;
for (auto& w : found) {
int p = posMap[w];
if (L == 1) {
totalPE += 1.0;
} else {
totalPE += 1.0 - (double)p / (L - 1);
}
}
double raw = matchScore * totalPE;
long long truncated = (long long)(raw * 10000);
double final_score = truncated / 10000.0;
cout << fixed << setprecision(4) << final_score;
}
cout << endl;
return 0;
}
[sol-Java]
import java.util.*;
public class Main {
static String normalize(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) sb.append(Character.toLowerCase(c));
}
return sb.toString();
}
static List<String> splitWords(String s) {
List<String> words = new ArrayList<>();
for (String w : s.split("\\s+")) {
String nw = normalize(w);
if (!nw.isEmpty()) words.add(nw);
}
return words;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
String[] parts = line.split("\\|", -1);
List<String> scrollWords = splitWords(parts[0]);
int L = scrollWords.size();
Map<String, Integer> posMap = new HashMap<>();
Set<String> scrollSet = new HashSet<>();
for (int i = 0; i < L; i++) {
scrollSet.add(scrollWords.get(i));
if (!posMap.containsKey(scrollWords.get(i))) {
posMap.put(scrollWords.get(i), i);
}
}
StringBuilder result = new StringBuilder();
for (int idx = 1; idx < parts.length; idx++) {
if (idx > 1) result.append("|");
List<String> incWords = splitWords(parts[idx]);
int k = incWords.size();
if (k == 0) {
result.append("0.0000");
continue;
}
List<String> incUnique = new ArrayList<>();
Set<String> seen = new LinkedHashSet<>();
for (String w : incWords) {
if (seen.add(w)) incUnique.add(w);
}
List<String> found = new ArrayList<>();
for (String w : incUnique) {
if (scrollSet.contains(w)) found.add(w);
}
boolean allFound = found.size() == incUnique.size();
boolean noneFound = found.isEmpty();
double matchScore;
if (noneFound) {
matchScore = 0.0;
} else if (allFound) {
int j = 0;
for (int i = 0; i < L && j < k; i++) {
if (scrollWords.get(i).equals(incWords.get(j))) j++;
}
matchScore = (j == k) ? 1.0 : 0.8;
} else {
int iCount = 0;
for (String w : incWords) {
if (scrollSet.contains(w)) iCount++;
}
matchScore = 0.6 * (double) iCount / (double) k;
}
double totalPE = 0.0;
for (String w : found) {
int p = posMap.get(w);
if (L == 1) {
totalPE += 1.0;
} else {
totalPE += 1.0 - (double) p / (L - 1);
}
}
double raw = matchScore * totalPE;
long truncated = (long) (raw * 10000);
double finalScore = truncated / 10000.0;
result.append(String.format("%.4f", finalScore));
}
System.out.println(result.toString());
}
}
[sol-Python3]
import sys, re, math
def normalize(word):
return re.sub(r'[^a-zA-Z0-9]', '', word).lower()
def solve():
line = input().strip()
parts = line.split('|')
scroll_text = parts[0]
incantations = parts[1:]
scroll_words = [normalize(w) for w in scroll_text.split() if normalize(w)]
L = len(scroll_words)
pos_map = {}
scroll_set = set()
for i, w in enumerate(scroll_words):
scroll_set.add(w)
if w not in pos_map:
pos_map[w] = i
results = []
for inc in incantations:
inc_words = [normalize(w) for w in inc.split() if normalize(w)]
k = len(inc_words)
if k == 0:
results.append("0.0000")
continue
inc_unique = list(dict.fromkeys(inc_words))
found = [w for w in inc_unique if w in scroll_set]
all_found = len(found) == len(inc_unique)
none_found = len(found) == 0
if none_found:
match_score = 0.0
elif all_found:
j = 0
for sw in scroll_words:
if j < k and sw == inc_words[j]:
j += 1
match_score = 1.0 if j == k else 0.8
else:
i_count = sum(1 for w in inc_words if w in scroll_set)
match_score = 0.6 * i_count / k
total_pe = 0.0
for w in found:
p = pos_map[w]
if L == 1:
total_pe += 1.0
else:
total_pe += 1.0 - p / (L - 1)
raw = match_score * total_pe
final = math.floor(raw * 10000) / 10000
results.append(f"{final:.4f}")
print('|'.join(results))
solve()
[sol-JavaScript]
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
const parts = line.split('|');
const scrollText = parts[0];
const incantations = parts.slice(1);
function normalize(word) {
return word.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
}
function splitWords(s) {
return s.split(/\s+/).map(normalize).filter(w => w.length > 0);
}
const scrollWords = splitWords(scrollText);
const L = scrollWords.length;
const posMap = {};
const scrollSet = new Set();
for (let i = 0; i < L; i++) {
scrollSet.add(scrollWords[i]);
if (!(scrollWords[i] in posMap)) {
posMap[scrollWords[i]] = i;
}
}
const results = [];
for (const inc of incantations) {
const incWords = splitWords(inc);
const k = incWords.length;
if (k === 0) {
results.push("0.0000");
continue;
}
const incUnique = [];
const seen = new Set();
for (const w of incWords) {
if (!seen.has(w)) {
seen.add(w);
incUnique.push(w);
}
}
const found = incUnique.filter(w => scrollSet.has(w));
const allFound = found.length === incUnique.length;
const noneFound = found.length === 0;
let matchScore;
if (noneFound) {
matchScore = 0.0;
} else if (allFound) {
let j = 0;
for (let i = 0; i < L && j < k; i++) {
if (scrollWords[i] === incWords[j]) j++;
}
matchScore = (j === k) ? 1.0 : 0.8;
} else {
let iCount = 0;
for (const w of incWords) {
if (scrollSet.has(w)) iCount++;
}
matchScore = 0.6 * iCount / k;
}
let totalPE = 0.0;
for (const w of found) {
const p = posMap[w];
if (L === 1) {
totalPE += 1.0;
} else {
totalPE += 1.0 - p / (L - 1);
}
}
const raw = matchScore * totalPE;
const truncated = Math.floor(raw * 10000);
const finalScore = truncated / 10000;
results.push(finalScore.toFixed(4));
}
console.log(results.join('|'));
});
复杂度分析
设卷轴文本长度为 ，咒语总数为
，每条咒语平均长度为
。
- 时间复杂度：
。每条咒语需要
做去重和集合查找，子序列检查最坏
，位置能量求和
- 空间复杂度：
京公网安备 11010502036488号