Codeforces 补题计划 #397

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个点特判了一下

代码戳...这里