跳转至

杭电多校9 01

Arithmetic Subsequence

题目链接

题目大意

给定一个数组，请问能够将该数组重新排列使得不存在任何一个等差三元组\((i, j, k)\)，其中\(1 \le i \lt j \lt k \le n\)。

题解

假设我们要构造一个1-n的排列满足题意，我们可以这样操作

从0，1开始，先把0，1复制一遍，前面的乘2，后面的乘2+1，变成0，2，1，3，然后继续这样操作，变成0，4，2，6，1，5，3，7

这样构造是满足题意的

接下来考虑怎么表示这种规律

我们发现这些数的二进制数有某种规律

若将这些数的二进制数翻转，我们发现其实它是递增的

考虑到这样的性质，我们直接对给定的数的二进制翻转后排序即可

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N = 5005;
int a[N];
typedef pair<int, int> PII;
PII b[N];
map<int, int> cnt;
signed main() {
    int t;
    cin >> t;
    while(t -- ) {
        int n;
        cin >> n;
        cnt.clear();
        bool flag = true;
        for(int i = 1; i <= n; i ++ ) {
            cin >> a[i];
            b[i] = {0, a[i]};
            cnt[a[i]] ++ ;
            if(cnt[a[i]] > 2) {
                flag = false;
            }
        }
        if(!flag) {
            cout << "NO" << '\n';
            continue;
        }

        cout << "YES" << '\n';
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 0; j < 32; j ++ ) {
                if((b[i].y >> j) & 1) b[i].x |= (1LL << (32 - j));
            }
        }
//        for(int i = 1; i <= n; i ++ ) cout << b[i].x << " ";
//        cout << '\n';
        sort(b + 1, b + n + 1);
        for(int i = 1; i <= n; i ++ ) cout << b[i].y << ' ';
        cout << '\n';
    }
    return 0;
}