CSP-J/S 2020 第二轮认证 入门级

一般来说，一个正整数可以拆分成若干个正整数的和。

例如，$1=1$，$10=1+2+3+4$ 等。对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，$n$ 被分解为了若干个不同的 $2$ 的正整数次幂。注意，一个数 $x$ 能被表示成 $2$ 的正整数次幂，当且仅当 $x$ 能通过正整数个 $2$ 相乘在一起得到。

例如，$10=8+2=2^3+2^1$ 是一个优秀的拆分。但是，$7=4+2+1=2^2+2^1+2^0$ 就不是一个优秀的拆分，因为 $1$ 不是 $2$ 的正整数次幂。

现在，给定正整数 $n$，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

6

4 2

7

-1

126

64 32 16 8 4 2

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 $w\%$，即当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 $p$ 个选手的成绩，则当前计划获奖人数为 $\max(1, \lfloor p \times w \%\rfloor)$，其中 $w$ 是获奖百分比，$\lfloor x \rfloor$ 表示对 $x$ 向下取整，$\max(x,y)$ 表示 $x$ 和 $y$ 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

10 60
200 300 400 500 600 600 0 300 200 100

200 300 400 400 400 500 400 400 300 300

10 30
100 100 600 100 100 100 100 100 100 100

100 100 600 600 600 600 100 100 100 100

小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为 $0$ 或 $1$，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：

1. 与运算：a & b。当且仅当 $a$ 和 $b$ 的值都为 $1$ 时，该表达式的值为 $1$。其余情况该表达式的值为 $0$。
2. 或运算：a | b。当且仅当 $a$ 和 $b$ 的值都为 $0$ 时，该表达式的值为 $0$。其余情况该表达式的值为 $1$。
3. 取反运算：!a。当且仅当 $a$ 的值为 $0$ 时，该表达式的值为 $1$。其余情况该表达式的值为 $0$。

小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。

为了化简对表达式的处理，我们有如下约定：

表达式将采用后缀表达式的方式输入。

后缀表达式的定义如下：

1. 如果 $E$ 是一个操作数，则 $E$ 的后缀表达式是它本身。
2. 如果 $E$ 是 $E_1~\texttt{op}~E_2$ 形式的表达式，其中 $\texttt{op}$ 是任何二元操作符，且优先级不高于 $E_1$ 、$E_2$ 中括号外的操作符，则 $E$ 的后缀式为 $E_1' E_2' \texttt{op}$，其中 $E_1'$ 、$E_2'$ 分别为 $E_1$、$E_2$ 的后缀式。
3. 如果 $E$ 是 $E_1$ 形式的表达式，则 $E_1$ 的后缀式就是 $E$ 的后缀式。

同时为了方便，输入中：

1. 与运算符（&）、或运算符（|）、取反运算符（!）的左右均有一个空格，但表达式末尾没有空格。
2. 操作数由小写字母 $x$ 与一个正整数拼接而成，正整数表示这个变量的下标。例如：x10，表示下标为 $10$ 的变量 $x_{10}$。数据保证每个变量在表达式中出现恰好一次。

x1 x2 & x3 |
3
1 0 1
3
1
2
3

1
1
0

x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

0
1
1

设有 $n \times m$ 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

9

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

-10