当前位置：首页 > news >正文

UVa 175 Keywords

news 2026/5/2 14:24:06

题目分析

本题要求根据给定的若干个兴趣配置文件（Profile \texttt{Profile}Profile）和标题（Title \texttt{Title}Title），判断每个标题是否被每个配置文件选中。选中的条件是：在标题中，存在至少一对来自配置文件的关键词，它们之间的单词个数不超过配置文件给定的阈值。

输入格式如下：

配置文件以P:开头，后面依次为一个整数阈值和至少两个小写关键词。
标题以T:开头，后跟一个以|结尾的字符串。标题可能跨多行，每行不超过80 8080个字符，总长度不超过255 255255个字符。
非字母字符被忽略，大写字母转为小写。
文件以一行#结束。

输出格式为：对于每个配置文件，输出其编号和选中的标题编号，编号从1 11开始，标题编号按升序排列，用逗号分隔。

解题思路

本题的核心是关键词匹配和距离判断。

1. 输入处理

读取每一行，判断行首是否为P:或T:。
若为P:，解析阈值和关键词，存入profiles和gaps数组。
若为T:，将多行内容拼接，直到遇到|，然后进行预处理：
- 保留字母和空格，其他字符删除。
- 大写字母转小写。
- 按空格分词，得到标题的单词列表。
遇到#时停止输入。

2. 匹配与距离判断

对于一个配置文件i ii和一个标题j jj：

配置文件中可能包含多个关键词（至少2 22个）。
我们需要判断是否存在一对关键词（可以是不相邻的顺序，如第一个和第三个），它们在标题中的位置差（即中间隔的单词数）不超过阈值g a p gapgap。
具体实现方法：
- 遍历标题中的每个单词，如果匹配到配置文件中的第p pp个关键词，则向后遍历配置文件中的其他关键词q qq（q > p q > pq>p）。
- 在标题中，只检查距离当前单词前后g a p + 1 gap + 1gap+1范围内的单词（即最多间隔g a p gapgap个单词）。
- 如果找到匹配，则返回true \texttt{true}true。

3. 输出结果

按配置文件顺序输出，每个配置文件一行，包含选中标题的编号。

注意事项

标题中的单词可能重复，因此不能简单使用find \texttt{find}find。
阈值表示中间最多可以有多少个单词，因此搜索范围为[n - gap - 1, n + gap + 1]。
行末的|是标题结束标志，|本身不出现在标题内容中。
输入中P和T后的冒号后面可能有空格，需要处理。

代码实现

// Keywords// UVa ID: 175// Verdict: Accepted// Submission Date: 2016-02-21// UVa Run Time: 0.000s#include<bits/stdc++.h>usingnamespacestd;vector<vector<string>>profiles;// 存储每个配置文件的关键词列表vector<int>gaps;// 存储每个配置文件的阈值vector<vector<string>>titles;// 存储每个标题的单词列表// 处理配置文件voidprocessProfile(string line){// 去掉开头的 "P:"line=line.substr(line.find("P:")+2);string word;intdistance;istringstreamiss(line);iss>>distance;// 读取阈值gaps.push_back(distance);// 存入 gaps 数组vector<string>keywords;while(iss>>word)keywords.push_back(word);// 读取后续关键词profiles.push_back(keywords);// 存入 profiles 数组}// 处理标题voidprocessTitle(string line){// 去掉开头的 "T:"line=line.substr(line.find("T:")+2);// 从后往前处理，删除非字母字符，并将大写字母转为小写for(inti=line.length()-1;i>=0;i--)if(isalpha(line[i])){if(isupper(line[i]))line[i]=tolower(line[i]);}elseif(line[i]!=' '&&line[i]!='\t')line.erase(line.begin()+i);// 按空格分词istringstreamiss(line);vector<string>singleTitle;string word;while(iss>>word)singleTitle.push_back(word);titles.push_back(singleTitle);}// 判断第 i 个配置文件是否选中第 m 个标题boolfindKeywords(inti,intm,intgap){// 遍历配置文件中的每一对关键词for(intj=0;j<profiles[i].size()-1;j++)for(intn=0;n<titles[m].size();n++){// 在标题中找到匹配的第一个关键词if(titles[m][n]==profiles[i][j]){// 遍历配置文件中后面的关键词for(intk=j+1;k<profiles[i].size();k++){// 计算搜索范围：[n - gap - 1, n + gap + 1]intup=n+gap+1;intdown=n-gap-1;for(intx=max(down,0);x<=min(up,(int)(titles[m].size())-1);x++){if(x==n)continue;// 跳过自身if(titles[m][x]==profiles[i][k])returntrue;// 找到匹配}}}}returnfalse;}// 对所有标题进行匹配搜索，并输出结果voidsearchTitle(){for(inti=0;i<profiles.size();i++){cout<<(i+1)<<": ";boolfirstPrinted=false;for(intj=0;j<titles.size();j++)if(findKeywords(i,j,gaps[i])){if(firstPrinted==false)firstPrinted=true;elsecout<<",";cout<<(j+1);}cout<<"\n";}}intmain(){cin.tie(0);cout.sync_with_stdio(false);string line,title;boolprofileEnded=false;// 标记是否已经遇到第一个标题while(getline(cin,line),line!="#"){// 尚未遇到标题，且当前行是配置文件if(profileEnded==false&&line.find("T:")==line.npos){processProfile(line);continue;}elseprofileEnded=true;// 开始处理标题// 拼接标题内容title+=line;// 遇到 '|' 表示一个标题结束if(line.find('|')!=line.npos){processTitle(title);title.clear();// 清空，准备下一个标题}}searchTitle();return0;}