The solution of「P16394 回响形态」- 构造

· · 题解

\textup{P16394 回响形态}

\textup{Link} | 更好体验 | \textup{Tag: }构造。

\textup{Solution}

> 瞪不出来的话，打一打表也可以看出。 > > 结论：当 $k \in [{\large \frac{n(n -1)}{2}}, (n-1)\cdot(n-1)]$ 才有解。 > > :::success[$\textup{Proof.}$] > > 考虑如果有 $i$ 位，极差一定不会小于 $i - 1$，取一个升序排列可以取到，所以是 ${\large \frac{n(n -1)}{2}}$。 > > 考虑最大值，让 $x_1 - y_1 = 0$，之后每个都是 $n - 1$ 是可行的。 > > 此时序列为 $1,n,n-1,n-2,\cdots,2$，感性理解是最大的（额可能不是很严谨）。 > > ::: $\textup{Step2}$：两个序列的条件真奇怪……难道有什么特殊含义？ > 瞪不出来的话，打一打表也可以看出。 > > 结论：当我们找到一个满足条件的序列 $a$ 之后，让 $a_i \gets n - a_i + 1$ 即可得到另一个合法序列。 > > :::success[$\textup{Proof.}$] > > 显然有反转后还是排列。 > > 接着就是最大变最小，最小变最大，减出来的东西实际上还是一样的。 > > 即设原来最大是 $M$，最小是 $m$，有 $(n+1−m) − (n+1−M) = M − m$，得证。 > > ::: $\textup{Step3}$：如何构造出一个序列？ > 瞪不出来的话，打一打表……似乎也看不出。 > > 我们考虑排列产生的贡献是从 ${\large \frac{n(n -1)}{2}}$ 起步的，那么思考它与真正的 $k$ 相差了多少。 > > 假设初始序列是 $a = [1, 2, 3, \cdots, n]$，那么此时的 $k$ 是下界的值，在第一个部分有所说明。 > > **第一步**，我们将第 $n$ 个数往前拉，贡献会逐渐增加。设从 $n$ 到 $n-m$ 个位置，增加的贡献就是 ${\large \frac{m(m + 1)}{2}}

此时序列是 a = [1, 2, \cdots, j, n, j + 1, \cdots, n - 1]。

这种调整方法是跨度较大的，我们只能调到保证正好不大于 k 然后继续微调。

第二步，根据前面的推导，我们在 n 出现之前的位置的代价是 i - 1。

而因为已经遇到了 1 和 n，从 j 那一位开始每一位就固定为 n-1 了。

考虑通过动 j 这个位置来凑代价，如果当前还需要多少代价我们就把 j 和后面已经固定代价的部分的某个数交换来凑齐。

这一定是可行的，因为我们需要的数一定在后面又出现，且在第一步调整的时候保证了此时不会大于 k。

\textup{Code}

\textup{Submission.}

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 2e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int N, K;
int a[MAXN], b[MAXN];

//----------------------打表用的暴力，需要自取
bool vis[MAXN], flg, flg1;
void dfs( int dep ){
    if( flg && flg1 ) return;
    if( dep > N ){
        if( flg && flg1 ) return;
        int k = 0, maxx = 0, minn = inf;
        for( int i = 1; i <= N; i ++ ){
            maxx = max( maxx, a[i] );
            minn = min( minn, a[i] );
            k += maxx - minn;
        }
        if( k == K ){
            if( flg ) flg1 = true;
            else flg = true;
            for( int i = 1; i <= N; i ++ ){
                cout << a[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for( int i = 1; i <= N; i ++ ){
        if( vis[i] ) continue;
        vis[i] = true;
        a[dep] = i;
        dfs( dep + 1 );
        vis[i] = false;
    }
}
//---------------------------------

void slove(){
    int cnt = 0;
    flg = flg1 = false;
    cin >> N >> K;
    for( int i = N - 1; i >= 1; i -- ) cnt += i;
    if( K < cnt || K > ( N - 1 ) * ( N - 1 ) ){//判无解
        cout << "-1\n";
        return;
    }

    int neeed = K - cnt, m = 0;//计算还有多少贡献需要加回去
    while( ( m + 1 ) * ( m + 2 ) / 2 <= neeed ) m ++;
    neeed -= m * ( m + 1 ) / 2;//第一步

    int j = N - m - 1, k;
    for( k = 1; k < j; k ++ ) a[k] = k;//前i位不动
    a[k ++] = j + neeed;//第二步
    a[k ++] = N;
    for( int i = j; i <= N - 1; i ++ )
        if( i != j + neeed ) a[k ++] = i;//把剩下的数按顺序放回去
    for( int i = 1; i <= N; i ++ ) cout << a[i] << " ";
    cout << endl;
    for( int i = 1; i <= N; i ++ ) cout << N - a[i] + 1 << " ";
    cout << endl;
}

signed main(){
    ios::sync_with_stdio( 0 );
    cin.tie( 0 ), cout.tie( 0 );
    // freopen( "star.in", "r", stdin );
    // freopen( "star.out", "w", stdout );
    int T = 1;
    cin >> T;
    while( T -- )
        slove();
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗？

谢谢你看到这里~