PAT Basic 1065 单身狗

简介: 单身狗(25)时间限制300 ms内存限制65536 kB代码长度限制8000 B判题程序Standard作者CHEN, Yue“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。
  1. 单身狗(25)

时间限制
300 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

输入格式:

输入第一行给出一个正整数N(<=50000),是已知夫妻/伴侣的对数;随后N行,每行给出一对夫妻/伴侣——为方便起见,每人对应一个ID号,为5位数字(从00000到99999),ID间以空格分隔;之后给出一个正整数M(<=10000),为参加派对的总人数;随后一行给出这M位客人的ID,以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式:

首先第一行输出落单客人的总人数;随后第二行按ID递增顺序列出落单的客人。ID间用1个空格分隔,行的首尾不得有多余空格。

输入样例:
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
输出样例:
5
10000 23333 44444 55555 88888

思路:把已婚人士记录到一个hash表中,互为对方id;查询阶段,每个query在已婚人士表中查看,没有查到则肯定单身,放到vector容器;查到了则放置到“等候区”,将其标记值设定为1;如果他/她配偶也在等候区那么她配偶的等候标记也等于1,那么两个人的等候标记都修改为2(表示双方都在场);随后遍历等候区,根据等候标记值是否等于1表示是否为单身狗,是则放入单身狗的vector容器。最后,单身狗的vector容器排序,再输出结果。

注意如果没有单身狗则不要输出多余换行。题目不说这点略坑。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <set>
#include <iomanip>
#include <sstream>
#include <unordered_map>

using namespace std;


int main() {
    unordered_map<string, string> mp;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        mp[a] = b;
        mp[b] = a;
    }
    int k;
    cin >> k;
    vector<string> v_dog;
    unordered_map<string, int> wait_region;
    for (int i = 0; i < k; i++) {
        string q_id;
        cin >> q_id;
        if (mp[q_id] == "") {
            v_dog.push_back(q_id);
        }
        else {
            wait_region[q_id] = 1;
            if (wait_region[mp[q_id]] == 1) {
                wait_region[q_id] = 2;
                wait_region[mp[q_id]] = 2;
            }
        }
    }
    unordered_map<string, int>::iterator it = wait_region.begin();
    for (; it != wait_region.end(); it++) {
        if (it->second == 1) {
            v_dog.push_back(it->first);
        }
    }

    cout << v_dog.size() << endl;
    sort(v_dog.begin(), v_dog.end());
    for (int i = 0; i < v_dog.size(); i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << v_dog[i];
    }
    if (v_dog.size() > 0) {
        cout << endl;
    }
    
    return 0;
}

/*
使用了unordered_map来做,其实用数组也OK,只不过哈希表对于字符串类型id也适用。
第一个坑:结果要排序
第二个坑:如果单身狗数量为0,则不应该输出换行。题目居然不说这一点,好坑
*/
目录
相关文章
|
Linux 数据安全/隐私保护
Linux权限 - 概念与管理 | 文件权限的修改与转让 【详解】
Linux权限 - 概念与管理 | 文件权限的修改与转让 【详解】
366 0
Linux权限 - 概念与管理 | 文件权限的修改与转让 【详解】
|
设计模式 Java 关系型数据库
【阿里规约】阿里开发手册解读——命名规范篇
本文中所有代码命名规范遵循《阿里规约》,从包名、类名、变量名等角度展开,详细阐述测试类、枚举类、数组、布尔型变量、方法等元素的命名规范。
【阿里规约】阿里开发手册解读——命名规范篇
【ChatGLM】本地版ChatGPT ?6G显存即可轻松使用 !ChatGLM-6B 清华开源模型本地部署教程
【ChatGLM】本地版ChatGPT ?6G显存即可轻松使用 !ChatGLM-6B 清华开源模型本地部署教程
776 0
|
6月前
|
数据采集 DataWorks 监控
《打破壁垒:DataWorks ETL与AI算法的深度融合变革》
在数字化时代,数据成为企业发展的核心驱动力。DataWorks作为强大的大数据开发治理平台,其ETL流程与人工智能算法的融合,显著提升了数据处理效能。传统ETL依赖预设规则,面对海量复杂数据时效率低下且易出错。而人工智能赋能的ETL实现了智能数据抽取、自适应数据转换和实时数据质量监控,极大提高了数据处理的准确性和灵活性。以电商企业为例,融合后的系统加速了数据接入、优化用户分类与推荐,并通过实时监控避免决策失误,显著提升客户满意度和销售额。这一变革助力企业在激烈竞争中实现数字化转型与创新。
129 1
|
7月前
|
人工智能 程序员 iOS开发
一文彻底学会HarmonyOS的AI编程助手
本文介绍了华为官方AI辅助编程工具CodeGenie,该工具支持HarmonyOS NEXT领域的智能问答、ArkTS代码补全/生成及万能卡片生成,显著提升开发效率。安装步骤包括下载插件、离线安装及授权登录,功能涵盖知识问答、代码补全与生成、以及智能生成HarmonyOS万能卡片。
289 0
|
10月前
|
存储 缓存 算法
什么是配置中心页面?
【10月更文挑战第24天】什么是配置中心页面?
215 3
|
机器学习/深度学习 自动驾驶 机器人
深度学习之3D场景重建
基于深度学习的3D场景重建是通过深度学习技术从多视角图像或视频数据中重建三维场景结构的过程。它在计算机视觉、增强现实、虚拟现实、机器人导航和自动驾驶等多个领域具有广泛应用。
538 4
|
安全 Python Windows
游戏开发丨基于Tkinter的扫雷小游戏
游戏开发丨基于Tkinter的扫雷小游戏
307 3
|
API C++ Windows
Windows API Hooking 学习
Windows API Hooking 学习
|
消息中间件 算法 Java