有 组数据,每组数据有一个长度为 的 字符串,求构造一个 个结点的树满足每个结点的度数的奇偶性符合 串 ,且将这些点依次排列到一个环上,任意两条边不在非端点处相交。
。
VP 的时候想到了一大堆奇奇怪怪的做法,有些是对的,但是都否定了。
首先发现因为每条边都会贡献两个度数,又有 条边,所以若度数总和是奇数那么就不行。
由于需要构成一棵树,而树的叶子节点一定只有一个度,所以若度数全都是偶数也不行。
对于其它情况,考虑构造解:
-
若度数都是奇数,那么此时 必定为偶数,把 当作根,其它点向 连边组成菊花图即可;
-
否则考虑构造一些链,把整个序列看作一个环,把环断成 段 这样的序列,每一段序列都依次串起来,这样我们就获得了一些”趴在边上“的链。考虑如何把这些链连起来,显然由于度数是偶数, 一定是也偶数,所以拿一条链的开头当作根把这些链接上即可。