记五道2020年某企业提前批招聘笔试题

窗口点击模拟

• 描述：

本题需要让你模拟一下在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

• 样例输入：

2 4
100 100 100 100
10 10 150 150
105 105
180 180
105 105
1 1

• 样例输出：

2
1
1
-1

• 样例说明：

有2个窗口，第1个窗口左上角坐标为(100,100)，宽和高都是100，则其右下角坐标为(200,200)；
第2个窗口左上角坐标为(10,10)，宽和高都是150，则其右下角坐标为(160,160)。

有4次鼠标点击，第1次点击的位置同时属于1号和2号窗口，但由于2号窗口在上面，所以它被选择并且被置于顶层；
第2次点击的位置只属于1号窗口，因此该次点击选择了1号窗口并将其置于顶层，现在1号窗口在上，2号窗口在下；
第3次点击的位置同时属于1号和2号窗口的范围，但由于1号窗口在上，所以它被选择；
第4次点击的位置不属于任何窗口。

• 解题思路：模拟

用一个结构体数组存给出的窗口信息，根据题意，数组中越靠后的窗口优先级越高，因此，每次点击从数字后面开始扫描，扫到满足点击的窗口就输出对应的编号，并将它提到末尾。

• 参考代码:

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
const int M=1010;
int n,m;

struct win {
    int id,x,y,w,h;
}wins[N];//存窗口的结构体数组

//将窗口i置于顶层
void top(int i) {
    win t=wins[i];
    for(;i<n-1;i++) wins[i]=wins[i+1];
    wins[n-1]=t;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d%d%d%d",&wins[i].x,&wins[i].y,&wins[i].w,&wins[i].h);
        wins[i].id=i+1;
    }
    while(m--) {
        int dx,dy,flag=0;
        scanf("%d%d",&dx,&dy);
        for(int i=n-1;i>=0;i--) {
            //判断鼠标点击范围
            if(dx>=wins[i].x&&dy>=wins[i].y&&dx<=wins[i].x+wins[i].w&&dy<=wins[i].y+wins[i].h) {
                printf("%d\n",wins[i].id);
                top(i);
                flag=1;
                break;
            }
        }
        if(!flag) printf("-1");
    }
    return 0;
}

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 thefirst 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, everypositive 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 B 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.

• 样例输入：

5 3

• 样例输出：

4 6

• 解题思路：数学+二分

• 参考程序：

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;

struct Fraction {
    int m,n;
}sl,sr,input;
int row,col;

int main(){
    int summ,sumn;
    scanf("%d%d",&input.m,&input.n);
    if(input.m!=1||input.n!=1) {
       //string ans;
       sl.m=0,sr.m=1;
       sl.n=1,sr.n=0;
       row=1;
       col=1;
       while(1){
            summ=sl.m+sr.m;
            sumn=sl.n+sr.n;
            int temp=input.m*sumn-input.n*summ;
            if(temp>0){ // input.m/input.n>summ/sumn --> input.m*sumn-input.n*summ>0
                // ans+='R';
                row++;
                col*=2;
                sl.m=summ;
                sl.n=sumn;
            }
            else if(temp==0) // input.m/input.n==summ/sumn --> input.m*sumn-input.n*summ==0
                break;
            else{ // input.m/input.n<summ/sumn --> input.m*sumn-input.n*summ<0
                // ans+='L';
                row++;
                col=2*col-1;
                sr.m=summ;
                sr.n=sumn;
            }
        }
        printf("%d %d\n",row,col);
    }
    return 0;
}

双人数字游戏

• 描述：

游戏规则如下

• 在棋盘上有N个数字（A1 ~ AN）从左到右排列成一行

• A，B两个玩家轮流进行游戏，第一回合A玩家行动，第二回合B玩家行动，依次行动直到游戏结束

• 每回合玩家可以选择拿走棋盘上最左边或者最右边的一个数字，其余的都不能拿

• 拿走的数字依次从左到右排列在自己面前

• 棋盘上所有数字被拿走后游戏结束

• 最优策略的说明：在任意局面下，玩家如果取左边的数字或者取右边的数字，最终最优得分都一样，那么只能取左边的数字

当所有数字都被拿走后，A，B两个玩家面前都各有一个数列。

假设A玩家面前数字从左到右为X1，X2，X3…XM，则他的最终得分Sa计算方式如下（B玩家的得分计算Sb也类似，不赘述）：
Sa=abs(X1-0)+abs(X2-X1)+abs(X3-X2)+..+abs(XM-X(M-1))

请计算在以上的规则下，如果两个玩家都想拿到尽量多的分数，用最优策略进行游戏，计算两个人的最终得分。

• 输入：

第一行一个数字N，一半的测试用例（0<N<=50），一半的测试用例（0<N<=1000）

第二行N个数字Ai（0<=Ai<=50）

• 输出：

用空格隔开的两个整数Sa和Sb

• 样例输入：

4
1 2 3 4

• 样例输出：

7 4

• 解题思路：模拟

• 参考程序：

#include<bits/stdc++.h>
using namespace std;

int n, a, k = 1;
deque<int> dq;
int pa = 0, sa = 0, pb = 0, sb = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        dq.push_back(a);
    }
    while (dq.size()) {
        int left = dq.front();
        int right = dq.back();
        if (k % 2) {
            if (abs(left - pa) >= abs(right - pa)) {
                dq.pop_front();
                sa += abs(left - pa);
                pa = left;
            }
            else {
                dq.pop_back();
                sa += abs(right - pa);
                pa = right;
            }
        }
        else {
            if (abs(left - pb) >= abs(right - pb)) {
                dq.pop_front();
                sb += abs(left - pb);
                pb = left;
            }
            else {
                dq.pop_back();
                sb += abs(right - pb);
                pb = right;
            }
        }
        k++;
    }
    printf("%d %d\n", sa, sb);
    return 0;
}

聊天消息排版

• 描述

在网游中，聊天功能是一项非常重要的功能，加上玩家可以打出游戏内置的一些表情图片，因此需要实现一个图文混排系统，如下图所示。
玩家在聊天框输入的是一段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号表情图片的宽度为×19，高度为Y19。

4. 字符（中英文以及标点符号、空格等，下同）与字符之间、字符与表情之间、表情与表情之间都需要额外保留一个PX像素的字间距。每一行第一个字符左边，以及最后一个字符右边不需要保留字间距。

5. 当下一个字符或者表情无法在本行W宽度的像素内完整显示的话，则会强行换到下一行首开始显示。遇到#r的时候也会自动换到下一行开始显示下一个字符或表情。

6. 在一行里出现高度不同的中英文以及表情的时候，需要将其底部对齐。

7. 当一行里没有任何字符或表情，直接被#r换行的时候，这一行的高度算英文字体的高度。

8. 每一行里高度最高的字符或表情，需要同上一行的的底部保留PY像素的行间距。第一行上面与最后一行下面不需要保留行间距。

9. 最后一个字符或表情显示显示以后，它的右下角坐标则为结束坐标。也就是本题需要求解的问题。输入保证最后不会以#r结尾。

• 输入：

每个测试输入包含1个测试用例
第一行为7个正整数w，XE，YE，XC，YC，BX，PY
第二行为40个正整数x0，Y0，X1，Y1…X19，Y19
第三行为长度不超过10000的十六进制编码过的玩家输入，即玩家输入的utf-8编码的数据每个字节的数字转成大写的十六进制表示，不足两位的话前面补0（同c里printf的%x格式化），然后不同字节的十六进制编码表示依次拼接起来。
比如Hello的十六进制编码表示为48656C6C6F。
前两行的各个数字含义如上文描述，其中50< w <10000，0<其他<50。

• 输出：

输出用空格隔开的两个数字，表示结束坐标

• 输入样例：

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
48656C6C6F20776F726C6423E5A4A7E5AEB6E5A5B
D2372E6ACA2E8BF8EE5A4A7E5AEB6E58F82E58AA0
E7BD91E69893E99BB7E781ABE6A0A1E59BADE68B9
BE881982331E7A59DE5A4A7E5AEB6E58F96E5BE97
E5A5BDE68890E7BBA9

• 输出样例：

38 19

• 解题思路：模拟

• 参考程序：

黑客行动

• 描述：

钱老板家的电子保险柜被一个神秘的安保函数y=f(x)保护，每次试图开锁时，系统都会调用安保函数代码输入一个(0,1)之间的浮点数x，如果安保函数能输出正确的y数值则可以打开保险柜，否则就会报警。黑客小军想办法获取到了一份这个安保函数的测试程序，但这个程序并不能在钱老板家的系统上直接运行，必须要重新编码一份新的代码才能使用，请帮助小军实现这个安保函数代码！
你可以在以下的URL下载这份测试程序的可执行文件，压缩包里包含windows、linux和macos三个平台下的可执行程序：
http://guess.zip

• 输入：

一个(0,1)的浮点数，精确到小数点后6位

• 输出：

一个浮点数，精确到小数点后6位

• 输入样例：

0.268044

• 输出样例：

2.681916

• 备注：

本题的判题标准，如果你的代码输出的结果四舍五入到小数点后5位与标准答案四舍五入到小数点后5位一致就算正确

• 解题思路：

• 参考程序：