华为笔试题2023-05-06
笔试时间：2023-05-06 19:00-21:00
1、多孔补偿策略（100分）
喷墨扫描打印的基本原理是同步控制喷墨头在x方向滑动，纸张在方向滑动以及对应xy坐标的喷墨开关来实现图像像素点的逐点打印。 某喷墨式黑白打印机在使用中，由于喷墨头部分小孔经常堵塞导致打印图像存在些像素丢失的问题。针对此问题，现在有一种多孔补偿策略， 方案描述如下:
- 检测喷墨头堵塞的小孔位置。
- 根据1中检测的堵孔位置，计算种两次扫描补偿策略，通过第二次扫描对丢失的像素进行打印补偿。该算法需要输出第二次扫描使能的小孔位置、扫描整体平移的小孔数以及平移方向。
- 第二次扫描时，如果同一个方向存在多个移动方案都可以满足，则取移动孔位最少的方案。
- 注意对于第一次扫描打印过的像素点，第二次扫描时不能重复打印。
解答要求
时间限制：C/C++ 1000ms，其他语言：2000ms 内存限制：C/C++ 256MB，其他语言：512MB
输入
第一行为喷墨头水平排列的小孔个数N, 10<=N<=1024； 第二行为N个bit的序列，用双字节十六进制数表示，如果N超过16，则用多个双字节十六进制表示，它们之间用空格分割。其中0表示该bit对应位置的小孔为堵塞的孔， 1表示正常的孔。有效bit从第一个十六进制的最高位开始计算，序列尾部如果有无效bit则用1填充。
输出
第一行输出可以完成补偿的方案个数，同一个方向只需要给出移位最少的方案。如果无法找到多孔补偿策略或者不需要补偿，输出0。
第二行开始，每两行为一个数据分组，分组中，
- 第一行为相对于喷墨头原始位置平移方向和平移的小孔个数，用±X表示，向右为+，向左为-；
- 第二行为N个bit的序列，用'0'或'1'的连续字符序列表示，其中'0'表示该bit对应的位置的小孔关闭喷墨，'1'表示打开喷墨。
- 如果存在多个方案，先输出向右移动的方案。
样例1
输入： 14
0xE77F
输出： 2
+2
01100010000000
-2
00000110001000
解释： 输入中第二行的十六进制数0xE77F，其中只有前14个bit有效，转换为二进制序列为11100111011111；
输出表示有2种补偿方案，分别是右移2个小孔和左移2个小孔，对应的'0'/'1'连续字符序列表示所有孔的开关状态。样例2
输入： 18
0x677F 0xFFFF
输出： 1
-2
001
001100010000000
解释： 输入中第二行的十六进制数0x677F 0xFFFF，其中只有前18个bit有效，转换为二进制序列为011001110111111111；
输出表示有1种补偿方案，左移2个小孔，对应的'0'/'1'连续字符序列表示所有孔的开关状态。提示
输入的合法性由题目保证。
2、表达式计算（200分）
给定一个字符串形式的表达式，保证每个字符串表达式中仅包含加(+)这1种运算符，计算并输出表达式结果。
要注意的是，+号两边的数据可能仅包含数字字符、小数点字符与特殊字符，特殊字符包括!@#，这些特殊字符的加法运算有特别的规则：
!+!=0 !+@=13 !+#=4 @+@=7 @+#=20 #+#=5
注意：
- 保证每个表达式仅包含一个运算符
- 保证表达式一定可运算且有数据结果
- 保证运算符两边数据有效（不会出现包含两个小数点之类的无效数据）
- 表达式内不存在空格
- 特殊字符的加法运算符合交换律
- 如果表达式中包含特殊字符，则运算中不会出现数字与特殊字符的加法运算
- 表达式两边的数据均不以0开头，比如不会出现这样的表达式：0250+0110
解答要求
时间限制：C/C++ 1000ms，其他语言：2000ms 内存限制：C/C++ 256MB，其他语言：512MB
输入
第一行：代表字符串的长度（长度在[1, 1000]之间） 第二行：代表一个字符串表达式
样例1
输入： 15
123.45#1+126.53@
输出： 250.0001
解释： @+#=20，即进2位，表达式结果为250.0001
竖式运算如下：
123.45#1
126.53@
————————
250.0001样例2
输入： 7
1#3+1#0.4
输出： 253.4
解释： #+#=5，即253.4
竖式运算如下：
1#3
1#0.4
————————
253.43、魔幻森林救公主（300分）
一名王子的未婚妻公主被抓到了魔幻森林中，王子需要去救她，森林中除了一些怪物之外，还有时隐时现的路障，王子只能绕过怪物、绕过出现的路障或者等路障消失之后通过。
魔幻森林是一个n*n大小的二维地图，森林中的k只怪物分别在各自的位置中，每个地图点都有一个路障的状态循环，状态循环以3个单位时间作为一个循环，我们用0代表没有路障，用1代表有路障，如011表示初始单位时间路障消失，下一个单位时间路障出现，再下一个单位时间路障继续存在。
王子在每个单位时间可以向上、下、 左、右某个方向移动一个地图单位，也可以选择不移动，如果王子移动方向上有怪物，或者王子移动目的地在下个单位时间存在路障，则不可以朝该方向移动，同时，如果王子当前位置在下一个单位时间会出现路障。 那子也不可以选择停在原地。
我们需要计算王子到达公主的位置的最短时间。
解答要求
时间限制：C/C++ 1000ms，其他语言：2000ms 内存限制：C/C++ 256MB，其他语言：512MB
输入
第一行：地图大小n (2≤n≤100) 第二行：怪物数量k (0<k≤n*n - 2) 第三行：怪物位置，每个位置包含row和col用于代表row行col列，用空格分开，位置之间用空格间隔，三个位置示例: row1 col1 row2 col2 row3 col3，地图左上角位置为0 0，输入保证所有位置合法。 第四行：公主位置和王子起始位置共两个位置，row1 col1 row2 col2 第五行开始的n行：每行n个字符串空格分开，每个字符串长度固定为3，内容固定只有0和1，表示每个地图点的路障的状态循环
注意：
- 输入数据保证 一定能找到公主。
- 输入数据保证 怪物位置与公主位置、王子起始位置不重合。
- 输入数据保证 怪物位置、公主位置下，路障的状态循坏一定为'000'，即路障一定不会出现。
- 输入数据保证 王子起始位置的路障在第一个单位时间不会出现。
- 输入数据保证 位置一定合法。
输出
一个数字，代表找到公主花费的最短时间
样例1
输入： 3
1
1 1
2 2 0 0
000 010 010
000 000 000
101 000 000
输出： 5
解释： 最快路王子的移动顺序：
(0,0) -> (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
另一条路（时间6）：
(0,0) -> (1,0) -> (1,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)样例2
输入： 3
1
1 1
0 2 0 0
010 011 000
000 000 000
000 000 000
输出： 4
解释： 最快路王子的移动顺序：
(0,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2)
另一条路（时间6）：
(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (1,2) -> (0,2)