题解：CF2147B Multiple Construction

赛时这个题和 E 卡了我八百年，怄火怄火怄火。

来个不需要脑电波构造的方法。

如何用奇怪的方式撞到通解。

Solution

首先从剩余系的角度入手：把每个下标 $\bmod x$，划分成 $x$ 个同余类，这样想给 $x$ 选两个位置只需要在某个同余类里找两个空位即可。

有一个显然错误的暴力思路是按 $x$ 从小到大暴力放。具体地，对于每个 $x$，用并查集维护空位 $p$，每次找到一个空位就暴力跳，如果有 $p$ 和 $p + kx$ 都是空位，就把这两个位置填上 $x$，如果没有就继续看下一个空位。

这个做法随便举个例子比如 $n = 3$ 就能轻松 hack。原因是，我们没办法保证处理到 $x$ 时一定有一个同余类有 $\geq 2 $ 个空位。

但是我们可以按 $x$ 从大到小放！这样当处理到 $x$ 的时候前面已经占了 $2(n - x)$ 个位置，还剩 $2x$ 个空位，抽屉原理可得，至少有一个同余类 $\geq 2$ 个空位，所以正确性是对的。

这时候有一个很好玩的事情：我们不难发现，这个做法构造出来的其实和官解那个 $n, n - 1, \cdots, 1, n, 1, 2, n - 1$ 是一样的，所以其实每个 $x$ 只会跳 $O(1)$ 次，因此复杂度是 $O(n\alpha (n))$。

Code

// Problem: B. Multiple Construction
// Contest: Codeforces - Codeforces Global Round 29 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2147/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

const int maxn = 4e5 + 5 ;

int n, ans[maxn] ;
int m ;
bool vis[maxn] ;
struct dsu {
    int f[maxn], g[maxn] ;
    void init() {
        rep(i, 1, m + 1) f[i] = i ;
    }
    int fnd(int x) {
        if(x == f[x]) return x ;
        f[x] = fnd(f[x]) ;
        return f[x] ;
    }
    void add(int x) {
        f[x] = fnd(x + 1) ;
    }
} d ;

void solve(){
    cin >> n ;
    m = n * 2 ;
    d.init() ;
    rep(i, 1, m) {
        ans[i] = vis[i] = 0 ;
    } 
    per(x, n, 1) {
        int p = d.fnd(1) ;
        while(p <= m) {
            int q = p + x ;
            while(q <= m && vis[q]) q += x ;
            if(q <= m) {
                ans[p] = ans[q] = x ;
                vis[p] = vis[q] = 1 ;
                d.add(p) ; d.add(q) ;
                break ;
            }
            else p = d.fnd(p + 1) ;
        }
    }
    rep(i, 1, m) {
        cout << ans[i] << ' ' ;
    } 
    cout << endl ;
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

---

• 分类： OI
• 标签： 无标签