解题思路

• 整体流程

  1. 将广告标题与每个关键词短语统一转成小写，并按规则分词：只保留字母、数字与连字符-，其它符号替换为空格后再按空格切分。

  2. 预处理标题：长度为 n 的标题，其位置权重为线性衰减：

     • n==1 时权重为 [1.0]；
     • 否则第 i 个单词（0-based）的权重 w[i] = 1 - i/(n-1)。 同时记录每个单词首次出现的位置（若标题中有重复词，按规则只取第一次）。

  3. 对每个关键词短语，设其词序列为 q，长度为 k，与标题匹配得到：

     • 有序子序列：q 在标题中按顺序出现（可不连续）→ 匹配分 X1=1.0
     • 无序包含：q 的所有词都在标题中但顺序不一致 → 匹配分 X2=0.8
     • 部分匹配：仅有 i 个词在标题中 → 匹配分 X3 * (i/k)，其中 X3=0.6
     • 其余：X4=0.0 （匹配忽略大小写）

  4. 位置权重求和：将 q 中出现在标题里的每个词，取其在标题中第一次出现的权重并求和。

  5. 最终相关性分数：score = 匹配分 * 位置权重和。按四舍五入保留 4 位小数。

• 涉及算法

  • 字符串预处理与分词（正则/字符过滤）
  • 有序子序列判定（双指针扫描标题一次）
  • 线性函数计算位置权重并哈希表记录首次出现位置

复杂度分析

• 设标题长度为 n，关键词短语个数为 m，第 j 个短语长度为 k_j。
• 预处理标题：O(n)；每个短语：有序判定 O(n)，其余统计 O(k_j)。
• 总时间复杂度 O(n + m·n + Σk_j)，题目数据（m<100）下完全可行。
• 额外空间：权重数组与哈希表 O(n)。

代码实现

Python

# -*- coding: utf-8 -*-
# 题面功能写在外部函数，主函数只做输入输出

import sys
import re
from decimal import Decimal, ROUND_HALF_UP

# 分词：仅保留字母/数字/连字符-，其余替换为空格
def tokenize(s: str):
    s = s.lower()
    s = re.sub(r'[^a-z0-9\-]+', ' ', s)
    return [w for w in s.split() if w]

# 计算单个关键词短语的得分
def calc_one_score(title_tokens, weights, first_pos, query: str) -> str:
    q = tokenize(query)
    n = len(title_tokens)
    # 位置权重求和（仅对出现过的词求和，且取首次出现位置）
    pos_sum = 0.0
    for w in q:
        if w in first_pos:
            pos_sum += weights[first_pos[w]]

    # 有序子序列判定（双指针）
    ordered = False
    if len(q) > 0:
        i = 0
        for t in title_tokens:
            if i < len(q) and q[i] == t:
                i += 1
        ordered = (i == len(q))

    # 统计包含情况
    all_present = len(q) > 0 and all(w in first_pos for w in q)
    match_cnt = sum(1 for w in q if w in first_pos)

    # 匹配分
    X1, X2, X3, X4 = 1.0, 0.8, 0.6, 0.0
    if len(q) == 0:
        base = 0.0
    elif ordered and all_present:
        base = X1
    elif all_present:
        base = X2
    elif match_cnt > 0:
        base = X3 * (match_cnt / len(q))
    else:
        base = X4

    val = base * pos_sum
    # 四舍五入保留4位小数
    res = Decimal(val).quantize(Decimal('0.0001'), rounding=ROUND_HALF_UP)
    return f"{res:.4f}"

# 计算整行输入的所有得分
def solve(line: str) -> str:
    parts = line.strip().split('|')
    title = parts[0]
    queries = parts[1:]

    title_tokens = tokenize(title)
    n = len(title_tokens)
    if n == 0:
        return '|'.join(['0.0000' for _ in queries])

    # 位置权重
    if n == 1:
        weights = [1.0]
    else:
        weights = [1.0 - i / (n - 1) for i in range(n)]

    # 每个词的首次出现位置
    first_pos = {}
    for i, w in enumerate(title_tokens):
        if w not in first_pos:
            first_pos[w] = i

    # 逐个短语计算分数
    scores = [calc_one_score(title_tokens, weights, first_pos, q) for q in queries]
    return '|'.join(scores)

if __name__ == "__main__":
    line = sys.stdin.readline().rstrip('\n')
    print(solve(line))

Java

// 题面功能写在外部函数，主函数只做输入输出
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class Main {

    // 分词：仅保留字母/数字/连字符-，其它替换为空格
    static List<String> tokenize(String s) {
        s = s.toLowerCase().replaceAll("[^a-z0-9\\-]+", " ");
        String[] arr = s.trim().isEmpty() ? new String[0] : s.trim().split("\\s+");
        return Arrays.asList(arr);
    }

    // 四舍五入到4位小数并输出字符串（保留末尾0）
    static String format4(double v) {
        BigDecimal bd = new BigDecimal(v);
        bd = bd.setScale(4, RoundingMode.HALF_UP);
        return bd.toPlainString();
    }

    // 计算单个关键词短语的得分
    static String calcOneScore(List<String> titleTokens, double[] weights,
                               Map<String, Integer> firstPos, String query) {
        List<String> q = tokenize(query);

        // 位置权重求和
        double posSum = 0.0;
        for (String w : q) {
            Integer idx = firstPos.get(w);
            if (idx != null) posSum += weights[idx];
        }

        // 有序子序列判定（双指针）
        boolean ordered = false;
        if (!q.isEmpty()) {
            int i = 0;
            for (String t : titleTokens) {
                if (i < q.size() && q.get(i).equals(t)) i++;
            }
            ordered = (i == q.size());
        }

        // 包含情况
        boolean allPresent = !q.isEmpty();
        int matchCnt = 0;
        for (String w : q) {
            if (firstPos.containsKey(w)) matchCnt++;
            else allPresent = false;
        }

        // 匹配分
        double X1 = 1.0, X2 = 0.8, X3 = 0.6, X4 = 0.0;
        double base;
        if (q.isEmpty()) base = 0.0;
        else if (ordered && allPresent) base = X1;
        else if (allPresent) base = X2;
        else if (matchCnt > 0) base = X3 * ((double) matchCnt / q.size());
        else base = X4;

        double val = base * posSum;
        return format4(val);
    }

    static String solve(String line) {
        String[] parts = line.split("\\|", -1); // 保留空段
        String title = parts[0];
        List<String> queries = new ArrayList<>();
        for (int i = 1; i < parts.length; i++) queries.add(parts[i]);

        List<String> titleTokens = tokenize(title);
        int n = titleTokens.size();
        if (n == 0) {
            String[] zero = new String[queries.size()];
            Arrays.fill(zero, "0.0000");
            return String.join("|", zero);
        }

        // 位置权重
        double[] weights = new double[n];
        if (n == 1) weights[0] = 1.0;
        else {
            for (int i = 0; i < n; i++) weights[i] = 1.0 - (double) i / (n - 1);
        }

        // 首次出现位置
        Map<String, Integer> firstPos = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String w = titleTokens.get(i);
            if (!firstPos.containsKey(w)) firstPos.put(w, i);
        }

        // 逐个短语计算
        List<String> res = new ArrayList<>();
        for (String q : queries) res.add(calcOneScore(titleTokens, weights, firstPos, q));
        return String.join("|", res);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        System.out.println(solve(line));
    }
}

C++

// 题面功能写在外部函数，主函数只做输入输出
#include <bits/stdc++.h>
using namespace std;

// 分词：仅保留字母/数字/连字符-，其余替换为空格
vector<string> tokenize(const string& s0) {
    string s = s0;
    vector<string> res;
    for (char& c : s) {
        char x = tolower((unsigned char)c);
        if ((x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') || x == '-') c = x;
        else c = ' ';
    }
    string tmp;
    stringstream ss(s);
    while (ss >> tmp) res.push_back(tmp);
    return res;
}

// 四舍五入到4位小数
double round4(double x) {
    return floor(x * 10000.0 + 0.5) / 10000.0;
}

// 计算单个关键词短语的得分
string calcOneScore(const vector<string>& titleTokens, const vector<double>& weights,
                    const unordered_map<string,int>& firstPos, const string& query) {
    vector<string> q = tokenize(query);

    // 位置权重求和
    double posSum = 0.0;
    for (const string& w : q) {
        auto it = firstPos.find(w);
        if (it != firstPos.end()) posSum += weights[it->second];
    }

    // 有序子序列判定
    bool ordered = false;
    if (!q.empty()) {
        size_t i = 0;
        for (const string& t : titleTokens) {
            if (i < q.size() && q[i] == t) ++i;
        }
        ordered = (i == q.size());
    }

    // 包含统计
    bool allPresent = !q.empty();
    int matchCnt = 0;
    for (const string& w : q) {
        if (firstPos.count(w)) ++matchCnt;
        else allPresent = false;
    }

    // 匹配分
    const double X1 = 1.0, X2 = 0.8, X3 = 0.6, X4 = 0.0;
    double base;
    if (q.empty()) base = 0.0;
    else if (ordered && allPresent) base = X1;
    else if (allPresent) base = X2;
    else if (matchCnt > 0) base = X3 * ( (double)matchCnt / (double)q.size() );
    else base = X4;

    double val = base * posSum;
    double v = round4(val);

    // 固定4位小数输出
    ostringstream oss;
    oss.setf(std::ios::fixed);
    oss << setprecision(4) << v;
    return oss.str();
}

string solve(const string& line) {
    // 按 | 分割（保留空段）
    vector<string> parts;
    string cur;
    for (size_t i = 0; i <= line.size(); ++i) {
        if (i == line.size() || line[i] == '|') {
            parts.push_back(cur);
            cur.clear();
        } else cur.push_back(line[i]);
    }

    string title = parts[0];
    vector<string> queries(parts.begin() + 1, parts.end());

    vector<string> titleTokens = tokenize(title);
    int n = (int)titleTokens.size();
    if (n == 0) {
        string out;
        for (size_t i = 0; i < queries.size(); ++i) {
            if (i) out += "|";
            out += "0.0000";
        }
        return out;
    }

    // 位置权重
    vector<double> weights(n, 1.0);
    if (n > 1) {
        for (int i = 0; i < n; ++i) weights[i] = 1.0 - (double)i / (double)(n - 1);
    }

    // 首次出现位置
    unordered_map<string,int> firstPos;
    for (int i = 0; i < n; ++i) if (!firstPos.count(titleTokens[i])) firstPos[titleTokens[i]] = i;

    // 逐个短语计算
    string out;
    for (size_t i = 0; i < queries.size(); ++i) {
        if (i) out += "|";
        out += calcOneScore(titleTokens, weights, firstPos, queries[i]);
    }
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    getline(cin, line);
    cout << solve(line) << "\n";
    return 0;
}

题目内容

在搜索广告系统中，广告商希望他们的广告能够精准地展示给搜索相关关键词的用户。为了提高广告的相关性，系统需要计算广告与搜索关键词之间的相关性得分。一个关键的相关性指标与keywords在广告标题是否出现及出现的位置权重有关。出现在越靠近标题开头的关键词权重越高。

相关性得分计算规则:

1、计算匹配度分，如下是根据广告标题中关键词出现方式来计算匹配度分。规则如下:

1)有序子序列:对于搜索关键词 "$red$ $shoes$"和广告标题 “$buy$ $red$ $running$ $shoes$ $online$"，关键词 "$red$"和“$shoes$" 在广告标题中形成了一个有序的子序列"$red$ $shoes$"，匹配度得分为 $X1$;

2)无序子序列:对于搜索关键词"$shoes$ $red$"和广告标题"$buy$ $redrunning$ $shoes$ $online$"，广告标题包括所有的 $red$ 和 $shoes$ 两个关键词，匹配度得分为 $X2$ ;.

3)匹配关键词占比权重: $k$ 表示搜索关键词单词个数，$i$ 表示搜索关键词中与广告标题中单词匹配个数，对于搜索关键词"$shoes$ $red$ $or$ $black$" 和广告标题"$buy$ $red$ $running$ $shoes$ $online$"，搜索关键词的 $k=4$ ，其中 $shoes$ 和 $red$ 匹配广告标题中的 $red$ 和 $shoes，i=2$，匹配度得分为 $X3*i/k$。

4)除上述场景外，其他情况匹配度为 $X4$ 分。

其中根据业务实际相关性标准，$Xi$ 系数 $∈[1.0,0.8.0.6,0]$

2、计算位置权重

1)本题位置权重根据广告标题长度按线性袁减函数计算，如长度为 $5$ 的广告标题，位置权重为 $[1.0,0.75,0.5,0.25,0]$ ; 即: $sum(weight= 1.0-(pos/(ads\_tiltle\_length -1)))pos$ 代表单个关键词位置，从索引 $0$ 开始

2)若存在多个关键词，位置权重取求和

3)广告标题存在多个相同关键词，取第一个关键词索引权重

3、计算相关性分数

相关性分数 $=$ 匹配分 $*$ 位置权重，保留 $4$ 位小数，向下取整。

函数需要返回每个搜索关键词与广告之间的相关性得分(浮点数列表，保留 $4$ 位小数，向下取整)，相关性得分根据关键词在标题匹配度及其位置权重计算得出。(说明:匹配时忽略大小写)

输入描述

输入:现在有广告标题和检索的关键词列表输入格式:$ad\_title丨keywords1丨keywords2丨keywords3丨keywordsN$

描述:以”$丨$"分割，首位为广告标题，其余为关键词列表，测试样例中均为英文单词或字符组成。输入的关键词个数小于 $100$

输出描述

每个关键词对应的相关行得分(得分个数等于关键词个数，即也小于 $100$;保留 $4$ 位小数，向下取整)，中间用 $丨$ 分隔。比如 $1.0000丨1.4000丨0.0750丨0.0000$

样例1

输入

Advanced Camera: Capture Life in Stunning Detail! Elevate Your Photography with Our Cutting-Edge Camera!|Camera|Camera Photography|digital phone|phone

输出

0.9231|1.2308丨0.0000丨0.0000

样例2

输入

buy red running shoes online!|red shoes|buy shoes running|shoes black|Phone

输出

1.0000|1.4000|0.0750|0.0000