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

UVa 335 Processing MX Records

news 2026/5/30 23:35:57

题目描述

域名系统（DNS\texttt{DNS}DNS）的主要功能是将符号化机器名（如bigone.stateu.edu）映射到对应的网络地址（如24.99.100.33）。机器名的各个部分由点分隔，从右向左读取时对应树中的节点。内部节点对应域（domain\texttt{domain}domain）。例如，.edu域下是所有美国大学和学院的机器，而加拿大的所有机器都在.ca域下。

通过提供一个或多个MX\texttt{MX}MX记录，系统管理员可以安排DNS\texttt{DNS}DNS将发往一台机器的邮件重定向到另一台机器。重定向在许多情况下是合适的，其中一个常见用途是为虚构的、具有有意义名称的机器创建邮件地址。例如，允许邮件发送到info.stateu.edu，但校园内并没有名为info的物理机器。通过使用适当的MX\texttt{MX}MX记录，可以将邮件重定向到bigone.stateu.edu。

在本题中，我们将处理简化版的MX\texttt{MX}MX记录。

MX 记录格式

一个MX\texttt{MX}MX记录包含三个字段（由空白字符分隔）：

第一字段：源机器名（目标邮件地址的机器名）
第二字段：偏好值（非负整数，数值越小优先级越高）
第三字段：目标机器名（邮件实际投递的目标）

如果第一字段不存在（即行首为空格），则假定它与前一行的第一字段相同。

通配符记录

通配符MX\texttt{MX}MX记录允许使用一条记录将邮件重定向到多台机器。例如：

*.citycc.midville.edu 0 tiny.stateu.edu

将任何以.citycc.midville.edu结尾的机器名的邮件重定向到tiny.stateu.edu。

简化假设：通配符*只出现在符号名的第一部分，且任何符号名中不会出现超过三个点。

命令

在NNN条MX\texttt{MX}MX记录之后，输入包含以下命令：

U machine：机器上线（up\texttt{up}up）
D machine：机器下线（down\texttt{down}down）
A machine：查询邮件重定向目标
X：输入结束

所有机器初始为上线状态。

注意：MX\texttt{MX}MX记录不会被递归处理。即，如果first.com的邮件被重定向到second.com，任何可能将second.com重定向到其他机器的MX\texttt{MX}MX记录都不会在处理first.com时被检查。

输入格式

第一行包含整数NNN，接下来NNN行每行一个MX\texttt{MX}MX记录。剩余行每行以U、D、A或X开头。

输出格式

对于每个A命令，输出一行：

machine => destination

如果没有适用的MX\texttt{MX}MX记录，输出：

machine =>

样例输入

5 service.stateu.edu 10 tiny.stateu.edu info.stateu.edu 0 bigone.stateu.edu 10 tiny.stateu.edu service.stateu.edu 5 bigone.stateu.edu *.smallu.edu 10 service.stateu.edu A alpha.cs.smallu.edu A info.stateu.edu D bigone.stateu.edu A info.stateu.edu A nowhere.com X

样例输出

alpha.cs.smallu.edu => service.stateu.edu info.stateu.edu => bigone.stateu.edu info.stateu.edu => tiny.stateu.edu nowhere.com =>

题目分析

问题的本质

这是一个字符串匹配 + 优先级选择问题。给定一组MX\texttt{MX}MX记录，每条记录包含：

源模式（完整域名或通配符模式）
优先级（数值越小优先级越高）
目标机器

当查询一个机器名时，需要：

找到所有匹配该机器名的MX\texttt{MX}MX记录
选择优先级最高（数值最小）且目标机器为上线状态的记录
输出目标机器名；如果没有匹配，则不输出目标

匹配规则

精确匹配：源模式与机器名完全相同
通配符匹配：源模式形如*.domain，匹配所有以.domain结尾的机器名

匹配优先级：在相同优先级下，精确匹配优先于通配符匹配？题目没有明确说明，但从样例可知，需要取所有匹配记录中优先级最高的，如果优先级相同，取哪个？题目没有要求，只需输出一个即可。

机器状态

初始所有机器为上线（up\texttt{up}up）
U machine将机器设为上线
D machine将机器设为下线

只有上线的目标机器才能被选为最终目的地。

参考代码

// Processing MX Records// UVa ID: 335// Verdict: Accepted// Submission Date: 2016-07-07// UVa Run Time: 0.170s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 机器状态：true=在线，false=离线map<string,bool>status;// MX 记录索引（仅用于记录，实际未使用）map<string,int>indexer;// MX 记录存储：源模式 -> (优先级, 目标) 的多重映射map<string,multimap<int,string>>records;// 判断机器是否在线（已注册且状态为 true）inlineboolisMachineLive(string machine){return(status.find(machine)!=status.end()&&status[machine]);}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn,second_field;string line,last_first_field,first_field,third_field,machine;istringstream iss;// 读取 MX 记录数量getline(cin,line);n=stoi(line);// 读取并存储所有 MX 记录for(inti=1;i<=n;i++){getline(cin,line);iss.clear();iss.str(line);// 判断第一字段是否存在（行首是否有空格）if(line.front()!=' '){iss>>first_field>>second_field>>third_field;last_first_field=first_field;}else{iss>>second_field>>third_field;first_field=last_first_field;}// 存储记录records[first_field].insert(make_pair(second_field,third_field));indexer[first_field]=i;// 初始化机器状态为在线status[first_field]=true;status[third_field]=true;}charaction;while(getline(cin,line),line.front()!='X'){iss.clear();iss.str(line);iss>>action>>machine;if(action=='U'||action=='D'){// 更新机器状态if(status.find(machine)!=status.end())status[machine]=(action=='U');// 通配符模式的状态更新elseif(status.find("*."+machine)!=status.end())status["*."+machine]=(action=='U');}elseif(action=='A'){cout<<machine<<" =>";boolflag=false;intminPreference;string destination;// 1. 精确匹配for(autorecord:records[machine]){if(isMachineLive(record.second)){minPreference=record.first;destination=record.second;flag=true;break;// 由于 map 按优先级升序存储，第一个即为最优}}// 2. 通配符匹配：逐级检查for(intstart=machine.find('.',0);start!=string::npos;start+=1,start=machine.find('.',start)){string next_machine="*"+machine.substr(start);for(autorecord:records[next_machine]){if(isMachineLive(record.second)){if(!flag){minPreference=record.first;destination=record.second;flag=true;}elseif(record.first<minPreference){minPreference=record.first;destination=record.second;}}}}if(flag)cout<<" "<<destination;cout<<endl;}}return0;}