标签：10 Non Set divisible int ch read isdigit

ARC141D Non-divisible Set

这题还是比较有启发性的。

经典的偏序关系下最长反链，第一反应是转化为最小链覆盖，但是在很多以整数的整除关系为背景的题目中这个做法不是最好的。

洛谷的题意翻译中少给了一个信息：值域为 \([1,2M]\)。这个条件看上去就应该和选 \(M\) 个数的限制结合。若由 \(i\) 向 \(2i\) 连边，观察到恰好形成了 \(M\) 条链，又有每条链只能选一个数，所以最多选 \(M\) 个数，且每条链上都需要选一个数。

如果把每条链中唯一的奇数当作这条链的代表元，那么可以将最终选出来的每个数都表示为 \(2^{k_n}n\) 的形式，现在只需要解决 \(k\) 的取值。

重新描述题目中的限制

\[2^{k_i}i | 2^{k_j}j \Leftrightarrow i | j \wedge k_i \leq k_j \]

考察对于奇数 \(i\)，若有 \(k_i\) 的最大值为 \(r_i\)，最小值为 \(l_i\)，不难发现对于任意 \(x \in [l_i,r_i]\)，\(k=x\) 都是合法的。所以现在只需要求 \(l\) 和 \(r\) 了。这是平凡的。时间复杂度 \(O(m \log m + n)\)

这题关键在于由 \(i\) 向 \(2i\) 连边的分组，利用了值域和限制的特殊关系，通过钦定奇数为代表元化简了问题。

#include <bits/stdc++.h>
#define log2(x) (31 - __builtin_clz(x))
 
using namespace std;
 
typedef long long LL;
 
namespace IO {
  #define isdigit(x) (x >= '0' && x <= '9')
  template<typename T>
  inline void read(T &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if(f) x = -x;
  }
  template<typename T>
  inline void write(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  #undef isdigit
}
using namespace IO;
 
const int N = 6e5 + 10;
 
int n, m;
int a[N], c[N];
int l[N], r[N];
int ans[N];
 
vector<int> factor[N];
 
int main() {
  read(n), read(m);
  for(int i = 1; i <= n; ++i)
    read(a[i]), c[a[i]] = 1;
  
  for(int i = 1; i <= 2 * m; i += 2)
    for(int j = i * 3; j <= 2 * m; j += i * 2)
      factor[j].emplace_back(i);
  
  for(int i = 1; i <= 2 * m; i += 2)
    r[i] = log2(2 * m / i), l[i] = 0;
 
  for(int i = 1; i <= 2 * m; i += 2) {
    for(int j : factor[i]) 
      r[i] = min(r[i], r[j] - 1);
    while(r[i] && !c[i << r[i]]) --r[i];
    if(!r[i] && !c[i]) {
      for(int i = 1; i <= n; ++i)
        puts("No");
      return 0;
    }
  }
 
  for(int i = 2 * m - 1; i >= 1; i -= 2) {
    while((i << l[i]) <= 2 * m && !c[i << l[i]]) ++l[i];
    if((i << l[i]) > 2 * m) {
      for(int i = 1; i <= n; ++i)
        puts("NO");
      return 0;
    }
    for(int j : factor[i])
      l[j] = max(l[j], l[i] + 1);
  }
  
  for(int i = 1; i <= 2 * m; i += 2) 
    for(int j = l[i]; j <= r[i]; ++j)
      ans[i << j] = 1;
  for(int i = 1; i <= n; ++i)
    puts(ans[a[i]] ? "Yes" : "No");
  return 0;
} 

标签：10,Non,Set,divisible,int,ch,read,isdigit
From： https://www.cnblogs.com/DCH233/p/17260369.html