关键点在于 \(M\le N\le2M\) 的条件。
结论:在 \(1\sim2M\) 中至多选出 \(M\) 个数使得它们两两不为整除关系。
证明:鸽巢原理。考虑把每个数写成 \((x,y)\) 表示 \(A_i=x\times 2^y\),其中 \(x\) 是奇数,然后把这个数的 \(y\) 丢进桶 \(x\) 里,发现每个桶只能选恰好一个,而桶的数量就是 \(M\)。
接下来就很套路了,如果两个桶 \(a=kb\),那么 \(b\) 桶中选的数一定大于 \(a\) 桶中选的数,那么就可以贪心的求出每个桶中能取得的最大值/最小值。
时间复杂度 \(\mathcal O(N\ln N)\)。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 600005;
int n, m;
int a[N];
int f[N], g[N], w[N];
vector <int> cnt[N];
void ret() { while (n--) printf("No\n"); exit(0); }
void chkmax(int &a, int b) { if (a < b) a = b; }
void chkmin(int &a, int b) { if (a > b) a = b; }
int main() {
scanf("%d%d", &n, &m), m <<= 1;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x), a[i] = x;
int y = __builtin_ctz(x);
cnt[x >> y].push_back(y);
}
for (int i = 1; i <= m; ++i) if ((i & 1) && cnt[i].empty()) ret();
memset(f, 0xcf, sizeof f), memset(w, 0xcf, sizeof w);
for (int i = m; i; --i) if (i & 1) {
for (int j = i + i; j <= m; j += i) chkmax(f[i], w[j]);
if (f[i] >= cnt[i].back()) ret();
w[i] = *upper_bound(cnt[i].begin(), cnt[i].end(), f[i]);
}
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= m; ++i) if (i & 1) {
if (g[i] <= cnt[i].front()) ret();
w[i] = *--lower_bound(cnt[i].begin(), cnt[i].end(), g[i]);
for (int j = i + i; j <= m; j += i) chkmin(g[j], w[i]);
}
for (int i = 1; i <= n; ++i) {
int y = __builtin_ctz(a[i]);
int x = a[i] >> y;
printf("%s\n", (f[x] < y && y < g[x]) ? "Yes" : "No");
}
return 0;
}
标签:cnt,No,int,void,back,ret,ARC141D
From: https://www.cnblogs.com/Kobe303/p/16818877.html