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

第一题

题目：栈数据合并

向一个空栈压入正整数，每当压入一个整数时，执行以下规则(设: 栈顶至栈底整数依次编号为n1、n2...nx， n1为最新压入的整数)

1.如果n1=n2，则n1、n2全部出栈，压入新数据m(m=2*n1)

2.如果n1=n2+...+ny(y的范围为[3,x]) ，则n1、n2...ny全部出栈，压入新数据m(m=2*n1)。

3.如果上述规则都不满足，则不做操作

如: 依次向栈压入6、1、2、3，当压入2时，栈顶至栈底依次为[2、1.6];当压入3时，3=2+1，3、2、1全部出栈，重新入栈整数6，此时栈顶至栈底依次为[6、6]; 6=6，两个6全部出栈，压入12，最终栈中只剩个元素12。

向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms

内存限制: C/C++ 256MB,其他语言: 512MB

输入描述

使用单个空格隔开的正整数的字符串，如"5 6 7 8”，左边的数字先入栈。

正整数大小为[1,2^31-1]。

正整数个数为[1,1000]。

输出描述

最终栈中存留的元素值，元素值使用单个空格隔开，如”8 7 6 5”，从左至右依次为栈顶至栈底的数字。

样例输入

10 20 50 80 1 1

样例输出

2 160

解释: 向栈压入80时，10+20+50=80，数据合并后入栈160，压入两个1时，合并为2，最终栈顶至栈底的数字为2和160。

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

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

参考题解

用栈模拟即可，注意每次压栈都要进行检查。

C++：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    vector<int> arr;
    int num;
    while (cin >> num) {
        arr.push_back(num);
    }

    stack<int> st;

    for (int i = 0; i < arr.size(); i++) {
        st.push(arr[i]);
        while (st.size() > 1 && st.top() == st.top() - 1) {
            int num = st.top();
            st.pop();
            st.pop();
            st.push(2 * num);
        }
        while (st.size() >= 3) {
            int sum = 0;
            stack<int> temp;
            for (int j = 0; j < st.size() - 1; j++) {
                sum += st.top();
                temp.push(st.top());
                st.pop();
                if (sum >= st.top()) {
                    if (sum == st.top()) {
                        for (int k = 0; k < j + 2; k++) {
                            temp.pop();
                        }
                        st.push(2 * sum);
                        while (!temp.empty()) {
                            st.push(temp.top());
                            temp.pop();
                        }
                    }
                    break;
                }
            }
        }
    }

    while (!st.empty()) {
        if (st.size() > 1) {
            cout << st.top() << " ";
            st.pop();
        } else {
            cout << st.top() << endl;
            st.pop();
        }
    }

    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> arr = new ArrayList<>();
        
        while (scanner.hasNextInt()) {
            arr.add(scanner.nextInt());
        }

        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < arr.size(); i++) {
            st.push(arr.get(i));
            solve(st);
        }

        while (!st.isEmpty()) {
            if (st.size() > 1) {
                System.out.print(st.pop() + " ");
            } else {
                System.out.println(st.pop());
            }
        }
    }

    static void solve(Stack<Integer> st) {
        while (st.size() > 1 && st.peek().equals(st.elementAt(st.size() - 2))) {
            int num = st.pop();
            st.pop();
            st.push(2 * num);
        }
        
        while (st.size() >= 3) {
            int sum = 0;
            Stack<Integer> temp = new Stack<>();
            
            for (int i = 0; i < st.size() - 1; i++) {
                sum += st.peek();
                temp.push(st.pop());
                
                if (sum >= st.peek()) {
                    if (sum == st.peek()) {
                        for (int j = 0; j < i + 2; j++) {
                            temp.pop();
                        }
                        st.push(2 * sum);
                        
                        while (!temp.isEmpty()) {
                            st.push(temp.pop());
                        }
                    }
                    break;
                }
            }
        }
    }
}

Python：

arr = [int(c) for c in input().split(" ")]

st = []

def solve():
    if len(st) > 1 and st[-1] == st[-2]:
        num = st.pop()
        st.pop()
        st.append(2 * num)
        solve()
    elif len(st) >= 3:
        sum_ = 0
        for i in range(len(st) - 1):
            sum_ += st[len(st) - i - 2]
            if sum_ >= st[-1]:
                if sum_ == st[-1]:
                    for _ in range(i+2): st.pop()
                    st.append(2 * sum_)
                    solve()
                break

for i in arr:
    st.append(i)
    solve()


while st:
    if len(st) > 1: print(st.pop(), end=" ")
    else: print(st.pop())

第二题

题目：寻找密码串

敌占区地下工作者冒死提供了加密后的字符串，需要你根据预先定好的方式进行解密，得到其中真正的密码。加密后字符串M是由0~9这10个数字组成的字符串，你手上是一个给定秘钥数字N和一个运算符k (加减乘中的一个)，需要按如下规则找出直正的密码。

1.截取M中的某一段数字x，和数字N进行k运算 (x k N)，如果结果是一个所有位数相同的数，则这段数字有可能就是所找密码，例如x为222，N为3，k为"，则计算结果是222*3=666，满足要求，x是所寻目标彩码串之一。

2.如果存在满足第1点的多种情况，则以计算结果最大的为准;

3.如果没有找到符合条件的密码串，则输出-1，表示密码串不存在

3.M的长度<100，N为正整数，且N<=9999999999，3<=所找密码长度<=12。k为+或-或中的一种，不考虑除法。为避免数据过于庞大，约定在乘法场景下，乘数最大为3位数。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms

内存限制: C/C++ 256MB,其他语言: 512MB

输入描述

提供加密后字符串M，秘钥数字N和运算符k，例如：

(加密字符串M) 748443217098

(秘钥数字N) 123

(运算符k) +

输出描述

满足计算结果所有位数相同，且计算结果最大的值。

例如:上述例子截取44321，和123相加，则为44321+123=44444，结果所有位的数字字符相同，包括个位数、十位数、百位数、千位数和万位数都是同一个数字字符4，且其值最大。

(目标字符串) 44321

样例输入

示例1:

6833023887793076998810418710

2211

-

示例2:

68846787793076946788418710

4210

+

样例输出

示例1:

9988

解释：通过计算，8877-2211=6666，而9988-2211=7777，因为7777>6666，则目标密码串为9988。

示例2:

884678

解释: 通过计算，符合条件有两个，884678+4210 = 888888，4678+4210=8888。则目标密码串为884678。

参考题解

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

C++：

#include <iostream>
#include <stri