网易雷火2020秋招笔试真题
网易雷火2020秋招笔试真题
1、模拟点击
【题目描述】本题需要让你模拟一下在Windows系统里窗口和鼠标点击的操作，具体如下：
1.屏幕分辨率为3840*2160，左上角坐标为(0, 0)， 右下角坐标为(3839, 2159)
2.窗口是一个矩形的形状，由左上角坐标(X, Y)，和宽高(W, H)，四个数字来定位。左上角坐标为(X, Y)、右下角坐标为(X+W, Y+H)，其中左上角坐标一定会在屏幕范围内，其他一些部分可能会超过屏幕范围。
3.窗口的点击和遮挡规则同Windows，但是不考虑关闭窗口、最大化、最小化和强制置顶的情况。即
3.1 如果发生重叠的话，后面打开的窗口会显示在前面打开的窗口上面
3.2 当鼠标发生一次点击的时候，需要判断点击到了哪个窗口，如果同个坐标有多个窗口，算点击到最上层的那个
3.3 当一个窗口被点击的时候，会浮动到最上层
输入描述
每个测试输入包含1个测试用例
第一行为2个整数N, M。其中N表示打开的窗口数目，M表示鼠标点击的数目。其中0<N,M<1000
接下来N行，每一行四个整数 Xi Yi Wi Hi，分别表示第i个窗口（窗口Id为i，从1开始计数）的左上角坐标以及宽高，初始时窗口是按输入的顺序依次打开。其中 0<=Xi<3840, 0<=Yi<2160, 0<Wi<3840, 0<Hi<2160
再接下来有M行，每一行两个整数 Xj Yj，分别表示接下来发生的鼠标点击坐标。其中0 <=Xj<3840, 0<=Yj<2160
输出描述
对于每次鼠标点击，输出本次点击到的窗口Id。如果没有点击到窗口，输出-1
示例1
输入
2 4 100 100 100 100 10 10 150 150 105 105 180 180 105 105 1 1
输出
2 1 1 -1
【解题思路】
根据题意模拟即可。
【参考代码】
#include "stdio.h"
struct WIND_t {
int pri;
int x, y;
int w, h;
};
WIND_t wnd[2000];
int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
int PRI = 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &wnd[i].x, &wnd[i].y, &wnd[i].w, &wnd[i].h);
wnd[i].pri = ++PRI;
}
for (int i = 0; i < m; i++) {
int cx, cy;
scanf("%d%d", &cx, &cy);
int ans = -1;
int anspri = -1;
for (int j = 1; j <= n; j++) {
WIND_t &t = wnd[j];
if (t.x <= cx && cx <= t.x + t.w && t.y <= cy &&
cy <= t.y + t.h) {
if (ans == -1 || anspri < t.pri) {
ans = j;
anspri = t.pri;
}
}
}
if (ans > 0)
wnd[ans].pri = ++PRI;
printf("%d\n", ans);
}
}
return 0;
}
2、Stern-Brocot tree
【题目描述】The Stern-Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a search tree.
Figure 1 shows a part of the Stern-Brocot tree, which has the first 4 rows. Each node in the tree is marked in a red cycle. The value in the node is the mediant of the left and right fractions. The mediant of two fractions A/B and C/D is defined as (A+C)/(B+D).
To construct the Stern-Brocot tree, we first define the left fraction of the root node is 0/1, and the right fraction of the root node is 1/0. So the value in the root node is the mediant of 0/1 and 1/0, which is (0+1)/(1+0)=1/1. Then the value of root node becomes the right fraction of the left child, and the left fraction of the right child. For example, the 1st node in row2 has 0/1 as its left fraction and 1/1(which is the value of its parent node) as its right fraction. So the value of the 1st node in row2 is (0+1)/(1+1)=1/2. For the same reason, the value of the 2nd node in row2 is (1+1)/(1+0)=2/1. This construction progress goes on infinitly. As a result, every positive rational number can be found on the Stern-Brocot tree, and can be found only once.
Given a rational number in form of P/Q, find the position of P/Q in the Stern-Brocot Tree.
输入描述
Input consists of two integers, P and Q (1<=P,Q<=1000), which represent the rational number P/Q. We promise P and Q are relatively prime.
输出描述
Output consists of two integers, R and C.
R indicates the row index of P/Q in the Stern-Brocot Tree, C indicates the index of P/Q in the row.
Both R and C are base 1.
We promise the position of P/Q is always in the first 12 rows of the Stern-Brocot tree, which means R<=12.
示例1
输入
5 3
输出
4 6
【解题思路】
实现一个分数类，然后进行模拟运算即可。
【参考代码】
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
static inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct fraction {
int p, q;
fraction(int p, int q) {
int t = gcd(p, q);
this->p = p / t;
this->q = q / t;
}
bool operator==(const fraction &o) const { return p == o.p && q == o.q; }
bool operator>(const fraction &o) const { return p * o.q > o.p * q; }
bool operator<(const fraction &o) const { return p * o.q < o.p * q; }
};
int main() {
int p, q;
scanf("%d%d", &p, &q);
fraction target(p, q);
fraction left(0, 1);
fraction right(1, 0);
fraction curr(1, 1);
int level = 0;
unsigned int count = 0;
unsigned int index = 0;
for (;;) {
if (target == curr) {
printf("%d %u\n", level + 1, index + 1 - count); // base 1
break;
}
if (target < curr) {
index = 2 * index + 1;
right = curr;
} else {
index = 2 * index + 2;
left = curr;
}
curr = fraction(left.p + right.p, left.q + right.q);
count += (1 << level);
level++;
}
return 0;
}
3、聊天消息排版
【题目描述】在网游中，聊天功能是一项非常重要的功能，加上玩家可以打出游戏内置的一些表情图片，因此需要实现一个图文混排系统，如上图所示。
玩家在聊天框输入的是一段utf-8编码的文字，且只会包含中文、英文、中英文的标点符号和空格（不会出现换行、回车和制表符）。按照网易游戏的传统，井号(#)是作为一个转义字符，支持下面几种转义行为：
1. #加一个数字来表示内置的表情图片，为了简化问题，我们这里只支持20个表情图片，从0开始计数，并且数字是按最长匹配原则去匹配，比如#0表示0号表情图片、#1表示1号表情图片、#19表示19号表情图片、#20则表示2号表情图片后面加数字0。需要注意的是#00表示的是0号表情图片加后面数字0。
2. #r表示换行，遇到以后会自动切换到下一行开始排版。
3. ##表示显示出#这个符号
4.如果玩家不按规则输入错误的转义，则按照玩家的输入原样显示，比如#a、#、#,、#啊
上图所示的玩家输入为：“Hello world#大家好#r欢迎大家参加网易雷火校园招聘#1祝大家取得好成绩”
排版的时候需要像上图一样，将文字从起始位置开始，依次显示在聊天窗口里，一些显示规则如下所示：
1.聊天窗口的宽度固定为W像素，起始坐标为左上角，坐标为(0, 0)，右上角坐标为(W-1, 0)，坐标向右向下增长。任何文字和表情必须显示在窗口内，不能超出窗口。但是高度可以无限向下延伸。
2.显示的字体均为等宽字体，英文（包括英文标点符号和空格）的字体宽度统一为XE，高度统一为YE。中文（包括中文的标点符号）的字体宽度统一为XC，高度统一为YC。
3.每个表情图片的宽高是独立的，0号表情图片的宽度为X0，高度Y0，依次类推，19号表情图片的宽度为X19，高度为Y19。
4.字符（中英文以及标点符号、空格等，下同）与字符之间、字符与表情之间、表情与表情之间都需要额外保留一个PX像素的字间距。每一行第一个字符左边，以及最后一个字符右边不需要保留字间距。
5.当下一个字符或者表情无法在本行W宽度的像素内完整显示的话，则会强行换到下一行首开始显示。遇到#r的时候也会自动换到下一行开始显示下一个字符或表情。
6.在一行里出现高度不同的中英文以及表情的时候，需要将其底部对齐。
7.当一行里没有任何字符或表情，直接被#r换行的时候，这一行的高度算英文字体的高度。
8.每一行里高度最高的字符或表情，需要同上一行的的底部保留PY像素的行间距。第一行上面与最后一行下面不需要保留行间距。
9.最后一个字符或表情显示显示以后，它的右下角坐标则为结束坐标。也就是本题需要求解的问题。输入保证最后不会以#r结尾。
输入描述
每个测试输入包含1个测试用例
第一行为7个正整数W, XE, YE, XC, YC, PX, PY
第二行为40个正整数X0,
Y0, X1, Y1…X19, Y19
第三行为长度不超过10000的十六进制编码过的玩家输入，即玩家输入的utf-8编码的数据每个字节的数字转成大写的十六进制表示，不足两位的话前面补0（同C里printf的%X格式化），然后不同字节的十六进制编码表示依次拼接起来。
比如Hello的十六进制编码表示为48656C6C6F。
前两行的各个数字含义如上文描述，其中50<W<10000，0<其他<50。
输出描述
输出用空格隔开的两个数字，表示结束坐标
示例1
输入
60 2 4 3 4 1 3 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 48656C6C6F20776F726C6423E5A4A7E5AEB6E5A5BD2372E6ACA2E8BF8EE5A4A7E5AEB6E58F82E58AA0E7BD91E69893E***7E781ABE6A0A1E59BADE68B9BE881982331E7A59DE5A4A7E5AEB6E58F96E5BE97E5A5BDE68890E7BBA9
输出
38 19
【解题思路】
大模拟题，注意各种情况的讨论。
【参考代码】
#include "stdio.h" #define MAXN 100000 int W, XE, YE, XC, YC
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
<p> 本专刊由牛客官方团队打造，主要讲解名企校招技术岗位的笔试题。 内容中包含多个名企的笔试真题，附有题目思路及参考代码 本专刊购买后即可解锁所有章节，故不可以退换哦~ <
