首先恭喜你通过网络赛来到这里,并且做到了第二道题,相信现在的你在OJ上做题已经有一定的经验了。不仅仅是在OJ上,我们日常浏览任何网站,都有一个看不见的程序在十分辛苦地为我们工作着,那就是数据库,比如在acm.xidian.edu.cn上,当你点击你的用户名的时候,页面需要向你展示很多关于你的信息,你做过的题目,你的邮箱等等,而这些信息存在于数据库中的不同表(这里你可以当成集合)中,所以如何在你一次请求中把这些信息整合出来反馈给你呢?这需要数据库中的多表查询(从多个集合中找到你需要的信息),这就是你在这道题目中要解决的问题。
看到努力学习算法的你,为了给你练习的机会,你们的导员交给你一个任务:
首先我们规定下面第一行之下的的每一行为集合的一个元素,我们有两个集合如下:
上面展示了集合中的三个元素{张三,1234},{李四,5678},{V8,2333},这个集合可能存在于你们导员的电脑里的一个Excel文档中,仅包含你们的一些基本信息。
第二个集合表示选课情况:
每一行表示一个人,每个人只选一门或者不选课,学号没有重复。现在导员想统计班级里同学的选课情况,并且想清楚的知道哪些同学选课而哪些同学没选,所以他希望最终的统计表中有所有人的姓名学号,没选课的同学在课程名这一列填写"NULL"(不含引号,下同),按照学号从小到大开始自上而下排列,注意要保留列标题,比如上面展示出来的部分集合,经过处理之后最终的统计表如下:
上述规则其实就是数据库中的“左连接”,如何在大量数据中快速找到需要的信息是非常具有挑战性的问题,所以说算法在计算机世界十分重要(˘••˘), 但是为了不影响你接下来比赛的心情,我们的集合非常小,大约就是一个普通班级的人数,保证集合元素个数不超过 130。