笔试时间：2023年5月6日 春招实习

第一题

题目：多孔补偿策略

喷墨扫描打印的基本原理是同步控制喷头在x方向滑动、纸张在y方向滑动、以及对应xy坐标的喷墨开关来实现图像像素点的逐点打印。

某喷墨式黑白打印机在使用中，由于喷墨头部分小孔经常堵塞导致打印图像存在一些像素丢失的问题。针对此问题，现在有一种多孔补偿策略，方案描述如下:

1)检测喷墨头堵塞的小孔位置。

2)根据1中检测的堵孔位置，计算一种两次扫描补偿策略，通过第二次扫描对丢失的像素进行打印补偿。该算法需要输出第二次扫描使能的小孔位置、扫描整体平移的小孔数以及平移方向，概念示意如下(x表示堵塞的小孔):

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)如果存在多个方案，先输出向右移动的方案;

样例输入

14

0xE77F

样例输出

2

+2

01100010000000

-2

00000110001000

输入中第二行的十六进制数0xE77F，其中只有前14个bit有效，转换为二进制序列为11100111011111

输出表示有2种补偿方案，分别是右移2个小孔和左移2个小孔，对应的’0‘/’1‘连续字符序列表示所有孔的开关状态.

参考题解

第二题

题目：表达式计算

给定一个字符串形式的表达式，保证每个字符串表达式中仅包含加(+)这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]之间)

第二行:代表一个字符串表达式

输出描述

输出一行，输出表达式结果

注意: 小数最后位如果为0则省略，如 结果250.010则输出250.01，结果250.0则省略为250;同时，如果计算结果为”0250”，也需以最简化形式”250”输出。

样例输入

15

123.45#1+126.53@

样例输出

250.0001

参考题解

将字符串分成 整数和 小数 两个部分，分别找到特殊字符的位置，替换成0，并且计算出特殊字符对应应该添加的值即可。

C++：

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    map<char, int> sc = { {'!', 0}, {'@', 0}, {'#', 0} };
    map<pair<char, char>, int> sr = {
        {{'!', '!'}, 0},
        {{'!', '@'}, 13},
        {{'!', '#'}, 4},
        {{'@', '@'}, 7},
        {{'@', '#'}, 20},
        {{'#', '#'}, 5}
    };

    string a, b;
    size_t plusPos = s.find('+');
    a = s.substr(0, plusPos);
    b = s.substr(plusPos + 1);

    size_t dotPosA = a.find('.');
    size_t dotPosB = b.find('.');
    string az, ax, bz, bx;

    if (dotPosA != string::npos) {
        az = a.substr(0, dotPosA);
        ax = a.substr(dotPosA + 1);
    }
    else {
        az = a;
        ax = "0";
    }

    if (dotPosB != string::npos) {
        bz = b.substr(0, dotPosB);
        bx = b.substr(dotPosB + 1);
    }
    else {
        bz = b;
        bx = "0";
    }

    double add = 0.0;

    if (az.find_first_of("!@#") != string::npos) {
        // Special characters at the beginning, aligning from the end
        for (int i = az.length() - 1; i >= 0; i--) {
            if (sc.find(az[i]) != sc.end()) {
                char cur = az[i];

                if (sr.find(make_pair(cur, bz[i])) != sr.end())
                    add = sr[make_pair(cur, bz[i])] * pow(10, az.length() - i - 1);
                else
                    add = sr[make_pair(bz[i], cur)] * pow(10, az.length() - i - 1);

                for (char c : "!@#") {
                    size_t pos = az.find(c);
                    if (pos != string::npos)
                        az.replace(pos, 1, "0");
                    pos = bz.find(c);
                    if (pos != string::npos)
                        bz.replace(pos, 1, "0");
                }

                break;
            }
        }
    }
    else {
        // Special characters at the end, aligning from the beginning
        for (size_t i = 0; i < ax.length(); i++) {
            if (sc.find(ax[i]) != sc.end()) {
                char cur = ax[i];

                if (sr.find(make_pair(cur, bx[i])) != sr.end())
                    add = sr[make_pair(cur, bx[i])] * pow(10, -i - 1);
                else
                    add = sr[make_pair(bx[i], cur)] * pow(10, -i - 1);

                for (char c : "!@#") {
                    size_t pos = ax.find(c);
                    if (pos != string::npos)
                        ax.replace(pos, 1, "0");
                    pos = bx.find(c);
                    if (pos != string::npos)
                        bx.replace(pos, 1, "0");
                }

                break;
            }
        }
    }

    string o1 = az + "." + ax;