CF237C

标签：int mid vis CF237C num prm check

我来水题解啦！！

首先这题和素数有关，我们就先需要一个线性筛：

int prm[1000005],tot;
bool vis[1000005];
void init(){
    vis[1]=vis[0]=1;
    for(int i=2;i<=b;i++){
        if(!vis[i])prm[++tot]=i;
        for(int j=1;j<=tot;j++){
            if(i*prm[j]>b)break;
            vis[i*prm[j]]=1;
            if(i%prm[j]==0)break;
        }
    }
}

然后让我们分析一下这题的答案：

设最优解为 \(ans\) ，其他答案为 \(sol\) ，若 \(sol<ans\) ，则这个 \(sol\) 一定无法满足条件；若 \(sol>ans\) ，则 \(sol\) 可以满足条件，但是不是最优的。

那么显然，对于这种答案分布，我们可以利用二分法求解。这是一个二分答案的板子：

int l=1,r=b-a+1;
while(l<r){
    int mid=(l+r)>>1;
    if(check(mid))r=mid;
    else l=mid+1;
}
cout<<r<<endl;

接下来我们考虑check函数：

其实很简单，我们只需要用 \(l\) 和 \(r\) 模拟一个区间，再利用一个 \(num\) 表示区间内素数的个数，如果在某一时刻 \(num<k\) ，则此答案无法满足要求，否则可以，代码：

bool check(int len){
    int t=a,h=a-1,num=0;
    while(h-t+1<len){
        h++;
        if(!vis[h])num++;
    }
    while(h<=b){
        if(num<k)return 0;
        h++;if(!vis[h])num++;
        t++;if(!vis[t-1])num--;
        //模拟区间向前移动一个位置
    }
    return 1;
}

最后对于无解的判断：如果整个区间内的素数个数都不到 \(k\) ，换句话说，就算是把整个区间覆盖住也无法满足需求，那么就是无解，特判代码：

int num=0;
for(int i=a;i<=b;i++)if(!vis[i])num++;
if(num<k){cout<<-1<<endl;return 0;}

那么这题就愉快地结束了！好水啊

此题虽然 \(a,b,k\) 范围都是百万，但是 \(n\log n\) 做法完全可过。

\[\mathfrak{End.} \]

标签：int,mid,vis,CF237C,num,prm,check
From： https://www.cnblogs.com/untitled0/p/17350634.html