题目
点这里看题目。
分析
对于这种构造题目，我们首先考虑边界情况。比如，我们可以计算不平衡点的上界，并且找到对应的构造方案，然后构造出来。
这个上界可以如下构造：
o
/
o o
/
o o
/
...
/
o
/
o o
也就是，首先构造一条链，长度为 (frac{n+1}{2}) （显然，有解的 (n) 一定是奇数）。接着，我们给链上的除任一端点以外的所有点加上一个儿子。这样我们就可以得到一棵有 (frac{n-3}{2}) 个不平衡点的树。可以发现这就是构造的上界。
现在，我们称 (T_k) 为长成这个样子的树：
1
/
2 o
/
3 o
/
... o
/
k
o
此时只要节点 (k) 的左儿子大小大于 1 ，我们就可以获得 (k) 个不平衡点的贡献（否则也会有 (k-1) 个的贡献）。可以发现我们刚刚构造的上界就是这样构造出来的。
接着考虑不平衡点的下界。显然，如果 (n=2^k-1(k>0)) ，那么它就可以构造出没有不平衡点的树。否则，最少只能构造出有一个不平衡点的树。这两种情况的构造方法是一样的，都是构造成完全二叉树的样子。
将两个极端结合起来——如果 (k<2) ，我们可以判断并构造。否则，我们可以首先构造出 (T_{k-1}) 。然后构造出带来 1 的贡献的树，并且接到 (T_{k-1}) 下面去。
如果 (n-2(k-1)) 不能构成满二叉树，我们就可以直接构造成完全二叉树并且接到 (T_{k-1}) 下面去。
否则，考虑丢掉满二叉树的几个点，使得它不满，然后接到 (T_{k-1}) 下面。接着，我们只需要给提出来的点找位置就好了。
不难想到构造 (n-2) 大小的树，接到 (T_{k-1}) 下面，然后将 2 个点接到 1 的右儿子上。此时，只要 1 的左儿子足够大， 1 还是可以贡献一个不平衡点。
这样的构造方法只会有一个反例：n=9,k=2 。而经过枚举可以发现它是真的无解。
于是问题就解决了，时间复杂度是 (O(n)) 。
小结：
- 有数量限制的构造题中，考虑数量的上下界是有用的思考方向。虽然可能跟最终构造方法没有关系，但是可以给你提供构造方法与思考方向。
代码
#include <cstdio>
const int MAXN = 1e5 + 5, MAXLOG = 50;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &x, _T &y )
{
_T t = x; x = y, y = t;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
int ance[MAXN];
int N, M, K;
int Lowbit( const int x ) { return x & ( -x ); }
bool Chk( int x ) { return x - Lowbit( x ) == 0; }
int main()
{
read( N ), read( K );
int lim = MAX( ( N - 3 ) / 2, 0 );
if( K > lim ) return puts( "NO" ), 0;
if( N % 2 == 0 ) return puts( "NO" ), 0;
if( N == 9 && K == 2 ) return puts( "NO" ), 0;
if( Chk( N + 1 ) && K == 1 ) return puts( "NO" ), 0;
if( ! Chk( N + 1 ) && K == 0 ) return puts( "NO" ), 0;
puts( "YES" );
int base = 2 * MAX( 0, K - 1 );
for( int i = 1 ; i < base ; i += 2 )
ance[i + 1] = i, ance[i] = MAX( 0, i - 2 );
for( int i = 1 ; i <= N - base ; i ++ )
{
if( i == 1 ) ance[i + base] = MAX( 0, base - 1 );
else ance[i + base] = ( i >> 1 ) + base;
}
if( Chk( N - base + 1 ) && K ) ance[N - 1] = ance[N] = 2;
for( int i = 1 ; i <= N ; i ++ ) write( ance[i] ), putchar( i == N ? '
' : ' ' );
return 0;
}