#P4444. 第2题-搜索广告相关性分数
-
1000ms
Tried: 109
Accepted: 17
Difficulty: 7
所属公司 :
华为
时间 :2025年11月5日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>模拟字符串
第2题-搜索广告相关性分数
解题思路
-
整体流程
-
将广告标题与每个关键词短语统一转成小写,并按规则分词:只保留字母、数字与连字符
-,其它符号替换为空格后再按空格切分。 -
预处理标题:长度为
n的标题,其位置权重为线性衰减:n==1时权重为[1.0];- 否则第
i个单词(0-based)的权重w[i] = 1 - i/(n-1)。 同时记录每个单词首次出现的位置(若标题中有重复词,按规则只取第一次)。
-
对每个关键词短语,设其词序列为
q,长度为k,与标题匹配得到:- 有序子序列:
q在标题中按顺序出现(可不连续)→ 匹配分X1=1.0 - 无序包含:
q的所有词都在标题中但顺序不一致 → 匹配分X2=0.8 - 部分匹配:仅有
i个词在标题中 → 匹配分X3 * (i/k),其中X3=0.6 - 其余:
X4=0.0(匹配忽略大小写)
- 有序子序列:
-
位置权重求和:将
q中出现在标题里的每个词,取其在标题中第一次出现的权重并求和。 -
最终相关性分数:
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