0%

Codeforces 1090H. Linearization

题意

定义一个长度为 \(n(n=2^k,k\in N)\) 的 01 串 \(s\)(从 0 开始标号)是线性的,当且仅当存在整数 \(x\) 和 二进制数位 \(b\),使得 \(\forall i\in [0,n),s_i=P(i~{\rm and}~x)~{\rm xor}~b\),其中 \(P(a)\) 表示 \(a\) 的二进制表示中 \(1\) 的数量的奇偶性

定义一个 01 串的线性化难度为,进行最少的取反一个区间的操作,使之成为线性的操作次数

给定一个长度为 \(m\) 的 01 串 \(t\)\(q\) 次询问指定一个子串,要求计算其线性化难度

\(m,q\le 2\times 10^5\)

Read more »

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 »