当前位置: 代码迷 >> 编程 >> Codeforces Round #165 (Div. 二)(完全)
  详细解决方案

Codeforces Round #165 (Div. 二)(完全)

热度:1242   发布时间:2013-02-26 00:00:00.0
Codeforces Round #165 (Div. 2)(完全)

这次比赛4分钟结束了,出了1题,诶,B题就卡住,我已经模拟出规律,但傻傻地在写暴力,没有充分简化规律,写出来以后TLE,这导致后面的题目都没看过。 其实这次的C,D很简单,赛后做了做很快就A了,可以了,发挥不够平稳。


B.

我一开始得到的规律:先检查剩下的数组是否升序,若不是升序最前面的一个数一定要更新,然后去掉这个数,重复这一操作直到数组中没有数为止 。

化简这一规律:以上的做法会TLE,我们可以换个角度描述规律,从数组最后的数开始往前扫描,找到第一个出现a[i-1] > a[i]的i,则i之前包括i都要更新,所以答案就是这个i。

code


C.

贪心,纯的数学题。

先按k值排序,小的在前,从大到小枚举i,把箱子i的放到箱子i+1里面, 放不下的箱子i化成箱子i+1。最后能得到一类箱子(k类的箱子, k表长度的指数),因为装它必须用比它大的箱子,所以我们再把这类箱子转化成k+1这类箱子,设其个数为a。 个数a每缩小4倍,k值就加1,所以  ansk = k+1+ceil(log4 (a))

code


D.

可以发现那些xi是无用的数据。根据题意我们可以将任何一个植物移动到任何位置。

要使移动的植物最少,即要不移动的植物最多,不移动的植物是不下降序列,所以题意可以转化为求最长不下降序列len(不移动的植物), 移动的植物则为n-len

code


E.

题目不用求最大流, 而是求每条边的流向,这题是考察网络流的基本规律。

若某图有最大,则有与源点相连的边必然都是流出的,与汇点相连的边必然是流入的,其它所有点流入和流出的流量是相等的。

我们可以根据这一规律来求解。

先求出所有点(除了源点和汇点)的总流量(表示流入的流量的2倍),每次流过该边,更新的时候减去流入流量的2倍。

从源点出发广搜每个点,搜的过程可以确定经过边的流向,当某个点的剩余总流量为0时,表示流入该点的流量边已经都处理完毕,将这点入栈。

特别注意:当 这个点是汇点时不要入栈, 不然会从汇点回流过来,不符合基本规律。

code


  相关解决方案