Skip to content

华为笔试题2023-05-06

笔试时间:2023-05-06 19:00-21:00

1、多孔补偿策略(100分)

喷墨扫描打印的基本原理是同步控制喷墨头在x方向滑动,纸张在方向滑动以及对应xy坐标的喷墨开关来实现图像像素点的逐点打印。 某喷墨式黑白打印机在使用中,由于喷墨头部分小孔经常堵塞导致打印图像存在些像素丢失的问题。针对此问题,现在有一种多孔补偿策略, 方案描述如下:

  1. 检测喷墨头堵塞的小孔位置。
  2. 根据1中检测的堵孔位置,计算种两次扫描补偿策略,通过第二次扫描对丢失的像素进行打印补偿。该算法需要输出第二次扫描使能的小孔位置、扫描整体平移的小孔数以及平移方向。
  3. 第二次扫描时,如果同一个方向存在多个移动方案都可以满足,则取移动孔位最少的方案。
  4. 注意对于第一次扫描打印过的像素点,第二次扫描时不能重复打印。

解答要求

时间限制:C/C++ 1000ms,其他语言:2000ms 内存限制:C/C++ 256MB,其他语言:512MB

输入

第一行为喷墨头水平排列的小孔个数N, 10<=N<=1024; 第二行为N个bit的序列,用双字节十六进制数表示,如果N超过16,则用多个双字节十六进制表示,它们之间用空格分割。其中0表示该bit对应位置的小孔为堵塞的孔, 1表示正常的孔。有效bit从第一个十六进制的最高位开始计算,序列尾部如果有无效bit则用1填充。

输出

第一行输出可以完成补偿的方案个数,同一个方向只需要给出移位最少的方案。如果无法找到多孔补偿策略或者不需要补偿,输出0。

第二行开始,每两行为一个数据分组,分组中,

  1. 第一行为相对于喷墨头原始位置平移方向和平移的小孔个数,用±X表示,向右为+,向左为-;
  2. 第二行为N个bit的序列,用'0'或'1'的连续字符序列表示,其中'0'表示该bit对应的位置的小孔关闭喷墨,'1'表示打开喷墨。
  3. 如果存在多个方案,先输出向右移动的方案。

样例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

注意:

  1. 保证每个表达式仅包含一个运算符
  2. 保证表达式一定可运算且有数据结果
  3. 保证运算符两边数据有效(不会出现包含两个小数点之类的无效数据)
  4. 表达式内不存在空格
  5. 特殊字符的加法运算符合交换律
  6. 如果表达式中包含特殊字符,则运算中不会出现数字与特殊字符的加法运算
  7. 表达式两边的数据均不以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.4

3、魔幻森林救公主(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,表示每个地图点的路障的状态循环

注意:

  1. 输入数据保证 一定能找到公主。
  2. 输入数据保证 怪物位置与公主位置、王子起始位置不重合。
  3. 输入数据保证 怪物位置、公主位置下,路障的状态循坏一定为'000',即路障一定不会出现。
  4. 输入数据保证 王子起始位置的路障在第一个单位时间不会出现。
  5. 输入数据保证 位置一定合法。

输出

一个数字,代表找到公主花费的最短时间

样例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)