Codeforces Round #477 (rated, Div. 2, based on VK Cup 2018 Round 3) E 贪心

时间:2021-10-08 06:57:46

http://codeforces.com/contest/967/problem/E

题目大意:

给你一个数组a,a的长度为n

定义:b(i) = a(1)^a(2)^......^a(i),

问,是否存在一种情况,使得a(i)重新排列以后以后,满足b(i)是严格单调递增的。

思路:

对于二进制位操作来说,如果异或后值增加,即 p^q > p,必然满足两种情况(假定一个为p,一个为q)

①q的最高位>p的最高位

②q的最高位(假定第k为最高) < p的最高位,但是p的第k位为0

这样,我们就贪心的去找就好啦。

每次都贪心的找符合条件的,且value最小的即可。

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 1e5 + ;
int n;
vector<LL> ve;
vector<LL> bite;
vector<LL> G[maxn];
int pos[maxn];
int maxlen; void get_bite(LL sum){
bite.clear();
while (sum){
bite.pb(sum % );
sum >>= ;
}
} bool solve(){
LL sum = ;
vector<LL> ans;
for (int i = ; i <= n; i++){
get_bite(sum);
bool flag = false;
for (int j = ; j <= maxlen; j++){
if (j == bite.size()) continue;
else if (j < bite.size() && (bite[j - ] == )){
if (G[j].size() > && (G[j].size() > pos[j])){
flag = true;
ans.push_back(G[j][pos[j]]);
sum ^= G[j][pos[j]];
pos[j]++;
break;
}
}
else if (j > bite.size()){
if (G[j].size() > && (G[j].size() > pos[j])){
flag = true;
ans.push_back(G[j][pos[j]]);
sum ^= G[j][pos[j]];
pos[j]++;
break;
}
}
}
if (!flag) return false;
}
puts("Yes");
for (int i = ; i < ans.size(); i++){
printf("%lld ", ans[i]);
}
cout << endl;
return true;
} int main(){
cin >> n;
for (int i = ; i <= n; i++){
LL a; scanf("%lld", &a);
ve.pb(a);
}
for (int i = ; i < ve.size(); i++){
LL tmp = ve[i];
int cnt = ;
while (tmp){
cnt++;
tmp >>= ;
}
G[cnt].pb(ve[i]);
maxlen = max(maxlen, cnt);
}
for (int i = ; i <= maxlen; i++){
sort(ALL(G[i]));
}
if (solve() == false) puts("No");
return ;
}