P8036 题解

Demeanor_Roy · 2022-09-17 11:42:48 · 题解

• 原题链接

• 考虑到其余题解人均打表，这里来一篇不一样的做法。

• 当然正解是不可能正解的，那太人类智慧了，想学的请转 COCI 官网。

Part 1

• 首先我们可以发现，对于一个具体的询问，我们用 L 和 R 分别表示答案区间左右端点，那么可能的答案区间分为三种：

Part 2

• 很自然地，我们想到了预处理，预处理出长度为 k 的高兴数（因为是第三类情况，也可以说成质数）个数为 L 的区间,询问时直接查表即可，这样做只需要对每一个区间长度扫一遍全集，时间复杂度能做到 150 \times 10^7 ，无疑优秀了许多。可这样做有一个限制是我们没有考虑到的，那就是 M。
• 怎样才能忽略 M 的限制呢？考虑贪心，对于满足长度为 i，区间内质数个数为 j 的区间，我们只保留起始位置最大的那个。这是因为 M 对答案的限制只是区间左端点必须大于 M，那左端点当然是越大越好！
• 于是，我们成功地完成了优化地第一步。

Part 3

• 在进入最重要的优化前，先讲几个更容易想到，但似乎用处不太大的 trick：
  1. 只预处理询问中出现过的区间长度。
  2. 预处理时倒序查找，如果对当前 K 值，所以合法的 L 都找到了区间，则中断循坏。
  3. 各种常数优化。

Part 4

• 其实若是这道题时限给到 2 s，那本篇题解也就到此为止了，可惜呀！
• 当我们发现其余地方都做到了极致时，似乎忘记考虑一个被我们忽略的细节：那就是我们真的需要 10^7 的全集吗？
• 让我们思考一下，对于确定的 K 值，L 能否取到只关乎与区间质数密度，而质数密度的范围与全集大小的关系并不是完全对应的，有没有这样一种可能，用更小的全集规模就能筛出 10^7 所能筛出的所有 L 的取值？
• 这时，你就可以愉快地人肉二分了！！！（正好正解也是二分）
• 这里直接放结论，3\times 10^6 就足够了。

• 于是，你愉快地通过了此题。
• 代码：

#include<bits/stdc++.h>
using namespace std;

const int N=3e6,M=5e5+10,G=155;
int Q,k,l,m;
int v[N],prime[M],id,ans[G][G];
bool st[G];

inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))  x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void write(int x)
{
    if(!x)  return;
    write(x/10);
    putchar(x%10+'0');
}
inline void init()
{
    for(register int i=2;i<=N-10;i++)
    {
        if(!v[i])   v[i]=i,prime[++id]=i;
        for(int j=1;j<=id;j++)
        {
            if(i*prime[j]>N-10||prime[j]>v[i])  break;
            v[i*prime[j]]=prime[j];
        }
    }
     //欧拉筛筛质数
    for(register int i=1;i<=N-10;i++)   v[i]=v[i-1]+(v[i]==i);
     //质数前缀和
}
inline void get(int len)
{
    int cnt=0;
    for(register int sta=N-160;sta>=1;sta--)
    {
        if(ans[len][v[sta+len-1]-v[sta-1]]) continue;
        cnt++;
        ans[len][v[sta+len-1]-v[sta-1]]=sta;
        if(cnt==len+1)  break;
    }   
    //对每一个 k 值进行预处理
}
int main()
{
    init();
    Q=read();
    for(register int i=1;i<=Q;i++)
    {
        k=read(),l=read(),m=read();
        if(k==l&&k<=m)
        {
            putchar('1');
            putchar('\n');
            continue;   
        }
        //情况一
        bool flag=false;
        for(register int j=max(1,m-k+2);j<=m;j++)   
            if(m-j+1+v[j+k-1]-v[m]==l)
            {
                write(j);
                putchar('\n');
                flag=true;
                break;
            }
        if(flag)    continue;
        //情况二
        if(!st[k])  st[k]=true,get(k);
        if(ans[k][l]>m) 
        {
            write(ans[k][l]);
            putchar('\n');
        }
        //情况三
        else
        {
            putchar('-');
            putchar('1');
            putchar('\n');
        }
        //无解
    }
    return 0;
}

• 完结撒花~