CodeForces Round#359 Div.2 Solution

这场比赛现场我只做出了两题(果然还是太弱)

太久没碰代码导致码力下降以至于C题这种简单题不会做

D题知识迁移能力太弱,明明知道重心合并一定在路上= =却不敢写

QQ图片20160623113150下次在努力。。

A.Free Ice-cream

题意:有个人卖冰激凌,初始有x个,有n个人陆续来到他的店,有可能是进货的,有可能是购买的,如果购买的时候没有足够的冰激凌,那那个人就会不开心,求最后剩余冰激凌数目以及不开心的人的数目。

暴力模拟就行,时间复杂度O(n)

考试的时候没考虑到long long,WA了一次= =

B.Little Robber Girl's Zoo

题意:有一个长为n的序列,每次可以选择一段区间[l,r],使得[l,l+1],[l+2,l+3]....[r-1,r]互相交换,求一种方案使得整个序列单调不下降,方案只要不超过20000步就可行,n\leq100

这个题目特殊在步数的限制,很容易发现题目的描述和插入排序的方法是一样,而总的次数一定不会超过n^{2},所以依旧是直接模拟就行

C.Robbers' watch

题意:给出两个十进制下上限n,m,求有多少个7进制下的数对(x,y)满足十进制下的x<n,十进制下的y<mn,m\leq10^{9}

可以算出10^{9}转为七进制以后顶多剩余7位,而每一位不超过6,所以直接暴力dfs然后判重就可以了。当然枚举也是可以的。时间复杂度O(7!)

妈的纸张为什么我每题都能写的那么烦,智商低是主要原因吧。。。QQ图片20160623113147

D.Kay and Snowflake

题意:给你一颗树,若干次询问查询以p_{i}为根的子树的重心,要求n\leq300000

考虑重心的性质:两棵树合并后的重心一定在两棵树的重心的路径上

然后利用这一点暴力向上爬就可以,时间复杂度O(nlogn),我也不会证明= =

 

发表评论