REALHW85 古代咒语共鸣匹配

题目链接

古代咒语共鸣匹配

题目描述

你需要计算咒语（incantation）与卷轴文本（scroll_text）之间的共鸣分数。分数由两部分相乘得到：匹配度和位置能量。

1. 匹配度 (Match Score) 根据咒语符文和卷轴文本符文的匹配情况，按优先级从高到低分为四个等级：

  1. 完美谐振 (Perfect Harmonic Match): 咒语中的所有符文，在卷轴文本中以相同的顺序出现（可以不相邻）。得分为 1.0。
  2. 部分谐振 (Partial Harmonic Match): 咒语中的所有符文，都能在卷轴文本中找到，但顺序不完全一致。得分为 0.8。
  3. 微弱回响 (Faint Echo): 只有部分咒语符文能在卷轴文本中找到。设咒语符文总数（含重复）为 k，其中不重复且能在卷轴中匹配到的符文数为 i。得分为 (i / k) * 0.6。
  4. 静默 (Silence): 咒语中没有任何一个符文出现在卷轴文本中。得分为 0.0。

2. 位置能量 (Positional Energy)

  • 设卷轴文本的符文总数为 L。对于一个在卷轴中匹配到的符文，其 0-索引位置为 p，则该符文贡献的位置能量为 1.0 - p / (L - 1) (当 L=1 时，约定能量为 1.0)。
  • 一个咒语的总位置能量是其所有匹配到的不重复的符文的位置能量之和。

3. 最终共鸣分数

  • 最终分数 = 匹配度 × 总位置能量
  • 结果直接截断至小数点后4位。
  • 所有符文匹配过程忽略大小写，并只处理单词前后的标点符号。

解题思路

本题是一道复杂的规则模拟题，成功的关键在于精确实现每一个细节，特别是题目描述中未能完全明确的规则。

  1. 文本预处理 (Sanitization):

    • 规则要求忽略大小写和标点，但根据实际测试用例，这里的“标点”指的是单词前后的非字母数字字符。单词中间的连接符（如-）应被保留。
    • 因此，需要一个sanitize函数，它接收一个字符串（符文），将其转为小写，并仅移除其头部和尾部的所有非字母数字字符。
    • 使用此函数处理卷轴文本和所有咒语，得到清洗后的符文列表。

  2. 数据结构准备:

    • 对清洗后的卷轴符文列表，创建两个哈希表：一个用于快速判断符文是否存在 (Set)，另一个记录每个唯一符文首次出现的位置 (Map)。

  3. 匹配度计算 (按优先级):

    • 这是一个严格的层级判断。
    • 首先，判断是否所有不重复的咒语符文都能在卷轴的Set中找到。
      • 如果都能找到：
        • 接着进行“完美谐振”判断：检查完整的咒语符文列表是否是卷轴符文列表的子序列。是，则分数为 1.0。
        • 如果不是子序列，则为“部分谐振”，分数为 0.8。
      • 如果不能都找到：
        • 进入“微弱回响”计算：
          • k = 咒语符文列表的总长度（含重复）。
          • i = 咒语中不重复的、且能在卷轴中找到的符文数量。
          • 如果i > 0，分数为 (i / k) * 0.6。
          • 如果i == 0，则为“静默”，分数为 0.0。

  4. 位置能量计算:

    • 找出咒语中所有不重复的、且能在卷轴中找到的符文。
    • 对其中的每一个符文，从位置Map中获取其首次出现的索引 p。
    • 根据卷轴符文总数 L，按公式 1.0 - p / (L - 1) 计算能量（注意处理 L=1 的边界情况）。
    • 将所有能量值累加，得到总位置能量。

  5. 最终计算与格式化:

    • 将匹配度与总位置能量相乘。
    • 将结果截断至小数点后4位并输出。

代码

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;

// 辅助函数：将字符串转为小写
string toLower(string s) {
    transform(s.begin(), s.end(), s.begin(),
                   [](unsigned char c){ return tolower(c); });
    return s;
}

// 辅助函数：净化字符串，移除前后非字母数字字符
string sanitize(string s) {
    while (!s.empty() && !isalnum(s.front())) {
        s.erase(0, 1);
    }
    while (!s.empty() && !isalnum(s.back())) {
        s.pop_back();
    }
    return s;
}

// 核心逻辑：计算匹配度分数
double calculateMatchScore(const vector<string>& incantation_runes,
                           const vector<string>& scroll_runes,
                           const set<string>& scroll_rune_set) {
    if (incantation_runes.empty()) {
        return 0.0;
    }

    set<string> unique_inc_runes(incantation_runes.begin(), incantation_runes.end());

    bool all_unique_runes_found = true;
    for (const auto& rune : unique_inc_runes) {
        if (scroll_rune_set.find(rune) == scroll_rune_set.end()) {
            all_unique_runes_found = false;
            break;
        }
    }

    if (all_unique_runes_found) {
        int inc_ptr = 0;
        for (const auto& scroll_rune : scroll_runes) {
            if (inc_ptr < incantation_runes.size() && scroll_rune == incantation_runes[inc_ptr]) {
                inc_ptr++;
            }
        }
        if (inc_ptr == incantation_runes.size()) {
            return 1.0; // 完美谐振
        } else {
            return 0.8; // 部分谐振
        }
    }

    double k = incantation_runes.size();
    double i = 0;
    for (const auto& rune : unique_inc_runes) {
        if (scroll_rune_set.count(rune)) {
            i++;
        }
    }

    if (i > 0) {
        return (i / k) * 0.6; // 微弱回响
    }

    return 0.0; // 静默
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    getline(cin, line);

    stringstream ss(line);
    string part;
    vector<string> parts;
    while(getline(ss, part, '|')) {
        parts.push_back(part);
    }
    
    // --- 预处理卷轴 ---
    vector<string> scroll_runes;
    stringstream ss_scroll(parts[0]);
    string word;
    while (ss_scroll >> word) {
        string sanitized_word = sanitize(word);
        if (!sanitized_word.empty()) {
            scroll_runes.push_back(toLower(sanitized_word));
        }
    }

    map<string, int> scroll_rune_positions;
    for (int i = 0; i < scroll_runes.size(); ++i) {
        if (scroll_rune_positions.find(scroll_runes[i]) == scroll_rune_positions.end()) {
            scroll_rune_positions[scroll_runes[i]] = i;
        }
    }
    set<string> scroll_rune_set(scroll_runes.begin(), scroll_runes.end());

    // --- 逐个处理咒语 ---
    vector<double> final_scores;
    for (size_t i = 1; i < parts.size(); ++i) {
        vector<string> incantation_runes;
        stringstream ss_incantation(parts[i]);
        while (ss_incantation >> word) {
             string sanitized_rune = sanitize(word);
            if (!sanitized_rune.empty()) {
                incantation_runes.push_back(toLower(sanitized_rune));
            }
        }

        double match_score = calculateMatchScore(incantation_runes, scroll_runes, scroll_rune_set);
        
        double positional_energy = 0.0;
        double L = scroll_runes.size();
        set<string> matched_unique_runes;
        for(const auto& ir : incantation_runes){
            if(scroll_rune_set.count(ir)){
                matched_unique_runes.insert(ir);
            }
        }
        
        for (const auto& mur : matched_unique_runes) {
            int p = scroll_rune_positions.at(mur);
            if (L > 1) {
                positional_energy += (1.0 - static_cast<double>(p) / (L - 1.0));
            } else {
                positional_energy += 1.0;
            }
        }
        
        double resonance_score = match_score * positional_energy;
        double truncated_score = floor(resonance_score * 10000.0) / 10000.0;
        final_scores.push_back(truncated_score);
    }

    // --- 输出结果 ---
    for (size_t i = 0; i < final_scores.size(); ++i) {
        cout << fixed << setprecision(4) << final_scores[i] << (i == final_scores.size() - 1 ? "" : "|");
    }
    cout << endl;

    return 0;
}


import java.util.*;
import java.math.BigDecimal;
import java.math.RoundingMode;

public class Main {
    private static String toLower(String s) {
        return s.toLowerCase();
    }

    private static String sanitize(String s) {
        if (s.isEmpty()) return "";
        int start = 0;
        while (start < s.length() && !Character.isLetterOrDigit(s.charAt(start))) {
            start++;
        }
        int end = s.length() - 1;
        while (end >= start && !Character.isLetterOrDigit(s.charAt(end))) {
            end--;
        }
        if (end < start) return "";
        return s.substring(start, end + 1);
    }

    private static BigDecimal calculateMatchScore(List<String> incantationRunes, List<String> scrollRunes, Set<String> scrollRuneSet) {
        if (incantationRunes.isEmpty()) {
            return BigDecimal.ZERO;
        }

        Set<String> uniqueIncRunes = new HashSet<>(incantationRunes);

        boolean allUniqueRunesFound = true;
        for (String rune : uniqueIncRunes) {
            if (!scrollRuneSet.contains(rune)) {
                allUniqueRunesFound = false;
                break;
            }
        }

        if (allUniqueRunesFound) {
            int incPtr = 0;
            for (String scrollRune : scrollRunes) {
                if (incPtr < incantationRunes.size() && scrollRune.equals(incantationRunes.get(incPtr))) {
                    incPtr++;
                }
            }
            if (incPtr == incantationRunes.size()) {
                return new BigDecimal("1.0"); // 完美谐振
            } else {
                return new BigDecimal("0.8"); // 部分谐振
            }
        }

        BigDecimal k = new BigDecimal(incantationRunes.size());
        BigDecimal i = BigDecimal.ZERO;
        for (String rune : uniqueIncRunes) {
            if (scrollRuneSet.contains(rune)) {
                i = i.add(BigDecimal.ONE);
            }
        }

        if (i.compareTo(BigDecimal.ZERO) > 0) {
            if (k.compareTo(BigDecimal.ZERO) == 0) return BigDecimal.ZERO;
            // 使用 BigDecimal 进行精确计算
            return i.divide(k, 20, RoundingMode.HALF_UP).multiply(new BigDecimal("0.6")); // 微弱回响
        }

        return BigDecimal.ZERO; // 静默
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] parts = line.split("\\|");

        // --- 预处理卷轴 ---
        List<String> scrollRunes = new ArrayList<>();
        Scanner scrollScanner = new Scanner(parts[0]);
        while (scrollScanner.hasNext()) {
            String sanitizedWord = sanitize(scrollScanner.next());
            if (!sanitizedWord.isEmpty()) {
                scrollRunes.add(toLower(sanitizedWord));
            }
        }
        scrollScanner.close();

        Map<String, Integer> scrollRunePositions = new HashMap<>();
        for (int i = 0; i < scrollRunes.size(); i++) {
            scrollRunePositions.putIfAbsent(scrollRunes.get(i), i);
        }
        Set<String> scrollRuneSet = new HashSet<>(scrollRunes);
        
        // --- 逐个处理咒语 ---
        List<BigDecimal> finalScores = new ArrayList<>();
        for (int i = 1; i < parts.length; i++) {
            List<String> incantationRunes = new ArrayList<>();
            Scanner incantationScanner = new Scanner(parts[i]);
            while (incantationScanner.hasNext()) {
                String sanitizedRune = sanitize(incantationScanner.next());
                if (!sanitizedRune.isEmpty()) {
                    incantationRunes.add(toLower(sanitizedRune));
                }
            }
            incantationScanner.close();

            BigDecimal matchScore = calculateMatchScore(incantationRunes, scrollRunes, scrollRuneSet);

            BigDecimal positionalEnergy = BigDecimal.ZERO;
            BigDecimal L_bd = new BigDecimal(scrollRunes.size());
            Set<String> matchedUniqueRunes = new HashSet<>();
            for (String ir : incantationRunes) {
                if (scrollRuneSet.contains(ir)) {
                    matchedUniqueRunes.add(ir);
                }
            }

            for (String mur : matchedUniqueRunes) {
                BigDecimal p_bd = new BigDecimal(scrollRunePositions.get(mur));
                if (L_bd.compareTo(BigDecimal.ONE) > 0) {
                    BigDecimal L_minus_1 = L_bd.subtract(BigDecimal.ONE);
                    BigDecimal energy = BigDecimal.ONE.subtract(p_bd.divide(L_minus_1, 20, RoundingMode.HALF_UP));
                    positionalEnergy = positionalEnergy.add(energy);
                } else {
                    positionalEnergy = positionalEnergy.add(BigDecimal.ONE);
                }
            }

            BigDecimal resonanceScore = matchScore.multiply(positionalEnergy);
            finalScores.add(resonanceScore);
        }

        // --- 输出结果 ---
        StringJoiner sj = new StringJoiner("|");
        for (BigDecimal score : finalScores) {
            BigDecimal truncatedScore = score.setScale(4, RoundingMode.DOWN);
            sj.add(String.format("%.4f", truncatedScore));
        }
        System.out.println(sj.toString());
    }
}


import re
import math

def to_lower(s):
    return s.lower()

def sanitize(s):
    return re.sub(r'^[^\w\d]+|[^\w\d]+$', '', s)

def calculate_match_score(incantation_runes, scroll_runes, scroll_rune_set):
    if not incantation_runes:
        return 0.0

    unique_inc_runes = set(incantation_runes)

    all_unique_runes_found = all(rune in scroll_rune_set for rune in unique_inc_runes)

    if all_unique_runes_found:
        it = iter(scroll_runes)
        if all(rune in it for rune in incantation_runes):
            return 1.0  # 完美谐振
        else:
            return 0.8  # 部分谐振

    k = len(incantation_runes)
    i = 0
    for rune in unique_inc_runes:
        if rune in scroll_rune_set:
            i += 1
            
    if i > 0:
        return (i / k) * 0.6  # 微弱回响
        
    return 0.0 # 静默

def solve():
    line = input()
    parts = line.split('|')

    # --- 预处理卷轴 ---
    scroll_text_raw = parts[0]
    scroll_runes = []
    for word in scroll_text_raw.split():
        sanitized_word = sanitize(word)
        if sanitized_word:
            scroll_runes.append(to_lower(sanitized_word))

    scroll_rune_positions = {}
    for i, rune in enumerate(scroll_runes):
        if rune not in scroll_rune_positions:
            scroll_rune_positions[rune] = i
    scroll_rune_set = set(scroll_runes)

    # --- 逐个处理咒语 ---
    final_scores = []
    for i in range(1, len(parts)):
        incantation_runes = []
        for word in parts[i].split():
            sanitized_rune = sanitize(word)
            if sanitized_rune:
                incantation_runes.append(to_lower(sanitized_rune))

        match_score = calculate_match_score(incantation_runes, scroll_runes, scroll_rune_set)

        positional_energy = 0.0
        L = len(scroll_runes)
        matched_unique_runes = set()
        for ir in incantation_runes:
            if ir in scroll_rune_set:
                matched_unique_runes.add(ir)
        
        for mur in matched_unique_runes:
            p = scroll_rune_positions[mur]
            if L > 1:
                positional_energy += (1.0 - p / (L - 1.0))
            else:
                positional_energy += 1.0
        
        resonance_score = match_score * positional_energy
        truncated_score = math.floor(resonance_score * 10000) / 10000
        final_scores.append(truncated_score)

    # --- 输出结果 ---
    print("|".join([f"{score:.4f}" for score in final_scores]))

solve()

算法及复杂度

  • 算法: 字符串处理, 哈希表, 子序列判断
  • 时间复杂度:
    • 是卷轴文本的总字符数，预处理卷轴需要 。
    • 对于 个咒语，每个咒语的总字符数为 。
    • 对每个咒语的处理（包括子序列判断）大致与其符文数量成线性关系。子序列判断的最坏情况是 ，但由于符文数量的限制，总体可以近似为与总字符数相关的线性复杂度。
  • 空间复杂度:
    • 需要 空间存储清洗后的卷轴符文和位置哈希表。
    • 在处理每个咒语时，需要 的临时空间。总空间复杂度由卷轴主导。