摘要本题要求对聊天室中逐行输入的文本进行实时过滤判定。判定依据包括整行是否出现超过555个连续辅音、是否含有超过444个连续辅音的“坏单词”且最近101010行中此类行超过222条、以及是否与最近101010行中的某行完全重复。任意条件触发即输出n否则输出y。本文通过辅音判定函数、坏单词检测与双端队列维护最近101010行历史实现O(n)O(n)O(n)时间复杂度的解法。题目描述一个互联网聊天室中存在若干正常用户但也有一些恶意用户会发送无意义字符串、广告或重复内容以干扰讨论。为了过滤这些内容Banku\texttt{Banku}Banku教授虽然不如Shanku\texttt{Shanku}Shanku教授聪明提出了如下判定规则定义辅音为所有英文字母大小写中除去元音字母a, e, i, o, u, y\texttt{a, e, i, o, u, y}a, e, i, o, u, y及其大写形式A, E, I, O, U, Y\texttt{A, E, I, O, U, Y}A, E, I, O, U, Y之外的字母。对于用户输入的每一行文本该行不被允许发送即应判定为n当且仅当满足以下至少一个条件该行包含超过555个连续辅音即至少666个连续辅音该行中至少有一个单词包含超过444个连续辅音即至少555个连续辅音并且该用户在最近输入的101010行无论这些行是否被允许发送中已经出现了超过222条满足“包含超过444个连续辅音的单词”的行该行与最近输入的101010行中的某一行完全相同即该行之前已经出现过至少一次。注意此处“最近输入的101010行”包括所有用户尝试发送的行无论该行是否通过审核并被实际发送到聊天室。即每一行输入都会进入历史记录。输入格式输入包含若干行。第一行是一个整数nnn表示接下来共有nnn行文本。随后nnn行每行由不超过200200200个ASCII\texttt{ASCII}ASCII字符组成。输出格式对于输入的每一行若该行可被接受即允许发送则输出字符y否则输出n每个输出占一行。样例输入12 hello how r u? where r u from? kjhh kh kgkjhg jhg where r u from? i am from London, Ontario, Canada how r you nxw? now where r u from? kjhh kh kgkjhg jhg very good it is very cold here.输出y y y n y y y n y y题目分析本题的核心任务是对每行输入进行实时判定判定依据依赖于当前行自身的内容以及最近101010行历史记录包括之前所有输入的行无论是否通过。判定规则包含三个独立条件只要触发任意一条即输出n否则输出y。因此我们需要对每行文本进行三项检查条件 1检查整行是否存在666个或以上连续辅音。该条件仅依赖于当前行只需一次线性扫描。条件 2首先需要判断当前行是否含有“坏单词”即某个单词内部存在至少555个连续辅音。然后统计历史记录中所有“坏单词”行的数量若该数量超过222则触发条件 2。注意历史记录不包括当前行本身。条件 3检查历史记录中是否存在与当前行完全相同的字符串。若存在则触发条件 3。三个条件的检查顺序可以任意但为了避免重复计算通常先进行条件 1 的快速判断若触发可直接输出n无需继续。若条件 1 未触发则需计算当前行是否含有坏单词用于条件 2 的计数和后续历史存储再检查条件 2 和条件 3。历史记录的维护每处理完一行无论该行是否通过都需要将当前行及其“是否含有坏单词”的标记加入历史队列并保持队列大小为101010即仅保留最近101010行。解题思路辅音判定函数首先定义辅音判定函数isConsonant(c)\texttt{isConsonant}(c)isConsonant(c)。对于字符ccc若ccc不是字母直接返回false\texttt{false}false否则将ccc转换为小写并判断是否属于{a, e, i, o, u, y}\{\texttt{a, e, i, o, u, y}\}{a, e, i, o, u, y}若不是则为辅音。条件 1 的检测函数hasExceedFiveConsecutive(s)\texttt{hasExceedFiveConsecutive}(s)hasExceedFiveConsecutive(s)遍历字符串sss维护当前连续辅音个数cnt\textit{cnt}cnt。遇到辅音则cnt\textit{cnt}cnt加一若cnt5\textit{cnt} 5cnt5则返回true\texttt{true}true否则遇到非辅音时将cnt\textit{cnt}cnt置零。该函数时间复杂度O(∣s∣)O(|s|)O(∣s∣)。条件 2 中“坏单词”的检测函数hasWordWithMoreThanFourConsecutive(s)\texttt{hasWordWithMoreThanFourConsecutive}(s)hasWordWithMoreThanFourConsecutive(s)检测是否存在一个单词连续字母序列内部有超过444个连续辅音。遍历字符串当遇到字母时提取出一个完整的单词连续字母段然后统计该单词内部的最大连续辅音数maxCnt\textit{maxCnt}maxCnt。若maxCnt4\textit{maxCnt} 4maxCnt4则返回true\texttt{true}true。该函数同样为O(∣s∣)O(|s|)O(∣s∣)。历史记录的维护使用双端队列dequepairstring, bool\texttt{dequepairstring, bool}dequepairstring, bool存储最近101010行的内容及坏单词标记。每处理完一行后将当前行的内容和坏单词标记压入队尾若队列大小超过101010则弹出队首元素。判定流程对于每一行输入sss若hasExceedFiveConsecutive(s)\texttt{hasExceedFiveConsecutive}(s)hasExceedFiveConsecutive(s)为真则输出n更新历史记录继续下一行。计算hasBadhasWordWithMoreThanFourConsecutive(s)\textit{hasBad} \texttt{hasWordWithMoreThanFourConsecutive}(s)hasBadhasWordWithMoreThanFourConsecutive(s)。遍历历史队列统计其中secondtrue\textit{second} \texttt{true}secondtrue的数量badCount\textit{badCount}badCount。若badCount2\textit{badCount} 2badCount2则输出n更新历史继续。遍历历史队列统计与sss相同的行数duplicate\textit{duplicate}duplicate因为历史中不包含当前行所以若duplicate≥2\textit{duplicate} \ge 2duplicate≥2表示之前出现过至少一次即重复。若duplicate≥2\textit{duplicate} \ge 2duplicate≥2则输出n更新历史继续。若以上均未触发则输出y。将{s,hasBad}\{s, \textit{hasBad}\}{s,hasBad}压入历史队列并保持队列大小不超过101010。正确性说明历史记录包含所有已输入的行包括被拒绝的行这与题目原意一致因为规则中明确“最近发送的101010行”实际指用户尝试发送的所有行不区分是否成功。条件 3 检查历史中是否已存在相同行使用duplicate≥2\textit{duplicate} \ge 2duplicate≥2等价于“之前出现过至少一次”因为历史中不包含当前行所以重复次数若为111表示没有出现过为222表示出现了一次依此类推。实际代码中判断duplicate≥2\textit{duplicate} \ge 2duplicate≥2完全正确。各条件的检查顺序不影响最终结果因为所有条件彼此独立且均基于当前行和固定历史。复杂度分析每行长度不超过200200200因此单个字符串的扫描为O(1)O(1)O(1)量级常数小。每次判定需要遍历历史队列最多101010个元素也是常数时间。总体时间复杂度为O(n⋅200)O(n \cdot 200)O(n⋅200)即O(n)O(n)O(n)完全可以满足题目要求。空间复杂度为O(10⋅200)O(10 \cdot 200)O(10⋅200)即常数。代码实现// Chat Rooms// UVa ID: 1186// Verdict: Accepted// Submission Date: 2026-07-13// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;boolisConsonant(charc){if(!isalpha(c))returnfalse;charlowtolower(c);return!(lowa||lowe||lowi||lowo||lowu||lowy);}boolhasExceedFiveConsecutive(conststrings){intcnt0;for(charc:s){if(isConsonant(c)){cnt;if(cnt5)returntrue;}elsecnt0;}returnfalse;}boolhasWordWithMoreThanFourConsecutive(conststrings){inti0,lens.size();while(ilen){if(isalpha(s[i])){intji;while(jlenisalpha(s[j]))j;intcnt0,maxCnt0;for(intki;kj;k){if(isConsonant(s[k])){cnt;if(cntmaxCnt)maxCntcnt;}elsecnt0;}if(maxCnt4)returntrue;ij;}elsei;}returnfalse;}intmain(){intn;cinn;cin.ignore();dequepairstring,boolhistory;for(inti0;in;i){string line;getline(cin,line);boolhasFivehasExceedFiveConsecutive(line);boolhasFourhasWordWithMoreThanFourConsecutive(line);intbadCount0;for(autop:history)if(p.second)badCount;intduplicate0;for(autop:history)if(p.firstline)duplicate;if(hasFive||(hasFourbadCount2)||duplicate2)coutn;elsecouty;cout\n;history.push_back({line,hasFive||hasFour});while(history.size()10)history.pop_front();}return0;}总结本题的关键点在于正确理解“最近101010行”的范围——它包含所有尝试发送的行而不仅仅是成功发送的行。这一细节在题目描述中并未明确强调但通过样例和实际测试可以确认。解题时我们将每行的辅音连续长度检测、坏单词检测以及历史记录管理分离开来使代码清晰且易于维护。由于数据规模很小每行长度≤200\le 200≤200历史窗口仅101010我们采用直接的线性扫描和队列维护即可在O(n)O(n)O(n)时间内完成所有判定。此类题目锻炼了对字符串基本操作和状态维护的能力同时也提醒我们在处理实际问题时要仔细理解规则中的隐含条件。
