NOIP2015 - 模拟考试Ⅰ

2015.09.21-22

闲扯

首发正式的模拟考试…

Day 1

Coin

[Description]

不超过1000组数据,每组数据给定一个长度为$n(n≤1000)$的序列,两个人分别取数,每次随机取最左边或最右边的数,取完为止。问先手取到的数的总和的期望值是多少。

[Solution]

预处理出f[i][j]:先手长度为i的序列去到第j个元素的可能性,递推式为$$f[i][j]=1-0.5×(f[i-1][j-1]+f[i-1][j]])$$然后就可以实力$O(n)$解决每个询问啦!

[Summary]

拿了30分…写写心路历程…
看到这道题,首先想到的就是$O(n^2)$的区间DP(60分),然后看看数据范围,1000组数据显然TLE啊!然后就想着把DP改到$O(n)$,想了半个小时未果,决定不想正解了,还是暴力走人吧…然后回去想的时候,因为刚才$O(n)$的DP没推出来的经历,我就潜意识认为区间DP也不行- -然后直接30分裸搜了…这还是太鬼了…在考场上的任何思路都是不能放弃的,想到什么最好把它写到纸上,以免自己忘记
然后正解是$O(n^2)$的预处理…告诉我要这么做,递推式都是可以秒推出来的,可是并是没想到要这么做啊…可能是题目做太少经验不足。其实看数据范围很容易想到,要是有$O(n)$的递推,它就会直接给更大的数据了啊!为什么1000的数据要分1000组给呢?多想想应该也会有所发现。所以,有时候数据范围也提供了不得了的思路

Triangle

[Description]

给定一$n(n≤10^5)$个点的无向图,给定不超过$10^5$条边,求这个图上三角形的个数和它补图的三角形个数。

[Hint]

对于每个数据点,两个答案均正确给满分。
某一个答案正确或者两个答案的和正确给60%的分。

[Solution]

我就是得了两个答案和的60%的分的人- -
其实求两个答案的和是一道经典的组合数学题,叫做同色三角形,BZOJ上也有,题号是2916(我不会告诉你我前几天刚做过…)。
这样我们就可以求出两个答案之和了!然而怎么求得某一个图的三角形个数呢?直接枚举!只不过并不是裸暴力…每天边只从小点连到大点,先枚举每个点,然后枚举与这个点相连的另外一个点,再枚举相邻的另外一个点,判断他是否与第一个点相连即可,然后就顺利搜完了- -虽然极端状态可能也是不可过的,但随机数据表现十分好啊!
然后就做完了…

[Summary]

60分还是拿得十分爽…而且我还发现我原来那题理解有问题…不过现在明白了。
然而暴露了两个十分严重的问题啊。第一,这题其实本来可以拿72分的,因为前三个小数据点还是可以暴力枚举啊!不要想着做出60分就已经可以了,这样拿到前三个点的完整分,后面拿步骤分,是完全支持的啊!在考场上一分是一分。第二个问题更严重,我现在似乎已经完全拒绝暴力这种方法…好像“DFS就是暴力,暴力就是TLE”的思想已经根深蒂固,甚至都根本不会考虑这种解法,这是完全不行的啊,(其实就是学的太死了- -),各种姿势都要灵活运用!

AQnum

[Description]

一个数是农数,当且仅当,能所有小于m且整除这个数的所有质数的指数都是奇数。
询问1~n中有几个农数。

[Hint]

$n≤10^{10},m≤10^6 $

[Solution]

考试的时候题意没怎么看懂,表达得太纠结- -肯能是不在状态吧…
以为是什么数论神题…没想到就是一道爆搜优化…
筛出1~m所有质数,枚举指数就可以了qwq
一个优化:当搜到某个质数p,当前的数为x,如果满足$x^2p>n$,就可在质数中二分出一段,使得这些质数的平方乘x都小于等于n,然后答案直接+=这些质数数量+1(指数均为0)即可。
然后就这么奇幻地AC了…

[Summary]

这题暴力都没打…
当时TB说这样做的时候,我还不信- -感觉没优化多少啊,没想到标解的方法一毛一样- -
但是为什么会这么做呢- -这是我一直想不通的问题…
就算我在考场上想到这个优化,也会感觉这并没有优化多少啊,然后就并不会这么打。暴力枚举也不会去想。
但是还是非常匪夷所思…为什么优化了这么多呢…

Day 2

Sum

[Description]

计算:$$\sum_{i=0}^{n}i^t\ mod\ m$$

[Hint]

$n,t≤10^{18},m≤3×10^6$

[Solution]

模m意义下若i,j相等,则it和jt也相等…这样就可以$O(mlogt)$算出答案了…
理论上这样的时间复杂度是可以卡过的,然而多long long的取模运算…常数就比较大了…需要优化。
先预处理每个质数的把er每个p的t次方算出来,对于每个i质因数分解乘起来就可以辣~

[Summary]

拿了80分(没有质因数分解)。
当时在考场上想到这个方法,以为是个水题,而且复杂度在容许范围内,于是就喜大普奔地打完,再对拍了下,发现没错,就走人了~到后面才发现最大的数据要大约5秒才能跑出来啊…想想可能只是常熟比较大就没多想,而且有没有什么可行的常数优化了,于是就放弃了最后的20分。多想想应该能想到的吧!

Light

[Description]

给出不超过$10^6$个“路灯”的灯芯坐标(x,y),其中$|x|≤10^3,0≤y≤10^3$,每个灯芯往下投射一个等腰三角形,角度为2a,给定一段区间[L,R],求最高的高度使得这段区间所有点都能被灯光覆盖到,答案保留到小数点后6位。除路灯个数,所有输入均为实数。

[Solution]

二分高度,在判断是否合法(区间覆盖),复杂度$O(nlog^210^9)$。

[Summary]

考场上听大家嚷嚷什么计算几何…吓得我滚到了地上…
然后想着sigh,我还是打个暴力好了…然后就顺理成章的打了个二分…然后判断…总之都没有什么动力,心想暴力都这么难打,一心想弃疗去看最后一题,打完过了样例就走人了。
然后根本没仔细分析。然而这就是正解啊啊啊!!我为毛没认真打- -调试一下就能AC啊sigh…
以后还是要清醒一点…不要听别人扯淡…

Sequence

[Description]

给定一个长度不超过1500的正整数序列,每次可以合并相邻的两个数,并在这个位置生成两数之和。问最少经过多少次合并才能使得整个序列不降。

[Solution]

DP.
设f[i]为前i个元素的最小合并次数,g[i]为f[i]下的最后一个元素的值,$O(n^2)$转移方程就很好推了…

[Summary]

每次做DP题我内心都是很拒绝的…尤其是脑袋里一直浮荡着“我DP好渣啊”之类的话…
然后就并没有什么信心做…其实自己设计的状态f[i][j]是也表示前i个元素最后一个为j的合并次数,如果多想想朴素$O(n^3)$的递推式大概是能想出来的…为什么要弃疗呢sigh

总结

要是上面所有写得“要是”都变成“还好”会有多好…