水题一道

较难题一道

我们先观察，为n肯定不行，n-1和1一定可以，且如果i可以n-i也一定可以，这样就把无解判断好了。

接着就是构造方法，发现构造的后$\frac n 2$个其实是没有用的，全插到前$\frac {n+1} 2$个的根上即可，

那么重点就在于前$\frac {n+1} 2$个怎么构造。

很容易发先一个菊花图上面加一条边这样对其他的影响最小

那就从小到大枚举i到$\frac {n+1} 2$

如果$S_i$为1，那么就新增加一个点i，将之前做好的根连接到点i上，接着给点i加叶子，直到点数够i，这样子所有$S_i$都可以满足，且其他非连接边都为叶子，删非连接边答案都为n-1。

难题一道

有趣的性质，如果$|X_i|+|Y_i|\leq 2^{k+1}$那么一定存在一个上下左右的方向，使得沿这方向走$2^k$之后$|X_i|+|Y_i|\leq 2^{k}$。

那么我们按位逐步逼近缩小范围即可。

而且由于m步，每步都要走$|X_i|+|Y_i|$的奇偶性必须相同，这是有解的充分必要条件。

我们可以直接设置一个比较大的m，然后逐步逼近，这样所有的步数和为奇数，

所以如果$|X_i|+|Y_i|$为偶数的话开始要强行向某个方向走一步，这样和就变为奇数了。