华为 暑期实习 2023.05.06 机试题目与题解

1、多孔补偿策略

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

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

输入

第一行为喷墨头水平排列的小孔个数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. 如果存在多个方室，先输出向右移动的力案。

样例

输入：
14
0xE77F

输出：
2
+2
01100010000000
-2
00000110001000

提示：输入中第二行的十六进制数0xE77F，其中只有前14个bit有效，转换为二进制序列为11100111011111；
输出表示有2种补偿方案，分别是右移2个小孔和左移2个小孔，对应的'0'/'1'连续字符序列表示所有孔的开关状态。

输入：
18
0x677F 0xFFFF

输出：
1
-2
001001100010000000

提示：输入中第二行的十六进制数0x677F OXFFFF，其中只有前18个bit有效，转换为二进制序列为011001110111111111；
输出表示有1种补偿方案，左移2个小孔，对应的'0'/'1'连续字符序列表示所有孔的开关状态。

解答

本题的难点在于处理输入输出，我为了避免麻烦，使用了Python。

先将每个双字节读入，然后通过Python的一些进制转换，直到它成为一个2进制比特串。

这里注意的地方包括但不限于：

1. 如果作为一个整数处理，需要注意前导\(0\)的问题。
2. 字符串对比时会发生偏移，下标处理不好可能越界。
3. 如果原来的字符串没有\(0\)，那么及时退出，因为这时不需要提出方案。

最终，我们先枚举向右的情况，枚举到之后就停止。类似的，我们再枚举向左的情况。本质上，是将整个字符串以\(o\)的偏移量进行处理，并判断每个\(0\)是否被对应的\(1\)所补进去。

代码

n = int(input())
a = input().split()
t = "".join(s[2:] for s in a)
s = bin(int(t, 16))[2:]
s = '0' * (len(t) * 4 - len(s)) + s
s = s[:n]
c = s.count('0')
if c == 0:
    print(0)
    exit()
A = []
for o in range(1, n):
    cnt = 0
    for i in range(o, n):
        if s[i] == '0' and s[i - o] == '1':
            cnt += 1
    if cnt == c:
        t = s[o:] + '1' * o
        t = t.replace('0', '2').replace('1', '0').replace('2', '1')
        A.append((o, t))
        break
for o in range(1, n):
    cnt = 0
    for i in range(n - o):
        if s[i] == '0' and s[i + o] == '1':
            cnt += 1
    if cnt == c:
        t = '1' * o + s[:n - o]
        t = t.replace('0', '2').replace('1', '0').replace('2', '1')
        A.append((-o, t))
        break
print(len(A))
for k, v in A:
    print("{:+}".format(k))
    print(v)

2、表达式计算

给定一个字符串形式的表达式，保证每个字符串表达式中仅包含加(+)这1种运算符，计算并输出表达式结果。 要注意的是，+号两边的数据仅可能包含数字字符、小数点字符与特殊字符，特殊字符包括!@#，这些特殊字符的加法运算有特别的规则:

!+!=0
!+@=13
!+#=4
@+@=7
@+#=20
#+#=5

注意:

1. 保证每个表达式仅包含一个运算符
2. 保证表达式一定可运算且有数据结果
3. 保证运算符两边数据有效(不会出现包含两个小数点之类的无效数据)
4. 表达式内不存在空格
5. 特殊字符的加法运算符合交换律
6. 如果表达式中包含特殊字符，则运算中不会出现数字与特殊字符的加法运算
7. 表达式两边的数据均不以0开头，比如不会出现这样的表达式0250+0110

输入

第一行:代表字符串长度(长度在[1,1000]之间) 第二行:代表一个字符串表达式

输出

输出一行，输出表达式结果 注意：小数最后位如果为0则省略，如结果250.010则输出250.01，结果250.0则省略为250；同时，如果计算结果为"0250"，也需以最简化形式"250"输出

样例

输入：
15
123.45#1+126.53@

输出：
250.0001

提示：#+@=20，即进2位，表达式结果为250.0001

竖式运算如下
123.45#1
126.53@
--------
250.0001

输入：
7
1#3+1#0.4

输出：
253.4

提示：#+#=5，即253.4
竖式运算如下:
1#3
1#0.4
-----
253.4

解答

这又是一道字符串题，我还是使用了Python进行处理。

为了避免后续处理小数点的麻烦，我这里首先将小数点去掉。也就是说，将每个数乘以\(10^m\)，且这个\(m\)足够大，来避免小数对齐麻烦，等输出计算结果时再将小数点补上。

接下来则是常规的计算加法操作，只需要维护好进位值即可。至于如果是两个特殊字符做加法，那么就提前将结果存在字典中。

接下来的问题就是输出计算结果，需要加上小数点。除了题目中需要注意的地方外，还有：

1. 输出结果为"" (一个空字符串，这时补上\(0\))。
2. 输出结果为"."（只包含一个小数点）
3. 输出结果为".xxxxx"，前面的\(0\)忘记了。

代码

input()
s = input()
a = s.split('+')
m = 0
for i in range(len(a)):
    p = a[i].find('.')
    if p != -1:
        m = max(m, len(a[i]) - p - 1)
for i in range(len(a)):
    p = a[i].find('.')
    if p == -1:
        a[i] = a[i] + m * '0'
    else:
        n = len(a[i])
        a[i] = a[i].replace('.', '') + '0' * (m - (n - p - 1))

for i in range(len(a)):
    a[i] = list(a[i][::-1])

x, y = a[0], a[1]
if len(x) > len(y):
    x, y = y, x
x = x + list('0' for i in range(len(y) - len(x)))
n = len(y)
c = 0
a = []
mp = {'!!': 0, '!@': 13, '@!': 13,
      '@@': 7, '!#': 4, '#!': 4,
      '@#': 20, '#@': 20, '##': 5}
for i in range(n):
    if x[i].isdigit():
        w = int(x[i]) + int(y[i]) + c
        c, w = divmod(w, 10)
        a.append(w)
    else:
        w = mp[x[i] + y[i]] + c
        c, w = divmod(w, 10)
        a.append(w)
if c:
    a.append(c)
while len(a) > m and a[-1] == 0:
    a.pop()
if m != 0:
    a = a[:m] + ['.'] + a[m:]
    p = 0
    while p < len(a) and a[p] == 0:
        p += 1
    a = a[p:]
s = "".join(str(x) for x in reversed(a))
if len(s) == 0:
    s = '0'
else:
    if s[0] == '.':
        s = '0' + s
    if s[-1] == '.':
        s = s[:-1]
print(s)

3、魔幻森林救公主

一名王子的未婚妻公主被抓到了魔幻森林中，王子需要去救她，魔幻森林危险重重，除了一些怪物之外，还有时隐时现的路障，工子只能绕过怪物、绕过出现的路障或者等路障消失之后通过。 魔幻森林是一个n*n大小的二维地图，森林中的k只怪物分别在各自的位置中。每个地图点都有一个路障的状态循环，状态循环以3个单位时间作为一个循环，我们用0代表没有路障，用1代表有路障，如'011'表示初始单位时间路障消失，下一个单位时间路障出现，再下一个单位时间路障继续存在。 王子在每个单位时间可以向上、下、左、右某个方向移动一个地图单位，也可以选择不移动，如果王子移动方向上有怪物，或者王子移动目的地在下一个单位时间存在路障，则不可以朝该方向移动，同时如果王子当前位置在下一个单位时间会出现路障，那王子也不可以选择停在原地。 我们需要计算王子到达公主的位置的最短时间。

输入

第一行：地图大小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. 输入数据保证位置一定合法

输出

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

样例

输入：
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)

输入：
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)

解答

这是一道经典的分层图BFS题目。

在不同时刻中，只有\(3\)种不同的状态，而且这\(3\)个状态是循环的。因此我们将整个地图记录成\(3\)块\(s[0],s[1],s[2]\)。如果某个时刻我们处在地图\(s[i]\)，那么我们下一个时刻就处在\(s[(i+1)\%3]\)。也就是说，地图编号也作为其中一个维度参与到我们的BFS中。

这道题的困难点就在于想到将整个图进行分层。如果想好怎么分层，并且理清这里面的状态个数，这道题目就做完了，剩下的则是BFS的模板。

当然，由于我们只要找到公主就行，因此在\(3\)个分层中取到达公主的那个最小时间即可。

代码

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

const int N=104;
int dx[5]={-1,1,0,0,0},dy[5]={0,0,-1,1,0};
int s[3][N][N],n,k,m;
int d[3][N][N];
struct P{
    int f,x,y;
};
int main(){
    memset(d,-1,sizeof(d));
    int x,y;
    scanf("%d %d",&n,&k);
    for(int i=0;i<k;i++){
        scanf("%d %d",&x,&y);
        s[0][x][y]=s[1][x][y]=s[2][x][y]=1;
    }
    scanf("%d %d",&x,&y);
    P ed{0,x,y};
    scanf("%d %d",&x,&y);
    P st{0,x,y};
    string t;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>t;
            if(s[0][i][j]) continue;
            for(int k=0;k<3;k++){
                if(t[k]=='1') s[k][i][j]=1;
            }
        }
    }
    queue<P>q;
    d[st.f][st.x][st.y]=0;
    q.push(st);
    while(!q.empty()){
        P u=q.front();q.pop();
        for(int i=0;i<5;i++){
            int f=(u.f+1)%3,x=u.x+dx[i],y=u.y+dy[i];
            if(x<0||y<0||x>=n||y>=n||s[f][x][y]||d[f][x][y]!=-1) continue;
            d[f][x][y]=d[u.f][u.x][u.y]+1;
            q.push(P{f,x,y});
        }
    }
    int ans=1e9;
    for(int i=0;i<3;i++)
        if(d[i][ed.x][ed.y]!=-1)
            ans=min(ans,d[i][ed.x][ed.y]);
    printf("%d\n",ans);
}