[OI笔记]杂题整理1（基础篇~）

算是开学第四周啦，之前的三周大概过了一遍基础图论和数学相关的内容。这篇随笔打算口胡一些近期做感觉比较好的数学相关的题目
因为这段时间主要是看紫书学的，所以其实会有些出自UVA的例题，如果需要题目但是觉得网页慢的话OI in hand这个网站也许会有帮助w
如果打算自己做一遍还是不要看题解的比较好
_(:з」∠)_可能会比较偏向于记笔记的口胡形式…？
不定期更新…

17.9.18

GCD XOR(UVA12716)

题意：给你一个$n(1<=n<=3*10^7)$问有多少对整数$(a,b)$满足$1<=b<=a<=n$且$gcd(a,b)=a xor b$？

题解：注意到如果有$a xor b = c$那么可以推出$a xor c = b$（我也不会很妙的证明…直接考虑某一个二进制位的所有4种情况吧…（其实由于交换律应该是三种？））

那我们干脆枚举$a$和$c$，因为$c$肯定是$a$的约数，所以可以枚举所有$c$然后枚举$c$的倍数$a$（一共是$O(nlogn)$个）这样只要检验所有的二元组$(a,c)$是否有$gcd(a,b)=gcd(a,a xor c)=c$就行啦，时间复杂度$O(nlog^2n)$。

实际上还可以更优：其实有$a-b=c$的…这里说下我自己的想法：首先如果把$a$和$b$写成二进制形式很容易看出有$a-b<=a xor b=c$，因为$c=gcd(a,b)=gcd(b,a-b)<=a-b$于是又得到了$c<=a-b$，然后就得到$a-b=c$啦。

然后根据这一点就可以直接得出$gcd(a,b)=gcd(a,a-c)=c$，于是连gcd都省了复杂度就又少掉一个log啦~

顺便这题询问挺多的可以先预处理出答案

Coupons(UVA10288)

口胡题意：卡池有$n$种卡，可以认为每种卡有无限张，每次抽一张，问集齐所有$n$种卡的期望次数

口胡题解：考虑一个简化版本：如果我已经抽到$k$种卡了，那么抽到一张新卡的概率是多少？$\frac{n-k}{n}$，很显然吧_{记$x=\frac{n-k}{n}$，抽一次没抽到的概率就是$(1-x)$了，抽$p$次没抽到的概率是$(1-x)^p$，也很显然吧}

然后现在来考虑下抽到新卡的期望次数，首先肯定要抽一次，如果没抽到就再抽，脸黑的话可能要一直抽下去…然后期望次数就是$\sum_{i=0}(1-x)^i$，怎么算下去呢？注意到这个和式其实是一个无限的等比数列求和，如果是有限的话呢？比如如果我们求的是$\sum_{i=0}^m(1-x)^i$的话答案就是$\frac{1-(1-x)^{m+1}}{1-(1-x)}$了，注意$(1-x)<1$，于是当$m→+∞$时$(1-x)^{m+1}→0$，然后答案其实就是$\frac{1}{x}=\frac{n}{n-k}$啦…

于是要抽到所有卡的期望就是$\sum_{k=0}^{n-1}\frac{n}{n-k}=n\cdot\sum_{k=0}^{n-1}\frac{1}{n-k}=n\cdot\sum_{k=1}^{n}\frac{1}{k}$啦~w

17.10.9

HEOI2016排序（bzoj4552）

题意：给出$1$到$n$的一个全排列，$m$次操作每次对一段区间升序或降序排序，最后询问一个位置的数字（$n,m<=10^5$）

qwq之前在浴谷秋令营上听了noip老师讲的这题，感觉做法很妙啊~

口胡题解：对每次操作排一次序，最后查位置，时间复杂度$O(nmlogn)$！~

上面一行划掉x

注意到给出的是一个$1$到$n$的全排列，以及这题只要在最后询问一个位置的信息，也就是说这里没有必要把每个位置具体的信息都求出来

我们可以考虑二分这个位置的答案，问题就转换到如何快速$check$一个$ans$了

我们肯定不能去直接排序这个东西，考虑维护每个位置的数字跟$ans$的关系，如果小于我们要$check$的$ans$就标记为$0$，否则就标为$1$~

这样每次排序操作要做的就是统计一下区间里有多少个$1$，然后根据情况进行区间赋值~

很显然上面这这种操作可以用线段树完成，于是时间复杂度就降到了$O(nlog^2n)$~（因为$n,m$范围一样就直接这样写了233）

（听说这个题还可以滋兹多次查询$O(nlogn)$的做…orz）

如果有错还请尽情怼我呀x

巴特西

[OI笔记]杂题整理1（基础篇~）

最新文章

热门文章