H. GCD is Greater
题意
给定一个长度为 n n n的数组 a a a,先手选择 [ 2 , n − 2 ] [2,n-2] [2,n−2]个数并计算所选择数的gcd,后手选择剩下的数,并计算剩下所有的数按位与的结果,再加上给定的 x x x,如果先手的结果大于后手,则先手赢,否则后手赢。找出先手必胜的方案,或输出先手不可能获胜。
分析
首先贪心地想到,若想gcd大,选择的数的数量越小越好,即只选择两个数,因为再选择别的数gcd不会再增加,而不会让结果更优。
再考虑到后手的计算过程为剩下的数按位与,那么考虑每一位的最终结果,统计每一位在数组中出现了多少次。对于每一位,此时有三种可能,令先手选择的两个数的下标为 x 1 x_{1} x1, x 2 x_{2} x2
- x 1 x_{1} x1和 x 2 x_{2} x2中有一个数在该位为1
- x 1 x_{1} x1和 x 2 x_{2} x2在该位的值都是1
- x 1 x_{1} x1和 x 2 x_{2} x2在该位的值都是0
对于上述三种情况,当该位为 1 1 1的数量 − ( x 1 -(x_{1} −(x1和 x 2 x_{2} x2在该位为 1 1 1的数量 ) = n − 2 )=n-2 )=n−2,则后手计算的结果中这一位必定是 1 1 1,否则必定是 0 0 0,那么我们可以找到这些特殊点,即该位为 1 1 1的数量为 n n n或 n − 1 n-1 n−1或 n − 2 n-2 n−2时, a i a_{i} ai在该位非 1 1 1,那么当我们选或不选它们对结果是有影响的。该集合大小为 2 l o g ( m a x ( a i ) ) 2log(max(a_{i})) 2log(max(ai))。然后考虑除了上述情况的其他情况,根据贪心想法,肯定是gcd越大越好,那么我们可以存下每个数以及其约数出现次数的和,然后从大到小枚举gcd的大小,暴力判断即可,只需要判断能取到的最大gcd即可,其他的必然不会比最大的更优。
对于会影响按位与的数,固定一个有影响的数,然后枚举另一个数,再暴力判断是否符合条件即可,时间复杂度 O ( n ( ( l o g ( m a x a i ) ) 2 + l o g ( m a x a i ) l o g V ) ) O(n((log(maxa_{i}))^{2}+log(maxa_{i})logV)) O(n((log(maxai))2+log(maxai)logV)), l o g V logV logV为计算gcd的复杂度
AC代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
vector<int> p[400010];
void init() {
for (int i = 1; i <= 400000; i++) {
for (int j = i; j <= 400000; j += i) {
p[j].emplace_back(i);
}
}
}
LL gcd(LL a, LL b) {
return b == 0 ? a : gcd(b, a % b);
}
void Solve() {
int n, x;
cin >> n >> x;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int maxx = *max_element(a.begin() + 1, a.end());
int L = __lg(maxx);
vector<int> cnt(L + 1);
vector<int> cnt1(maxx + 1);
vector<int> z;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= L; j++) {
if (a[i] >> j & 1) {
cnt[j]++;
}
}
}
vector<bool> vis(n + 1);
for (int j = 0; j <= L; j++) {
if (cnt[j] < n - 2) {
continue;
}
for (int i = 1; i <= n; i++) {
if (!(a[i] >> j & 1)) {
z.emplace_back(i);
vis[i] = true;
}
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
int sz1 = p[a[i]].size();
for (int j = 0; j < sz1; j++) {
cnt1[p[a[i]][j]]++;
}
}
}
vector<int> q;
for (int i = maxx; i >= 1; i--) {
if (cnt1[i] < 2) {
continue;
}
for (int j = 1; j <= n && q.size() < 2; j++) {
if (a[j] % i == 0 && !vis[j]) {
q.emplace_back(j);
}
}
int g = gcd(a[q[0]], a[q[1]]);
int sum = 0;
for (int j = 0; j <= L; j++) {
int num = 0;
if (a[q[0]] >> j & 1) {
num++;
}
if (a[q[1]] >> j & 1) {
num++;
}
if (cnt[j] - num == n - 2) {
sum |= (1 << j);
}
}
if (sum + x < g) {
cout << "YES\n";
cout << "2 " << a[q[0]] << " " << a[q[1]] << '\n';
cout << n - 2 << " ";
for (int j = 1; j <= n; j++) {
if (j != q[0] && j != q[1]) {
cout << a[j] << " ";
}
}
cout << '\n';
return;
}
break;
}
sort(z.begin(), z.end());
z.erase(unique(z.begin(), z.end()), z.end());
int sz = z.size();
for (int i = 0; i < sz; i++) {
for (int j = 1; j <= n; j++) {
if (z[i] == j) {
continue;
}
int sum = 0;
for (int k = 0; k <= L; k++) {
int num = 0;
if (a[j] >> k & 1) {
num++;
}
if (a[z[i]] >> k & 1) {
num++;
}
if (cnt[k] - num == n - 2) {
sum |= (1 << k);
}
}
int g = gcd(a[j], a[z[i]]);
if (sum + x < g) {
cout << "YES\n";
cout << "2 " << a[j] << " " << a[z[i]] << '\n';
cout << n - 2 << " ";
for (int k = 1; k <= n; k++) {
if (k != z[i] && k != j) {
cout << a[k] << " ";
}
}
cout << '\n';
return;
}
}
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int T;
cin >> T;
while (T--) {
Solve();
}
return 0;
}
文章评论