题解 P6104 【[EER2]相同的数字】

lemondinosaur · 2020-02-19 14:37:03 · 题解

传送门

题目大意

有n个数，可以在一个单位时间内用c1的花费

使x变为x+1，用c2的花费使y变为\min_{y'\in prime,y'>y}y'

每次询问c1,c2都会改变，但是原来的n个数在询问后恢复原状，

问使n个数相同的最小花费（强制在线）

分析

考场的时候想到伪50分的做法，但是被我弄成了10分的暴力

（然而就是暴力），只要记忆化答案应该能够卡常卡到五十分

首先考场的时候想到第一条性质：这n个数要么变成\max_{1\leq i\leq m}a_i，

要么变成\max_{1\leq i\leq m}a_i'(注意那个'和之前的定义相同)

首先线性筛所有范围里的质数（\approx 6.6\times 10^4个）。

然后预处理每个数x的x'，询问时跳到下一个质数

（因为一个一个跳总会跳到下一个质数）

~~暴力跳，终于拿到了10分，还跑得很慢~~

考后询问julao解法，预处理出跳到\max或\max'的每种长度需要跳的次数，

然后解不等式len\times c1<c2 那么当len<\lfloor\frac{c2}{c1}\rfloor时选择跳一步(花c1)，否则跳到质数（花c2），

这个可以用前缀和O(1)实现，所以总时间复杂度应该是

O(\max_{1\leq i\leq n}a_i+n+q)

瓶颈主要是询问和预处理

等等，预处理怎么弄？~~代码又长又丑~~

分成两种情况，这里以预处理a_j到\max为例，

首先把头尾长度单独加入答案，然后中间部分考虑差分，就是在开头加1，结尾的下一个减1，然后差分数组最后跑前缀和

是不是听起来很简单，按照julao的解法，我成功地WA了

主要有两个细节问题

跳一步需要记录长度，所以不仅要记录次数，而且要记录长度\times次数
对于跳到\max的情况有一段是不能计入跳到质数的（因为跳到\max不一定到的是质数）

改完之后，成功获得了一份常数巨大的正解（记得开\text {long long}）

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=10001001,M=666666; int cnt,n,Q,Is_Last,mx,mx1,mx2;
long long sL1[201],sL2[201],xz1,sN1[201],sN2[201];
int prime[M],v[N],nx[N],cf1[M],cf2[M],a[M/6];
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void print(long long ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
inline signed max(int a,int b){return a>b?a:b;}
inline void pro(int N){//线性筛
    for (rr int i=2;i<=N;++i){
        if (!v[i]) prime[++cnt]=i,v[i]=cnt;
        rr int t=N/i;
        for (rr int j=1;prime[j]<=t;++j){
            v[i*prime[j]]=j;
            if (i%prime[j]==0) break;
        }
    }
    for (rr int i=N-1,j=cnt;i;--i){
        nx[i]=prime[j];
        if (i==prime[j-1]) --j;
    }   
}
signed main(){
    n=iut(),Q=iut(),Is_Last=iut();
    for (rr int i=1;i<=n;++i) mx=max(mx,a[i]=iut());
    pro(mx+500),mx1=prime[v[nx[mx]]-1],mx2=nx[mx];
   //1.x->mx1->mx 2.x->mx2
    for (rr int i=1;i<=n;++i){
     //上面一坨是第一种情况
        if (nx[a[i]]>mx&&mx!=a[i]){
            if (prime[v[mx]]==mx) sL1[mx-a[i]]+=mx-a[i],++sN1[mx-a[i]];
                else xz1+=mx-a[i];//这一段不能加
        }
        else if (mx!=a[i]){
            ++sN1[nx[a[i]]-a[i]],sL1[nx[a[i]]-a[i]]+=nx[a[i]]-a[i];
            if (prime[v[mx]]==mx) sL1[mx-mx1]+=mx-mx1,++sN1[mx-mx1];
                else xz1+=mx-mx1;
            ++cf1[v[nx[a[i]]]],--cf1[v[mx1]];
        }
    //----------------------
        sL2[nx[a[i]]-a[i]]+=nx[a[i]]-a[i],++sN2[nx[a[i]]-a[i]];
        ++cf2[v[nx[a[i]]]],--cf2[v[mx2]];
    //差分
    }
    for (rr int i=1;i<=cnt;++i) cf1[i]+=cf1[i-1],cf2[i]+=cf2[i-1];//前缀和
  //sL长度乘次数前缀和，sN次数前缀和
    for (rr int i=1;i<cnt;++i)
        sN1[prime[i+1]-prime[i]]+=cf1[i],sN2[prime[i+1]-prime[i]]+=cf2[i],
        sL1[prime[i+1]-prime[i]]+=cf1[i]*(prime[i+1]-prime[i]),
        sL2[prime[i+1]-prime[i]]+=cf2[i]*(prime[i+1]-prime[i]);
    for (rr int i=1;i<=170;++i)
        sL1[i]+=sL1[i-1],sL2[i]+=sL2[i-1],
        sN1[i]+=sN1[i-1],sN2[i]+=sN2[i-1];
    for (rr long long lans=0,c1,c2,c3;Q;--Q){
        lans%=131072,c1=iut(),c2=iut();
        if (Is_Last) c1^=lans,c2^=lans;
        lans=0,c3=c2/c1>160?160:c2/c1;//解不等式
        rr long long s1=(sL1[c3]+xz1)*c1+(sN1[170]-sN1[c3])*c2,
                     s2=sL2[c3]*c1+(sN2[170]-sN2[c3])*c2;
        print(lans=s1<s2?s1:s2),putchar(10);
    }
    return 0;
}