首页 > 代码库 > BZOJ3509: [CodeChef] COUNTARI
BZOJ3509: [CodeChef] COUNTARI
3509: [CodeChef] COUNTARI
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 339 Solved: 85
[Submit][Status]
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
3 5 3 6 3 4 10 4 5 2
Sample Output
9
题解:
Mektpoy:
分成N/size块
对于三个数在同一块内
可以暴力size^2
对于两个数在同一块内
可以和上面一起暴力size^2
对于中间的数在当前块内 别的两个数不在当前块内
将两边卷积value*log(value)
时间复杂度 O(N*size+N/size*value*log(value))
size取2600左右可以达到比较满意的时间
感觉n*size已经超了。。。居然可过。。。orz
代码参考了云神的,感觉自己又没代码能力,思路又捉鸡,还怎么混啊。。。
代码:
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 500000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 struct cp 61 { 62 double x,y; 63 cp operator +(cp b){return (cp){x+b.x,y+b.y};} 64 cp operator -(cp b){return (cp){x-b.x,y-b.y};} 65 cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};} 66 }; 67 int n,m,len,mx,num[maxn],l[maxn],r[maxn],st[maxn],ed[maxn],size,rev[maxn]; 68 cp a[maxn],b[maxn],c[maxn],y[maxn]; 69 const double PI=acos(-1.0); 70 void fft(cp *x,int n,int flag) 71 { 72 for0(i,n-1)y[rev[i]]=x[i]; 73 for0(i,n-1)x[i]=y[i]; 74 for(int m=2;m<=n;m<<=1) 75 { 76 cp wn=(cp){cos(2.0*PI/m*flag),sin(2.0*PI/m*flag)}; 77 for(int i=0;i<n;i+=m) 78 { 79 cp w=(cp){1,0};int mid=m>>1; 80 for0(j,mid-1) 81 { 82 cp u=x[i+j],v=x[i+j+mid]*w; 83 x[i+j]=u+v;x[i+j+mid]=u-v; 84 w=w*wn; 85 } 86 } 87 } 88 if(flag==-1)for0(i,n-1)x[i].x/=n; 89 } 90 91 int main() 92 93 { 94 95 freopen("input.txt","r",stdin); 96 97 freopen("output.txt","w",stdout); 98 99 n=read();100 for1(i,n)num[i]=read(),mx=max(num[i],mx),r[num[i]]++;101 mx++;mx=mx*2-1;m=1;102 while(m<=mx)m<<=1,len++;mx=m;103 for0(i,mx-1)104 {105 int x=i,y=0;106 for1(j,len)y<<=1,y|=x&1,x>>=1;107 rev[i]=y;108 }109 size=2000;m=(n-1)/size+1;110 for1(i,m)st[i]=ed[i-1]+1,ed[i]=i*size;111 ed[m]=n;112 ll ans=0;113 for1(i,m)114 {115 for2(j,st[i],ed[i])r[num[j]]--;116 for0(j,mx-1)a[j]=(cp){l[j],0};117 for0(j,mx-1)b[j]=(cp){r[j],0};118 fft(a,mx,1);fft(b,mx,1);119 for0(j,mx-1)c[j]=a[j]*b[j];120 fft(c,mx,-1);121 for2(j,st[i],ed[i])ans+=(ll)(c[2*num[j]].x+0.5);122 for2(j,st[i],ed[i])123 {124 for2(k,st[i],j-1)if(2*num[j]-num[k]>=0)ans+=r[2*num[j]-num[k]];125 for2(k,j+1,ed[i])if(2*num[j]-num[k]>=0)ans+=l[2*num[j]-num[k]];126 l[num[j]]++;127 }128 }129 cout<<ans<<endl;130 131 return 0;132 133 }
一堆j打成i我也是醉了。。。
BZOJ3509: [CodeChef] COUNTARI
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。