3
14
2015
0

CH Round #63 - OrzCC杯#2省选热身赛

A,B,C其实本来还想写点儿啥的。。。结果过了之后一看题解和题解想的一样啊。。。那我就没什么说的了。。。简单说一下每道题的做法吧

题意可以上ch看。

A.这是个置换,然后分成了若干个圈。交换的最小次数为n-环的个数。坑点是方案数。对于每一个环分别处理,ans+起来,因为交换两个环的元素一定不会最优。而一个环内任何交换两个都会使一个环拆成两个。这样也是有效的。

B.注意到能吃的n-1次是固定的,而且我们不能从前往后推这次吃不吃。所以我们从后往前,先到1只狮子的情况。然后往回移。一旦发现每次找到最晚的因为进行了捕食活动而丧命的狮子,撤销他到last-1的捕食活动,并且更改这些捕食中丧命的狮子的存活状态。然后继续。

C.这题yy了好久,真是太弱了。。。其实只要倍增d[i]即可,d[i]表示fa[i]向下但不经过i的最短路径,这只要预处理一下就好了。所以需要保留最大,次大,三大这三个值。(LCA的特殊性)还有加上LCA向上最短,x,y向下最短。一条链的情况单独处理。这样就ok了。

D.神题果断不会做。搬运题解:

算出A类液体的总量和B类液体的总量,易知最后只剩总量更多的那种液体,下面我们都假定A类液体多于B类液体。
对A类液体的杯子考虑状态转移,设f(i)为保留第i个杯子,前i个最少剩下多少个杯子。那么f(i)能从f(j)转移过来,须满足从第j+1到第i-1个杯子中B类液体的量大于等于A类液体的量且从第j+1到第i个杯子中A类液体的量大于B类液体的量。(OrzOrzOrz!!!)
  
  其实想到这一步就不难了,接下来就用平衡树优化一下即可。Orz STD写动态开点线段树。

官方题解:http://pan.baidu.com/s/1eQjateM

Category: contest hunter | Tags: | Read Count: 475

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com