Manthan, Codefest 16

2016年3月6日96313

A. Ebony and Ivory

给定a,b,c

求一组整数解x,y使得x * a + y * b = c

题解

数据范围很小暴力枚举x

B. A Trivial Problem

求n!有多少个0

题解

暴力求n!被多少个2和5整除

C. Spy Syndrome 2

给定长为(n <= 10000)的主串,给(m <= 100000)个长不超过1000的子串,总长不超过1000000

求一个主串由 子串的反串 拼出的解法

题解

求每个子串的哈希值,主串每位枚举串长 <= 1000,求出哈希值和子串进行匹配转移

D. Fibonacci-ish

给一个长为( n <= 1000 )的数列,数字 <= 10^9 问最多能选出多少个数组成广义斐波那契数列

题解

枚举选出两个作为斐波那契数列的开头,暴力递推,由于斐波那契数列的增长速度很快,几十项就会超过10 ^ 9

F. The Chocolate Spree

在树上选两条不相交的链,使链上的点权和最大

预处理

best[x]表示x子树内的最长链

down[x]表示子树内从x出发的最长链

up[x]表示从x出发,终点在x子树外的最长链

最终一定存在点,使得最优解的一条链 a 经过它,另一条链 b 在它的一个儿子的子树内且链 a 不经过这个儿子

枚举这个儿子y,答案就是best[y]加上链 a

链 a 有若干种情况,记录down的前后缀最大/次大值讨论一下即可

 

  • 2016年3月26日 下午3:37 回复

    黄学长,你发Saber的图干甚,脑子没坑啊!

    #1  
    • ...2016年3月26日 下午4:10 回复

      请说话得体

      #11
    • 岁月是朵两生花2016年3月26日 下午4:31 回复

      图在哪里啊=-=
      请注意您的用词啊=-=

      #11
    • 大水车2016年3月27日 下午12:46 回复

      起码人家有脑子,可惜你没有

      #11
    • hzwer2016年4月11日 下午8:55 回复
      admin

      0w0 这位同学我只看到你头像有Saber。。。

      #11
      • 万千勇2016年4月11日 下午9:47 回复

        活捉。。。高三了竟然还能看到。
        话说图片到底放在哪呢,看见喵帕斯就戳进来了然而并没有,如何做到的?

        #12
        • 万千勇2016年4月11日 下午11:00 回复

          来晚了,又匿了TAT

          #13
          • hzwer2016年4月11日 下午11:23
            admin

            QwQ

            #14
          • 万千勇2016年4月11日 下午11:35

            每次看到都不一样诶,好神奇

            #14
        • hzwer2016年4月11日 下午11:23 回复
          admin

          你是说搜索引擎收录的时候会抓取页面的图片么。?
          我没看到过哪有喵帕斯啊

          #13
          • 万千勇2016年4月11日 下午11:36

            指的就是首页每篇博文的配图啊

            #14
          • 万千勇2016年4月11日 下午11:56

            找到了
            图包2014-12-05_10-13-41&2014-12-05_10-14-06
            随机显示?

            #14
          • 万千勇2016年4月11日 下午11:58

            另外图就THx了(^∀^)

            #14