题面描述:

塔子哥在玩积木塔游戏，按照特定规则添加标有正整数的积木块。当他添加新的积木时，如果新积木的数字与塔顶积木的数字相同，他会取下这两块积木，将它们的数字相加后乘以二，然后放回一块新积木；如果塔顶的数字等于下面连续几块积木的和，他也会进行相同操作。若两个条件都不满足，他就将新积木简单放在塔顶。最终，请输出游戏结束后积木塔上从顶到底的数字序列。

思路

这题是一道模拟题，抽象一下题意，每次元素入栈时，判断一下：

• 如果栈顶元素 $x$ 等于第二个元素，则删除最顶上的两个元素，并将 $2 * x$ 入栈。

• 如果栈顶元素 $x$ 等于前面若干元素之和，则删除前面若干的元素，并将 $2 * x$ 入栈。

• 否则不进行操作

由于数据范围只有 1000，每次插入一个新的 $x$ 时，可以暴力判断一下当前是否满足题目条件，并模拟即可，具体操作可看代码。

题解

这道题目是一个模拟题，要求我们根据特定规则处理一个整数序列。具体规则如下：

1. 条件一：如果栈顶元素$x$等于当前添加的元素$y$，则删除栈顶的两个元素，并将$2*x$入栈。
2. 条件二：如果栈顶元素$x$等于栈中若干元素的和，删除栈中的若干元素，并将$2*x$入栈。
3. 默认情况：如果上述条件都不满足，则直接将元素$y$放入栈中。

在实现上，我们使用一个动态数组（vector）来模拟栈的操作。对于每个新的元素，我们需要判断是否满足上述条件，利用累加和和栈的结构来进行操作。由于数据量限制在 1000 以内，可以使用暴力的方法逐一检查。

AC代码

cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> a; // 用于存储输入的数字
    int val;
    
    // 从输入中读取数字，直到没有输入
    while (cin >> val) {
        a.push_back(val);
    }

    vector<int> stack; // 用于模拟栈操作
    for (int x : a) { // 遍历每个输入的数字
        bool ok = true; // 标志变量，用于判断条件是否满足
        
        // 当栈不为空且当前栈中元素的和大于等于 x 时，进行循环
        while (ok && accumulate(stack.begin(), stack.end(), 0) >= x) {
            int s = 0; // 用于累加栈中的元素
            int cnt = 0; // 计数器，记录参与累加的元素个数
            
            // 从栈顶向下遍历，检查当前元素和
            for (int i = stack.size() - 1; i >= 0; --i) {
                s += stack[i]; // 累加栈中元素
                cnt++; // 增加计数
                
                // 如果累加和等于 x
                if (s == x) {
                    // 删除栈顶的 cnt 个元素，并将 2 * x 入栈
                    for (int j = 0; j < cnt; ++j) {
                        x += stack.back(); // 将栈顶元素加到 x 上
                        stack.pop_back(); // 移除栈顶元素
                    }
                    break; // 结束当前循环
                } 
                // 如果累加和超过 x，则不满足条件
                else if (s > x) {
                    ok = false; // 设置标志为 false，退出循环
                    break;
                }
            }
        }
        stack.push_back(x); // 将当前元素 x 放入栈中
    }

    // 从栈顶到栈底输出结果
    for (int i = stack.size() - 1; i >= 0; --i) {
        cout << stack[i] << " "; // 输出栈中的每个元素
    }
    cout << endl; // 输出换行符

    return 0; // 程序结束
}

java

import java.util.*;

class Main {
    public static void main(String args[]) {
        // 创建一个 Scanner 对象用于读取输入
        Scanner s = new Scanner(System.in);
        
        // 读取一行输入，并将其拆分成字符串数组，然后转换为长整型数组
        long[] arr = Arrays.stream(s.nextLine().split(" ")).mapToLong(Long::valueOf).toArray();
        
        // 初始化一个栈，用于存储当前的积木块
        long[] stack = new long[arr.length];
        
        // 当前栈的有效元素数量
        int cur = 1;
        
        // 将第一个输入元素放入栈中
        stack[0] = arr[0];
        
        // 从第二个元素开始处理
        for (int i = 1; i < arr.length; ) {
            // 从栈顶开始向下遍历
            int j = cur - 1;
            long sum = 0; // 初始化当前和
            
            // 检查栈中元素的和是否小于等于当前元素
            while (j >= 0 && sum + stack[j] <= arr[i]) {
                sum += stack[j]; // 累加栈中的元素
                j--; // 向下移动到下一个元素
            }
            
            // 如果累加和等于当前元素
            if (sum == arr[i]) {
                // 将当前元素更新为两倍的累加和
                arr[i] = sum << 1; // 左移一位相当于乘以 2
                // cur = j + 2; // 不再使用的行
                cur = j + 1; // 更新当前有效元素的数量
            } else {
                // 如果不满足条件，则将当前元素入栈
                stack[cur++] = arr[i]; // 将当前元素放入栈中并更新 cur
                i++; // 处理下一个输入元素
            }
        }
        
        // 定义字符串数组，用于格式化输出
        String[] str = {"%d ", "%d"};
        
        // 从栈顶到栈底输出最终的结果
        for (int i = cur - 1; i >= 0; --i) {
            // 输出格式化字符串，最后一个元素输出后换行
            System.out.printf(i != 0 ? str[0] : str[1], stack[i]);
        }
    }
}

python

# 读取输入并将其转换为整数列表
a = list(map(int, input().split()))

# 初始化一个空列表作为栈
st = []

# 遍历输入的每个数字
for x in a:
    flg = True  # 标志变量，用于控制内部循环
    # 当栈的和大于等于当前元素 x 时，继续循环
    while flg and sum(st[:]) >= x:
        s = 0  # 初始化累加和
        cnt = 0  # 初始化计数器
        
        # 反向遍历栈中的元素
        for t in st[::-1]:
            s += t  # 累加栈中的元素
            cnt += 1  # 增加计数器
            
            # 如果累加和等于当前元素 x
            if s == x:
                # 从栈中弹出 cnt 个元素并将其累加到 x 上
                for i in range(cnt):
                    x += st.pop()
                break  # 退出当前循环
            # 如果累加和超过了当前元素 x
            elif s > x:
                flg = False  # 设置标志为 False，退出循环
                break 
    
    # 将当前元素 x 添加到栈中
    st.append(x)

# 输出结果，从栈顶到栈底
print(*st[::-1])

javascript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
void (async function () {
    const input = await readline();
    const arr = input.split(' ').map(BigInt); // 使用BigInt处理大整数 
    
    const stack = new Array(arr.length).fill(0n); 
    let cur = 1;
    stack[0] = arr[0];
    
    for (let i = 1; i < arr.length;  ) {
        let j = cur - 1;
        let sum = 0n;
        
        // 逆向遍历栈计算可合并区间 
        while (j >= 0 && sum + stack[j] <= arr[i]) {
            sum += stack[j];
            j--;
        }
        
        if (sum === arr[i]) {
            arr[i] = sum << 1n; // 位运算实现乘2 
            cur = j + 1;        // 截断栈顶 
        } else {
            stack[cur++] = arr[i];
            i++;
        }
    }
    
    // 构造输出结果 
    const output = [];
    for (let i = cur - 1; i >= 0; i--) {
        output.push(stack[i].toString()); 
    }
    console.log(output.join(' '));
    
    rl.close(); 
})();

问题描述

小明在玩积木塔游戏。他有一系列的积木块，每块上标有一个正整数。他按照特定的规则堆积这些积木块：每次小明添加一块新的积木时，如果这块积木上的数字与塔顶的积木数字相同，他会取下两块积木，将上面的数字相加后，然后放回一块新的积木。此外，如果塔顶的积木数字等于下面连续几块积木数字之和，他同样会取下这些积木，进行相同的操作。如果这两个条件都不符合，他就会简单地将新的积木放在塔顶。现在，小明按照一定顺序添加了一系列的积木，请你计算游戏结束后积木塔各块上的数字。

输入格式

第一行输入为一个由空格分隔的正整数序列，表示小明按顺序添加到积木塔中的积木块上的数字。

输出格式

输出为一个由空格分隔的正整数序列，从左到右依次表示游戏结束后从塔顶到塔底的积木块上的数字。

样例输入

55 66 121 5 5

样例输出

10 242

评测数据与规模

• 每个正整数的范围为 $1$ 到 $2^{31}-1$。
• 正整数的个数范围为 $1$ 到 $1000$。