NOIP2015 - 模拟考试Ⅰ

首发正式的模拟考试…

Day 1

Coin

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

  • [Solution]
    预处理出f[i][j]f[i][j]：先手长度为i的序列去到第j个元素的可能性，递推式为

f[i][j]=1−0.5×(f[i−1][j−1]+f[i−1][j]])f[i][j]=1−0.5×(f[i−1][j−1]+f[i−1][j]])

然后就可以实力O(n)O(n)解决每个询问啦！

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

Triangle

  • [Description]
    给定一n(n≤105)n(n≤10^5)个点的无向图，给定不超过10510^5条边，求这个图上三角形的个数和它补图的三角形个数。

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

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

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

AQnum

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

  • [Hint]
    n≤1010,m≤106n≤10^{10},m≤10^6

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

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

Day 2

Sum

  • [Description]
    计算：

∑i=0nit mod m\sum_{i=0}^ni^t\ mod\ m

  • [Hint]
    n,t≤1018,m≤3×106n,t≤10^{18},m≤3×10^6

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

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

Light

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

  • [Solution]
    二分高度，在判断是否合法（区间覆盖），复杂度O(n⋅log2109)O(n\cdot log_210^9)。

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

Sequence

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

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

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

总结

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

Comment