2017CodeM初赛A场

发布时间:2017-7-9 7:32:35编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"2017CodeM初赛A场 ",主要涉及到2017CodeM初赛A场 方面的内容,对于2017CodeM初赛A场 感兴趣的同学可以参考一下。

A、最长树链(loj6159)

分析:

对于每个质因数,取出所有是它倍数的点组成一个树,然后找最长路径

每个数操作次数是其质因数的个数

所以总的复杂度不超过O(nlogA)

B、二分图染色(loj6160)

分析:

先转换模型——一个n*n的棋盘上,对于每个格子,可以下黑子,可以下白子,可以不下子,要求同一行同一列颜色相同的棋子最多只有一个

考虑黑白两种颜色不太好考虑,我们去考虑单个颜色

设An表示n*n的棋盘上,放若干个棋子,同一行同一列最多只有一个棋子的方案数

那么有An=ΣC(n,i)*P(n,i) (枚举哪些行放棋子,然后这些行棋子的列做排列)

再考虑两种颜色,我们把两个棋盘拼起来,发现矛盾点就是不能有格子既有黑子又有白子

那么想到容斥:An*An- 至少有一个格子重叠 + 至少有两个格子重叠 - 至少有三个格子重叠……

对于重叠怎么计算呢?一个格子如果重叠了,那么这个格子所在行列都不能放其它棋子了,所以这行这列相当于删去了

所以至少有i个格子重叠可以表示成:C(n,i)*P(n,i)*A(n-i)*A(n-i)

看一下时间复杂度,题目要求在线性时间内完成,求An就成为了一个问题

其实An可以递推求得:An=2nA(n-1)-(n-1)*(n-1)*A(n-2) (留个坑,暂时不太弄懂啥意思?)

C、倒水(loj6161)

分析:

容易发现当大水缸里水的容量介于水杯水之间的时候,一定是无解的

只有在两边才有解

如果在左边,那么答案一定是最小的那个;如果在右边,那么可以二分

D、身体训练(loj6162)

分析:

期望式子推一推就出来了

E、合并回文子串(loj6163)

分析:

考虑dp

dp[i][j][k][l]表示a[i..j]和b[k..l]结合能否成为一个回文串

那么显然一共有4种转移

注意下初值就行了

F、数列互质(loj6164)

分析:

第一想法肯定就是莫队,也容易想到记录当前区间每个数出现次数以及“出现次数”的出现次数

那么时间复杂度就是O(nsqrt(n)+m*MAX*logA)

其中MAX是出现次数的最大值,logA是求gcd的时间

如果MAX是根号级别的就好了,但明显此题中MAX会很大,那么怎么办呢?

我们可以先做一个这样的处理:挑出所有在数组中出现次数>=sqrt(n)的数字,把这些数字用一个桶一刷,求个前缀和,然后遍历所有询问,算这个数字对每个询问的贡献

因为出现次数>=sqrt(n)的数字个数肯定不会超过sqrt(n)个,所以这个的时间复杂度就是O(sqrt(n)*m)

然后对于那些出现次数<sqrt(n)的数字进行莫队,那么MAX就是sqrt(n)了

所以整个复杂度就是O(nsqrt(n)+msqrt(n)+m*sqrt(n)*logA)


上一篇:MongoDB 副本集的原理、搭建、应用
下一篇:如何下载火山小视频-附火山小视频下载youtube视频下载网站 - 刚刚好

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款