0%

UOJ #299. 【CTSC2017】游戏

题意

小 R 和小 B 玩了 $n$ 局游戏,第一局小 R 获胜的概率是 $p_1$,对于第 $i(1<i\le n)$ 局,若第 $i-1$ 局小 R 获胜,则小 R 获胜的概率为 $p_i$,否则为 $q_i$

现在已经知道了若干局的胜负情况,求小 R 获胜次数的期望,在 $m$ 次增加或删除已知条件后都输出答案

$n,m\le 2\times 10^5$

后面的游戏结果会影响前面的概率 = =

Read more »

恒等式

$$
[d|n]=\frac{1}{d} \sum_{i=0}^{d-1} \omega_d^{i\times n}
$$

其中 $\omega_d$ 是 $d$ 次单位根

  • 当 $d|n$,右边和式中每一项都为 $1$

  • 当 $d\nmid n$,容易得到右边为 $0$

Read more »

UOJ #345. 【清华集训2017】榕树之心

题目背景

深秋。冷风吹散了最后一丝夏日的暑气,也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧,石桥依旧,榕树虽是历经荣枯更迭,依旧亭亭如盖,只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。

……

“已经快是严冬了,榕树的叶子还没落呢……”

“榕树是常绿树,是看不到明显的落叶季节的……”

“唉……想不到已经七年了呢。榕树还是当年的榕树,你却不是当年的你了……”

“其实又有什么是一成不变的呢,榕树常绿,翠绿树冠的宏观永恒,是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”

“但你看这榕树,日日如此,季季如此,年年如此,仿佛亘古不变般,盘根错节,郁郁葱葱。我在想,或许成为一棵树更好吧,任时间从枝叶间流过,我只守这一片绿荫就好。”

“榕树固然长久,但在这无限的时光里,终归是要湮灭于尘土的。与其像榕树一般,植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了,榕树虽生长缓慢,却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”

“真的吗,榕树在她漫长的一生里,就是这样往外一步步探索的吗?”

“毕竟就算树冠看起来一成不变,榕树也会随着时间周期变化,春天到了自然就是生长的时候了,她也应当做出对应的表现吧……”

“相比于对季节更替做出本能的生长,我倒宁愿相信,榕树有一颗活跃的的,探索的心。”

“其实榕树是有心的,榕树刚刚种下的时候,心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候,心就会向着新枝条的方向移动一点,这样就能更靠近外面的世界了。你看这头顶上的枝条,纵横交错,其实心已经在这枝杈间,移动了数十载了呢……”

“哇,也就是说,这密密麻麻的树杈中的某个地方,藏着这棵榕树的心吗?”

“没错,可是要知道它在哪,就得另花一番功夫了……”

“呀,这时候想想,一株树还是不如一个人好……比如你,要是这样贴上去的话,就能听到跳动的声音呢……”

……

Read more »

AGC005E - Sugigma: The Showdown

题意

有 $n$ 个点,$n-1$ 条红边和 $n-1$ 条蓝边分别把这些点连成一棵树

一开始第一个人在 $x$,第二个人在 $y$,第一个人先手,轮流操作

第一个人走红边,第二个人走蓝边,每次操作可以不动或走一条边。

当两个人相遇的时候游戏结束,第一个人希望最大化总步数,第二个人希望最小化,两个人绝顶聪明

问游戏能否结束,如果可以结束输出最后的步数

Read more »

描述

Maximum-minimums identity

对于一个集合 $S$ 有

$$
\begin{align}
\max(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \min(T) \
\min(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \max(T)
\end{align}
$$

其中 $\max(S)$ 表示集合 $S$ 中的最大元素,$\min(S)$ 表示 $S$ 中的最小元素

证明略

在期望下也成立

$$
\begin{align}
E(\max(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \
E(\min(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\max(T))
\end{align}
$$

不会证

Read more »