搜狗2020校招【研究】笔试（第二场）
时长:120分钟 总分:100分
111浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 2 |
1.
垃圾邮件分类问题
编写Naïve Bayes分类模型对邮件文本进行分类，判断该邮件是不是垃圾邮件（二分类）。我们已经通过数据预处理，将原始的邮件文本数据转化为分类器可用的数据向量形式，具体：数据表示为整型数向量x=(x1,x2,…,xd)。d是数据特征向量的维数，每个输入数据样本的格式为:
Label x1 x2 … xd
其中Label为0或者1的整型数字（0表示正常邮件，1表示垃圾邮件）；
x1 x2 … xd是离散化后的特征，表示为从0开始的自然数；
维度d小于20；
如果Label=?，则表示希望输出的预测类别值（需要预测的类别一定已在对应的训练数据中已经出现过）。
输入描述： 输入格式如下：第一行三个数字M N d，M是训练集的大小，N是测试集的大小，d是数据维数。接下来是M行训练数据样本,然后是N行需要预测的样本。输入样例： 4 2 3 1 13 0 10 0 6 11 2 1 17 2 14 0 8 16 13 ? 20 3 19 ? 2 13 18 输出描述： 期望的输出：每条待预测样本的标签输出样例 1 0
2.
水雷阵列
本题分两问，第一问占20分，第二问占10分。
一条小河（在笛卡尔坐标系中，用 y=0 和 y=100.0 表示其两岸），其中被敌人布了若干（N 个）电磁水雷，其感应半径为 R 。我方一只小船（不计体积和大小，看做一个点）只要和水雷的距离 L <= R 就会触发爆炸，那么（第1问）小船是否可以不被发现地闯过水雷阵？如果小船可以闯过水雷阵，那么（第二问）敌方最少还需要增补多少个（数量记为 M）引爆半径为 D 的新型水雷才能对我方小船实时封锁？
如上图，假如只有1、2、3三个水雷（圆圈代表其触发范围），那结论为“否”（无法闯过）；假如只有4、5、6、7四个水雷，那结论为“是”（可以闯过），如果新型水雷如上图和6号水雷相连的小圆，那么再需要1个就能封锁住小船了（M等于1）。
输入描述：每个测试数据集包含 2～20 种情况，每种情况一行，每行包含 3+N*2 个数字（空格分隔），第1个数字为N表示有N个水雷（1<=N<=100），第2个数字为该组水雷的感应半径 R，第3个数字为新增水雷的感应半径 D，后面依次是N个水雷的中心坐标(xi, yi)，其中0<yi<100.0（水雷当然都布在水里），0<xi<500.0。
共15个测试文件，其中前3个测试文件仅包含不超过2个水雷，前10个测试文件D等于0。
输入样例：
3 10.0 0.0 13.3 14.2 15.7 25.0 33.3 59.8
1 70.0 0.0 40.5 60.5
2 30.0 30 40.5 35.5 65.6 64.5 输出描述：
对应输入文件的情况，每种情况一行输出。若D等于0，则输出 N（不能闯过）或 Y（可以闯过）
若D不等于0，则输出 N（不能闯过）或者数字 M（最小需要增补的水雷数）。输出样例 Y N 2
