[CEOI 2022] Homework

Luogu

IDLGP8997

Time1000ms

Memory512MB

DifficultyP5

字符串贪心递归2022CEOI（中欧）树的遍历

这是 Helena 的数学作业中的一道题：我们定义合法表达式如下： - `?` 是合法表达式，这表示一个未知数。 - 如果 $A,B$ 均为合法表达式，那么 $\texttt{min(}A\texttt{,}B\texttt{)}$ 和 $\texttt{max(}A\texttt{,}B\texttt{)}$ 均为合法表达式，这分别表示取左右两边的最大值/最小值。设 `?` 的个数为 $N$，现在给出一个合法表达式，将每一个问号替换为 $1\sim N$ 中的任意一个数并且每一个数不能使用多次，可以得到多少种不同的答案？可怜的 Helena 并不会做，请你帮帮她。 ## Input 仅一行一个字符串表示给出的合法表达式。 ## Output 输出一个整数，表示不同答案的个数。 [samples] ## Note ### 样例 1 解释无论权值如何选择，最后的答案都会是 $\min\{1,2,3,4\}$，也就是 $1$。 ### 样例 2 解释答案为 $4$ 的方案是： `4=max(4,max(3,min(2,1)))`，答案为 $3$ 的方案是 `3=max(3,max(2,min(1,4)))`，可以证明答案不可能为 $1$ 或 $2$。 ### 数据规模与约定对于全部数据，$2\le N\le 10^6$。 | Subtask 编号 | 特殊限制 | 得分 | | :----------: | :--------------------------------------------------------------------------: | :--: | | $1$ | $N\le 9$ | $10$ | | $2$ | $N\le 16$ | $13$ | | $3$ | 对于任意 $\texttt{min(}A\texttt{,}B\texttt{)}$ 与 $\texttt{max(}A\texttt{,}B\texttt{)}$，$A$ 和 $B$ 中有一个为 `?`。 | $13$ | | $4$ | $N\le 10^3$ | $30$ | | $5$ | 无特殊限制 | $34$ |

Samples

Input #1

min(min(?,?),min(?,?))

Output #1

Input #2

max(?,max(?,min(?,?)))

Output #2

Input #3

min(max(?,?),min(?,max(?,?)))

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2022] Homework",
    "description": {
      "content": "这是 Helena 的数学作业中的一道题： 我们定义合法表达式如下： - `?` 是合法表达式，这表示一个未知数。 - 如果 $A,B$ 均为合法表达式，那么 $\\texttt{min(}A\\texttt{,}B\\texttt{)}$ 和 $\\texttt{max(}A\\texttt{,}B\\texttt{)}$ 均为合法表达式，这分别表示取左右两边的最大值/最小值。 设 `?` 的个数为 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8997"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "这是 Helena 的数学作业中的一道题：\n\n我们定义合法表达式如下：\n\n- `?` 是合法表达式，这表示一个未知数。\n- 如果 $A,B$ 均为合法表达式，那么 $\\texttt{min(}A\\texttt{,}B\\texttt{)}$ 和 $\\texttt{max(}A\\texttt{,}B\\texttt{)}$ 均为合法表达式，这分别表示取左右两边的最大值/最小值。\n\n设 `?` 的个数为 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments