注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3509][CodeChef] COUNTARI  

2015-05-14 14:50:11|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3509: [CodeChef] COUNTARI

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 385  Solved: 104
[Submit][Status][Discuss]

Description

给定一个长度为N的数组A[],求有多少对i, j, k(1<=i<j<k<=N)满足A[k]-A[j]=A[j]-A[i]。

Input

第一行一个整数N(N<=10^5)。
接下来一行N个数A[i](A[i]<=30000)。

Output

一行一个整数。

Sample Input

10 3 5 3 6 3 4 10 4 5 2

Sample Output

9

Solution

将序列分成大小为size的块,如果三个点有两个点在块内的话就size^2暴力统计,如果三个点都在不同块的话,枚举中间点在哪个块内,左右两边FFT,然后扫一遍当前的块看看能贡献多少答案。
我去CC上面找了一下原题,发现(跑得快的,代码短的)都是暴力优化比如什么链表啦二分啦压位啦2333
只能说数据不太靠谱

Code

/**************************************************************
    Problem: 3509
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:24188 ms
    Memory:6808 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
typedef double ld;ld pi=acos(-1);
struct P{ld x,y;}tmp;
#define PP const P&
P operator+(PP a,PP b){return (P){a.x+b.x,a.y+b.y};}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
P operator*(PP a,PP b){return (P){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
P operator/(PP a,ld b){return (P){a.x/b,a.y/b};}
#define N 66666
int n,m,a[100010],rev[N],i,j,k,v,siz,len,p1[N],p2[N],p3[N],l,r,id[100010];
long long ans;
P w[2][N],x[N],y[N];
void FFT(P*a,int n,P*w){int i,j,k;
    for(i=0;i<n;i++)if(i<rev[i])tmp=a[i],a[i]=a[rev[i]],a[rev[i]]=tmp;
    for(i=2;i<=n;i<<=1)
    for(j=0;j<n;j+=i)
    for(k=0;k<i>>1;k++)
    tmp=a[j+k+i/2]*w[n/i*k],a[j+k+i/2]=a[j+k]-tmp,a[j+k]=a[j+k]+tmp;
}
void mul(){
    for(int i=0;i<n;i++)x[i]=(P){p1[i],0},y[i]=(P){p2[i],0};
    FFT(x,n,w[0]),FFT(y,n,w[0]);
    for(int i=0;i<n;i++)x[i]=x[i]*y[i];
    FFT(x,n,w[1]);
    for(int i=0;i<n;i++)p3[i]=x[i].x/n+0.5;
}
int main(){
    for(scanf("%d",&m),siz=8*sqrt(m),i=0;i<m;i++)scanf("%d",a+i),v<a[i]?v=a[i]:1,id[i]=i/siz,p2[a[i]]++;
    for(n=1;n<v;n<<=1,len++);n<<=1;
    for(i=0;i<=n;i++)w[1][n-i]=w[0][i]=(P){cos(pi*2*i/n),sin(pi*2*i/n)},rev[i]=(rev[i>>1]>>1)|((i&1)<<len);
    for(i=0;i<=id[m-1];i++){
        l=i*siz,r=l+siz-1;if(r>m-1)r=m-1;
        for(j=l;j<=r;p1[a[j]]++,p2[a[j]]--,j++)
        for(k=j+1;k<=r;k++)
        if(a[j]*2>=a[k])ans+=p1[a[j]*2-a[k]];
        for(j=l;j<=r;j++)
        for(k=j-1;k>=l;k--)
        if(a[j]*2>=a[k])ans+=p2[a[j]*2-a[k]];
    }
    for(i=id[m-1];i>=0;i--){
        l=i*siz,r=l+siz-1;if(r>m-1)r=m-1;
        for(j=l;j<=r;j++)p1[a[j]]--;
        mul();
        for(j=l;j<=r;j++)ans+=p3[a[j]*2],p2[a[j]]++;
    }
    printf("%lld\n",ans);
}
  评论这张
 
阅读(90)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018