BZOJ1423 : Optimus Prime

设$f[x]$表示为了保证自己可以取到质数$x$，第一步在$[0,n]$中可以选的数是多少。

这个数是唯一的，因为如果存在两个$f[x]=a,b(a<b)$，那么如果先手取了$a$，后手就能取$b$来让先手取不到$x$，矛盾。

如果$x$与下一个质数之间的差值大于$n$，那么$f[x]$就是结果，当$f[x]=0$时先手必败。

对于不超过$n$的$x$，$f[x]=x$。

对于大于$n$的$x,f[x]=f[y]$，其中$y$是$x$前面最近的与它差值大于$n$的质数，可以双指针得到。

如果没有找到终止态，取一定范围内的所有大质数的$f[x]$的众数，极有可能就是精确解。

#include<cstdio>

const int N=3000010,M=N/10,E=1010;

int T,n,t,i,j,tot,p[M],f[M],c[E],ans[E];bool v[N];

inline int cal(int n){

  if(~ans[n])return ans[n];

  int i,j;

  for(i=0;i<=n;i++)c[i]=0;

  for(i=j=0;i<=tot;i++){

    if(p[i]<=n)f[i]=p[i];

    else{

      while(j+1<i&&p[i]-p[j+1]>n)j++;

      f[i]=f[j];

    }

    if(i<tot&&p[i]+n<p[i+1])return ans[n]=f[i];

    if(i>tot/10*9)c[f[i]]++;

  }

  for(i=j=0;i<=n;i++)if(c[i]>c[j])j=i;

  for(i=0;i<=n;i++)if(i!=j&&c[i]*2>c[j])return ans[n]=0;

  return ans[n]=j;

}

int main(){

  for(v[1]=1,i=2;i<N;i++){

    if(!v[i])p[++tot]=i;

    for(j=1;j<=tot&&i*p[j]<N;j++){

      v[i*p[j]]=1;

      if(i%p[j]==0)break;

    }

  }

  for(i=0;i<E;i++)ans[i]=-1;

  scanf("%d",&T);

  while(T--){

    scanf("%d",&n);

    if(t=cal(n))printf("A %d\n",t);else puts("B");

  }

  return 0;

}

巴特西

BZOJ1423 : Optimus Prime

最新文章

热门文章