杭电多校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;
}
|