解题思路

设当前整数为 $x$ ，每次操作后要输出 $x$ 的二进制中 $1$ 的个数。

如果每次真的去维护大整数，再重新统计二进制里 $1$ 的数量，那么在数据范围 $n \le 10^6$ 下显然不合适。因此这里使用的核心算法是：用二进制的“连续段”来模拟，也就是维护二进制表示的运行长度编码（ $RLE$ ）。

P4690.第3题-二进制操作与1的个数

1000ms

Difficulty: 7

所属公司 : 阿里

算法与标签>模拟

给定一个初始值为 $0$ 的整数 $x$ 和一个仅由字符 $+、-、*、/$ 组成的字符串 $s$ ，表示一系列操作。

依次对 $s$ 中的每个字符执行以下操作：

若字符为 $+$ ，将 $x$ 增加 $1$ ；若字符为-，将 $x$ 减少 $1$ ，但保持 $x≥0$ ；

若字符为*，将 $x$ 乘以 $2$ ；若字符为 $/$ ，将x除以 $2$ 并向下取整。每次操作后，输出 $x$ 的二进制表示中1的个数。

第一行输入一个整数 $n (1 ≤ n ≤ 10^6)$ ，表示操作次数；

第二行输入一个长度为n的字符串 $s$ ，仅包含字符 $+，-，*，/，$ 表示操作序列。

输出 $n$ 行，每行输出一个整数，表示对应操作执行后 $x$ 的二进制表示中 $1$ 的个数。

输入

7
++-*-//

输出

输入

预期输出（选填）