NOIP2018提高组初赛选讲

说实话，这次的初赛比上一次的要简单。
不过还有些变态的题目。

在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望
长度是（）。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5

赛场做法

这题，一眼看下去，我就有点懵了。
后来，又想想有关期望的性质，然后……
画出一条线段，平均分成几份，将所有情况求出来，然后算出期望值。
算了两次，第一次分4份，第二次分6分。
结果都是 $frac{1}{3}$

证明

我在网上翻到一篇有关这个的证明的博客，结果，那博客秀了强大的微积分……
后来，同学告诉我一个比较好理解的证法：
考虑归纳证明
假设现在有一条线段，长度为 $l$ 。
利用分治的思想，在中间取个中点，设为 $M$ 。它将线段等分成两段。
设最终得到的线段的端点分别为 $X$ ， $Y$ 。
根据它们的位置，大体上有两种情况：

$X$ 和 $Y$ 在 $M$ 异侧，则 $overline{XY}=overline{XM}+overline{YM}$ 。显然，在期望情况下，两者皆为 $frac{x}{4}$ ，所以， $overline{XY}=frac{x}{2}$ 。
$X$ 和 $Y$ 在 $M$ 同侧，则 $overline{XY}=frac{x}{6}$

$hereforefrac{frac{x}{2}+frac{x}{6}}{2}=frac{x}{3}$
得证。

假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率
获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的
策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获
得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于
（）。
A. 1 : 2
B. 2 : 1
C. 1 : 3
D. 1 : 1

赛场做法&证明

其实这个比较简单。
设蓝球期望为 $x$ ，则 $x=frac{1+x}{2}$ 。
解得 $x=1$

方程 a*b = (a or b) * (a and b)，在 a,b 都取 [0, 31] 中的整数时，
共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）

赛场做法

第一眼看下去，就觉得这一定是一道神仙题。
果然，还真TM是神仙题。
我先考虑了一个情况：
如果 $a and b$ 和 $a or b$ 中，这两个数由 $a$ 和 $b$ 组成。
那么很显然的是，一定有其中一个是另外一个的子集。
然后乱搞一波，减去重复的，得出 $454$ 。

然后我还觉得有其它的情况，结果想了半天，没有想出来，最后就交了这个答案……
于是莫名切了。

证明

设 $x=a xor b$
$a and b=frac{a+b-x}{2}$
$a or b=frac{a+b+x}{2}$
$herefore left(a and b ight)*left(a or b ight)=frac{left(a+b ight)^2-x^2}{4}$
$herefore a*b=frac{left(a+b ight)^2-x^2}{4}$
$herefore left(a-b ight)^2=x^2$
得证。

然后就没有什么别的特别难的题目了。
总结一下：

期望题分治看看。
位运算有很多规律，有时候异或很有用。