美文网首页
Codeforces 补题计划 #397

Codeforces 补题计划 #397

作者: 胡天翼写字的地方 | 来源:发表于2017-02-23 02:24 被阅读0次

    Problem D Artsem and Saunders

    题目戳这里

    题意:有n-n的函数f(x),求构造函数n-m的g(x)和m-n的h(x),满足g(h(x)) = x for all 1-m, and h(g(x)) = f(x) for all 1-n,无解输出-1。

    数学题,构造题,掀桌。。。

    做法:

    1.h(x)=h(g(h(x)))=f(h(x))

    2.所以呢,f(f(x))=f(h(g(x)))=h(g(x))=f(x),f(x)=f(f(x)) 作为验证的标准

    3.m的数目根据f(x)=f(f(x))的数目来确定,依次计入,g(x)反推就可以获得

    代码戳这里


    Problem E Tree Folding

    题目戳这里

    题意:一棵树,如果一个节点的有两个子节点并且长度一样,就可以合并,问经过若干次合并后可否合并成一条链并且问最短长度

    树上乱搞,BFS。。。

    做法,从度为1的节点开始BFS,每一个节点开一个set,BFS删边,更新父节点set,只当每一个节点度为1再入队。BFS之后统计每个set

     1.恰巧size都是1,取最大的

    2.一个size是2,其他是1,取2的两个相加,2是链中间的

    3.其他的可以无解啦

    这就完了?Too young too simple 因为要求最小,把长度为偶数的一直合并合并合并。。。另外把2个点特判了一下

    代码戳...这里

    相关文章

      网友评论

          本文标题:Codeforces 补题计划 #397

          本文链接:https://www.haomeiwen.com/subject/rbevwttx.html