BZOJ5177 : [Jsoi2013]贪心的导游-爱分乐赚

爱分乐赚网站开发是一个面向开发者的知识分享社区。这里集合了网站开发所需要用到的各类网站开发教程。包括(JavaScript 入门教程,TypeScript 入门教程,Vue 入门教程,Ajax 入门教程,ES6-10 入门教程,Yarn 入门教程,ECharts 入门教程,CSS3 入门教程,雪碧图入门教程,移动端布局教程,Html5 入门教程,Sass 入门教程,HTML 入门教程,uni-app 入门教程,Nginx 入门教程,HTTP 入门教程,Docker 入门教程,Shell 入门教程,Linux 入门教程,Gradle 入门教程,Vim 编辑器教程,RESTful 规范教程,Dreamweaver 教程,Markdown 入门教程,Maven 入门教程,Eclipse 编辑器教程,GitHub 入门教程,Android Studio 编辑器教程,PyCharm 编辑器教程,Sublime Text 使用教程,Postman 教程,Python 原生爬虫教程)

首先预处理出对于每个模数,所有被模数按结果从大到小排序的结果,那么对于一个询问,如果可以在$O(1)$时间内判断某个数字是否出现,则可以$O(1000)$回答。

考虑对序列进行分治,对于区间$[l,r]$,取$mid=lfloorfrac{l+r}{2}
floor$。

处理出$mid$到$[l,r]$内每个位置里每个数字的出现次数,回答所有经过$mid$的询问,然后递归分治$[l,mid)$和$(mid,r]$。

时间复杂度$O((n+m)log n+1000m)$。

 

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000010,M=50010,K=1010,BUF=9000000;
char Buf[BUF],*buf=Buf;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
int n,m,i,j,x,y,a[N],gl[N],gr[N],v[M<<1],nxt[M<<1],ed,b[K],q[K][K];bool c[K];
struct E{int x,y,p,l,r;}e[M];
inline bool cmp(int x,int y){return b[x]>b[y];}
inline void add(int&x,int y){v[++ed]=y;nxt[ed]=x;x=ed;}
inline void check(int x,int l,int r,int&y){
  if(~y||e[x].x>l||e[x].y<r)return;
  for(int i=0,p=e[x].p;;i++)if(c[q[p][i]]){y=q[p][i]%p;return;}
}
void solve(int l,int r){
  if(l>r)return;
  int mid=(l+r)>>1,i,j;
  for(i=mid;i>=l;i--)for(c[a[i]]=1,j=gl[i];j;j=nxt[j])check(v[j],i,mid,e[v[j]].l);
  for(i=mid;i>=l;i--)c[a[i]]=0;
  for(i=mid;i<=r;i++)for(c[a[i]]=1,j=gr[i];j;j=nxt[j])check(v[j],mid,i,e[v[j]].r);
  for(i=mid;i<=r;i++)c[a[i]]=0;
  solve(l,mid-1),solve(mid+1,r);
}
int main(){
  fread(Buf,1,BUF,stdin);read(n),read(m);
  for(i=1;i<=n;i++)read(a[i]);
  for(i=1;i<=m;i++){
    read(x),read(y);
    if(x>y)swap(x,y);
    add(gl[e[i].x=x+1],i),add(gr[e[i].y=y+1],i);
    read(e[i].p),e[i].l=e[i].r=-1;
  }
  for(i=2;i<=1000;i++){
    for(j=0;j<=1000;j++)b[j]=j%i,q[i][j]=j;
    sort(q[i],q[i]+1001,cmp);
  }
  solve(1,n);
  for(i=1;i<=m;i++)printf("%d
",max(e[i].l,e[i].r));
  return 0;
}

  

本文转自:https://www.cnblogs.com/clrs97/p/8614937.html

----------------

微信扫一扫,分享到朋友圈

BZOJ5177 : [Jsoi2013]贪心的导游-爱分乐赚
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close