这次比赛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