猜猜我寒假经历了什么?

本来应该打线段树板子的晚上,我的Elementary OS正式“驾崩”,于是我装了很多天系统(以及摸鱼),度过了一个充实的寒假。

寒假的尾巴做了一些题目,就记一下寒假尾巴做过的这些题目吧。

我的答案仓库是Click Me!。根据题号你能找到我的答案,但是我的很多答案有很大的提高和优化空间,欢迎你与我探讨!

0x01. 模板题

这里应该是线段树的模板题,纪念一下,3月再补吧

喜闻乐见的什么都没有。

0x02. 趣题

这个假期也就主要打了Codeforces和AtCoder,所以绝大部分题目都来自于此。

  1. ExpectedMinimumPowerDiv2

    第一题是来自TopCoder的。

    人生中的第一场TopCoder SRM,不得不说作为Codeforce规则的起源,这种规则真的紧张刺激,尤其是看聊天区有人在看我的Solution的时候,无敌紧张。

    看题,给出两个整数$n$和$x$,在$1\sim n$区间中任选$x$个数的一个子集$S$,把这个子集中的最小元素$\min(S)$看作这个集合的代表元素。问这么选择下的$2^S$的数学期望。

    首先数学期望定义是很明确的,出现的值乘以概率,由于这里面的选择随机,也就是等可能性选择,所以期望就是简单的总和除以方案数。

    方案数是十分容易求的,$\binom{n}{x}$,关键问题在于这个总和上。首先考虑这样一个子问题:包含$1$的选择方法有多少?实际上是另一个组合问题:我们确定了$1$,从剩下的$n-1$个元素中选择$x-1$个元素有多少种方法?很简单,就是$\binom{n-1}{x-1}$。接下来来考虑$2$的情况:由于在$1$的情况中,已经包含了$2$的部分情况,这一部分可以求得为$\binom{n-2}{x-2}$。那么$2$的选择方法有$\binom{n-1}{x-1}$,我们拿掉这些情况就有$\binom{n-1}{x-1}-\binom{n-2}{x-2}=\binom{n-2}{x-1}$种情况。以此类推,$3$就有$\binom{n-3}{x-1}$种方法……直到$x$时有$\binom{x-1}{x-1}$种情况为止。那么最终答案就是如下的简单式子:

    $$ \frac{2^1\cdot\binom{n-1}{x-1}+2^2\cdot\binom{n-2}{x-1}+\cdots+2^x\cdot\binom{x-1}{x-1}}{\binom{n}{x}} $$

    一个循环就能计算了。

    上面这个过程还有一种更直观的方法:我们从$1$开始迭代,那么当我们把含$1$的组全部筛选掉之后,$2$的选择时自然不能考虑$1$,所以本来$2$可以从剩下$n-1$个元素中选择,现在$1$也被排除,只剩下$n-2$个元素了,自然是$\binom{n-2}{x-1}$。

    比较好玩的数学问题,从公式推导上有考虑的价值。(然而比赛的时候手动验算算错了,后面写了个demo发现是对了一波就过了。要是不搞这些幺蛾子说不定分数还能更高。

  2. Takahashi’s Information

    一道比较有趣的方程问题。

    给出一个9宫格,如下编号:

    $$\begin{matrix}c_{1,1} & c_{1,2} & c_{1,3} \\ c_{2,1} & c_{2,2} & c_{3,3} \\ c_{3,1} & c_{3,2} & c_{3,3}\end{matrix}$$

    对于每一个数,满足$c_{i,j}=a_i+b_j$。问是否存在这样的六元组$(a_1,a_2,a_3,b_1,b_2,b_3)$,使得上述命题成立。

    这个题一上来很容易拆成$9$个方程的方程组去做,然而这个题实际上难度只是AtCoder Beginners Contest的第三题而已,肯定不会这么大动干戈。

    首先观察一个很基本的事实:任何一个数的得出方法有多个。考虑$c_{1,1}=a_1+b_1, c_{2,1}=a_2+b_1$,马上就能得出$a_2-a_1=c_{2,1}-c_{1,1}$。根据这样的观察,我们可以解出$a_2-a_1,a_3-a_2,a_3-a_1$,那我们几乎可以立即得出$a_2-a_1+a_3-a_2=a_3-a_1$,这样通过两条路就解出了同一个解。假如上述命题成立,这样的等式一定成立,同时还可以对$b_2-b_1+b_3-b_2=b_3-b_1$做出验证,假如这两条都满足,毫无疑问命题成立。

    官方题解则提供了另一种做法:首先根据观察,这样的解一定有无穷多个:考虑解元组$(a_1,a_2,a_3,b_1,b_2,b_3)$:

    $$ (p_1,p_2,p_3,q_1,q_2,q_3) $$

    我们可以对任意的一个偏移量$x$如下构造$(a_1’,a_2’,a_3’,b_1’,b_2’,b_3’)$:

    $$ (p_1+x,p_2+x,p_3+x,q_1-x,q_2-x,q_3-x) $$

    毫无疑问,$(a_1’,a_2’,a_3’,b_1’,b_2’,b_3’)$也是一组可行解,也就是说,这样的解有无穷多个。那也就是说,$\exists x\in\mathbb{Z},a_1=p_1+x=0$。那到这里其实就很简单了,我们直接令$a_1=0$,然后代入解出一个解元组,之后逐条验证即可。

    这一题有趣的地方在于不定方程的处理,我们并不是直接开始高斯消元,而是从一些基本的数学原理入手反向验证,是一道开拓思维的好题目。

  3. Swap Adjacent Elements

    前缀和是区间统计的一大利器。

    给出$n$长度的一个序列$A=a_1,a_2,\cdots,a_n$,同时给出一个$n-1$长度的字符串$S$,这个字符串的含义为:假如$S_i=1$,那么$a_i$可以和$a_{i+1}$任意多次按任意顺序互换,否则不行。问你根据给定的状况能否把这个序列排成上升序的。

    一个排序问题。这里我们如下考虑:假如$a_j=i$,那么意味着$a_j$应该在$a_i$现在的位置上。由于这种交换没有步骤限制,我们可以在行动范围内任意的做出一些临时操作,所以我们的问题简化成了:$a_j$能否来到$i$这个位置。接下来考虑这样的$S=01111000110$,显而易见的是,$a_2\sim a_5$与$a_9\sim a_{10}$是可以无限互换的,那实际上这里就变成了一个很简单的情况:我们只需要考虑$j-i$这段区间内是否是连续的$1$。接下来我们考虑如何获得这个信息:我们把连续的$1$统计成距离,遇到$0$就重新统计,那么上面的$S$转化过后可得如下序列:$0,1,2,3,4,5,0,0,0,1,2,0$,那么我们就很容易可以计算两点间距离,上述问题就转化成$S’_i\ge j-i$的问题。那这样我们只需要扫一遍$S$做一下距离统计,再扫一遍原序列即可,$\mathcal{O}(n)$。

    这一题又一次利用到了前缀和的统计优点,可以说前缀和统计是一个必备的区间统计技巧了,树状数组也是利用了这一个性质。

  4. Vile Grasshoppers

    很有趣的一道题目。

    这有一棵树,树有许多树枝,依次编号为$2\sim y$,同时,在$2\sim p$上各有一只蚂蚱,这些蚂蚱的跳跃能力很强:假如这只蚂蚱在$x$号树枝上,那么它可以跳跃到$2\cdot x, 3\cdot x,\cdots,\lfloor\frac{y}{x}\rfloor\cdot x$上。现在给出$y$和$p$,求最高的,不会被蚂蚱跳到的树枝的编号,如果没有这样的树枝,输出$-1$即可。

    学过埃筛的一定知道这样的一个结论:一个数的两个不同的成对因子一定落在这个数的平方根两侧,也就是说,$\forall p<q, x=p\cdot q$满足$2\le p\le\sqrt{x}<q\le x$。这一题实际上就利用了这一个结论:我们对每一个数$k$来确认如下事实:$\exists x\in[2,p], x^2\le k\land x|k=0$,假如满足,那这个$k$不满足条件。那么我们直接倒序遍历$[p,y]$,来确认是否存在这样的$k$,存在即输出,否则输出$-1$即可。

    这一点观察其实十分的简单:能够整除$x$的因子必定有一半在$[2,\lfloor\sqrt{x}\rfloor]$里面,所以我们检测这里面所有因子即可。更深入思考其实有一个更强的结论:第一个小于等于$x$的质数一定满足要求。所以我们直接使用埃筛的筛法寻找第一个数就可以了。

    来自于质数筛的一个小结论,就这样变成了一道十分有趣的数论题,这也正是数学的魅力。

0x03. 难题

其实这两个月遗留了很多难题,但是刚好遇上开学,所以也没来得及补,这些题就留给下个月吧~