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个点特判了一下
网友评论