CF1649D 题解

· · 个人记录

题目大意：

给定 n 和 c。
给定一个长度为 n 的数组 a (1 \le a_i \le c) 。有以下规则：
数组中拿出任意两个数 x,y (y \le x)，如果 \lfloor \frac{x}{y} \rfloor 也存在于数组中，那么称这个数组是完美的。
问 a 数组是不是完美的。

1 \le n \le 10^6 1 \le c \le 10^6

题目分析：

可以发现，题目限定了每个数组元素 a_i \le c,也就是说 a_i 不会超过 10^6，可以用一种类似于线性筛的方法求解。
枚举 i 从 2 到 n，作为除数。里面再套一层枚举 j 作为商 (i \cdot j \le c)。此时被除数的范围是 (i \cdot j,i \cdot j + i-1)。显然，如果数组中的某一个数在当前被除数范围中，并且数组中不存在商 j，那么数组 a 就不是完美的。

那么如何判断某个数值范围内是否有数出现在 a 中呢，可以使用前缀和的方法。定义一个数组 hash,记录 a 中每一个值出现次数，代码如下： 

for(int i=1;i<=n;i++)
{
    a[i]=read();
    hash[a[i]]++;
}

然后定义一个数组 qzh，qzh_i 代表 1 到 i 的所有数字在 a 中的出现次数。假设被除数数值范围是 (l,r)，如果 qzh[r]-qzh_{l-1} 的值为 0，那么说明数组 a 没有一个元素在被除数数值范围内，否则说明数组 a 至少有一个元素在被除数数值范围内。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
namespace Main
{
    inline int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
    int hash[maxn];
    int qzh[maxn];
    int a[maxn];
    bool vis[maxn];
    int t;
    int n,c;
    void main()
    {
        t=read();
        while(t--)
        {
            n=read();
            c=read();
            for(int i=1;i<=n;i++)
            {
                a[i]=read();
                hash[a[i]]++;
                vis[a[i]]=1;
            }
            for(int i=1;i<=c;i++)
            {
                qzh[i]=qzh[i-1]+hash[i];
            }//方便确定某一个范围内的数的数量
            bool flag=1;
            for(int i=2;i<=c;i++)
            {
                if(!vis[i])continue;
                for(int j=1;i*j<=c;j++)
                {//枚举因数，跟线性筛有些像
                    int l=i*j;
                    int r=i*j+i-1;
                    r=min(r,c);
                    if((qzh[r]-qzh[l-1])&&!vis[j])
                    {
                        flag=0;
                    }
                }
            }
            if(!flag)
            {
                printf("No\n");
            }
            else
            {
                printf("Yes\n");
            }
            for(int i=1;i<=n;i++)
            {
                hash[a[i]]--;
                vis[a[i]]=0;
            }
        }
    }
}
int main()
{
    Main::main();
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}