首页 > 代码库 > SCOI2014题解

SCOI2014题解

  SCOI2014由极不靠谱的电子坑爹大学出题。电子坑爹大学打破了多年行规,暴力+NOIP500分居然不能进队。极其逗比的第一天暴力给10分!!还好有些题不是很难,省队爷分数大概在150以上(最高420)

  Day1

  第一题由于YY可以发现,提升[l,r]不如提升[l,n],所以列出一个状态f[i][j]表示现在扫到的值为i时,该位置被提升j次的答案,很明显,该状态有两种转移路径:

  1.f[i][j] = f[k][j] + 1 (k<i) 从比i小的中找到最大的,肯定f[k][j]>=f[k][j-1]

  2.f[i][j] = f[k][j-(k-i)-1] + 1 (k>=i) 从比i大的中找到一个最大的,因为k >= i 所以 k那个位置需要比 i 这个位置少提升(k-i-1)次

  这个方程是O(n^2)的,寻找优化方式

  将状态的二维数组列成一张表,那么第一个方程就是要询问某一行某前缀中的最大值,可以用树状数组维护,而第二个需要询问某一条斜线的某前缀的最大值,将状态变化一下或者写二维树状数组都可以,转状态的方法是因为原状态需转移的格子中两下标和一定,就维护和和第一个和总和的差,就又变成前缀了,每次是log的,代码量1K左右

  第二题的40分做法,存一个排名的树,记录每个节点的father,询问某节点就不断往上走,统计排名,提到第一名和最后一名也很简单是树的基本应用,查询第K也是最基本的,但是100分做法n<=10^8,那么就用每个节点存区间这样搞。。。代码量估计4K+

  第三题是一道防AK的烂题,暴力连样例都过不了你说个毛啊,不是T是WA啊!!题解大概就是可以分区嘛,找规律抵消嘛,然后亦或的前缀和有周期规律嘛,4为周期嘛,谁爱写谁写吧

  Day2

  第一题一眼分数规划,加大一条边流量1的费用为b+d,减小流量1的费用为a-d,然后按这个建图,如果有负环那么沿着这条路走不回减小流量,但是会减小费用,减小多少就是这个环的权值和,然后要让平均每条边的费用最大,那我们就二分这个值,每次找负环的时候给每条边加上这个值,找到就说明还可以变大。用dfs版的SPFA非常快,是一道分数规划的好题。

  第二题直接粘Artanis的题解,其方法完虐标程,给两秒时限全部0.1以内出解

    DAY2 T2:这道题数位DP,时限3秒,但我认为标程方法拙了,要不时限开0.2秒都跑的下来,不信你看看BZOJ 3598跑的最快的速度吧(有人问我是不是打表TAT),名字什么的不要太在意,话说Onion Movie作为高级黑还是推荐没看过的去看一看呢。

    我的算法说来很快很简单- -,数位DP的部分是最基础的水平。先不妨让所有的数都把石子移动到第1位,就可以得到初始总代价Cost,但我们发现这样对于很多数显然不优,我们就可以考虑都多少数从第1位改为第2位会更优,具体优多少,又有多少数从第2位改为第3位会更优……直到从倒数第二位移动到倒数第一位会更优,容易发现这样我仍然可以保证每个数都被我移到了最优情况。然后只用具体考虑有多少数从第i位移到第i+1位更优,优多少,我们可以发现,当一个数从第i位移到第i+1位时代价的变化量等于前i位的和减去i+1位至末位的和,然后就是简单的数位咯O(∩_∩)O!就是直接记录填到第k位的数字之和,如果k<=i就是加,否则就是减,最后的DP[s]就表示有多少个数满足从第i位移动至i+1位能优-s下来。

    复杂度应该是log()^3*k^2,反正属于秒跑的那种,再次吐槽标程一定写拙了,时限给那么大,够我跑⑨⑨次都不止吧……

    考场上秒A,毕竟是水数位DP嘛(∩_∩)

  第三题是计算几何?NO,主要是DP,枚举任意两点连线分开,然后在验证,如果分割线上有多个点,暴力搞搞只有50分,在分割线上作DP。。。不想写了,太麻烦(懒)

  考试时100+10+0+100+30+30拿了270,第六名,算上NOIP400就第八了。还好吧,进了省队。以后还要多多学习,好好学习,听海观涛(误)