Skip to content

1268: 红伞伞,白杆杆

题目

题目描述

红伞伞,白杆杆,吃完一起躺板板

躺板板,睡棺棺,然后一起埋山山

埋山山,哭喊喊,亲朋都来吃饭饭

吃饭饭,有伞伞,全村一起躺板板

大山里长着两种颜色鲜艳的蘑菇,我们称其为 品种A 和 品种B。

这次采摘的过程非常顺利,小安同学采到了 $n$ 只蘑菇,编号为 $0\sim n-1$。他仔细观察了编号为 $0$ 的蘑菇,并且确定了该蘑菇属于 品种A,是可以食用的品种。但是逐一观察去识别每只蘑菇的品种实在是太麻烦啦,小安并不想全村和他一起躺板板。

幸运的事,小安发现了一台机器。使用这台机器的时候,需要将多个蘑菇按照你自己定义的顺序放入机器中。投币后,机器就开始运作,最终会把所有放进去的蘑菇还给你,并在显示屏上显示一个数字,代表不属于同一种类的相邻蘑菇对的个数。例如,如果按顺序把种类为 $[A, B, B, A]$ 的蘑菇放入机器后,最终机器返回的结果是 $2$。

小安并没有那么多的硬币,并不支持使用太多次机器。此外,机器在使用的过程中也会发生老化,放入机器的蘑菇总数不可以超过 $10^5$。快来 帮帮小安同学,来筹办他的蘑菇宴会吧!

交互描述

你需要实现以下函数。

c++ int count_mushrooms(int n)

  • $n$ 代表了蘑菇的总数,蘑菇的编号为 $0\sim n - 1$。
  • 函数最后需要返回一个整数,表示 品种A 的蘑菇数量。

你可以调用以下函数。

c++ int use_machine(vector<int> x);

  • $x$ 是一个长度介于 $2$ 到 $n$ 之间的数组,代表了你依次放入机器的蘑菇编号
  • $x$ 的元素必须是在 $0$ 到 $n - 1$ 之间(包括 $0$ 和 $n-1$)互不相同的整数。
  • $x$ 的总长度不超过 $10^5$。
  • 这个函数最多被调用 $2\times 10^4$ 次。
  • 函数的返回值表示 $s[x_i] \neq s[x_{i+1}]$ 的数量。

输入格式

以下的描述为对于下发文件中 $main.cpp$ 的输入:

  • 第 $1$ 行:$n$。

  • 第 $2$ 行:$s_0, s_1, s_2, \dots, s_{n-1}$

其中 $n$ 代表了蘑菇的总数,$s_i$ 为一个 $0/1$ 的整数,表示编号为 $i$ 的蘑菇种类,$0$ 代表 $A$ 类。

输出格式

  • 第 $1$ 行:count_mushrooms 的返回值。

  • 第 $2$ 行:调用 use_machine 的次数。

样例输入

样例输入 1

text 3 0 1 1

样例输入 2

text 4 0 1 0 0

样例输出

样例输出 1

考虑以下场景:有 $3$ 个蘑菇,种类依次为 $[A, B, B]$ 。函数 count_mushrooms 用以下方式调用:

c++ count_mushrooms(3)

该函数可以调用 use_machine([0, 1, 2]),在该场景下调用返回 $1$ 。函数接着调用 use_machine([2, 1]),该调用返回 $0$。

此时,已经有足够的信息来推出只有 $1$ 个 A 类蘑菇。所以,函数 count_mushrooms 应该返回 $1$。

样例输出 2

考虑以下场景:有 $4$ 个蘑菇,种类依次为 $[A, B, A, A]$ 。函数 count_mushrooms 用以下方式调用:

c++ count_mushrooms(4)

该函数可以调用 use_machine([0, 2, 1, 3]),该调用返回 $2$。接着调用 use_machine([1, 2]),该调用返回 $1$。

此时,已有足够的信息推出:有 $3$ 个 A 类蘑菇。因此,函数 count_mushrooms 应该返回 $3$。

数据范围

时间限制:2000 ms 空间限制:512 mb

  • $2 \leq n \leq 2\times 10^4$

在所有测试用例中,如果对函数 use_machine 的调用不符合上面所述的要求,或者 count_mushrooms 的返回值不正确,你的解答得分将为 $0$。否则,令 $Q$ 为你对函数 use_machine 的最大调用次数。那么,单一测试点得分将按照以下进行计算:

  • $(\text{0 points})~20000 < Q \leq \infty$
  • $(\text{40 points})~10010 < Q \leq 20000$
  • $(\text{100 points})~904 < Q \leq 10010$
  • $(\frac{904}{Q} \times 100 \text{ points})~226 < Q \leq 904$
  • $(\text{400 points})~ Q \leq 226$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!