您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)ACwing中怎么遞增三元組,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個參考,希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。
前綴和處理
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; int n; int a[N],b[N],c[N]; int af[N],cf[N];//af[i] cf[i] 用于存儲比b[i]小的a的個數(shù);比b[i]大的c的個數(shù) int cnt[N],f[N]; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i],a[i]++; for(int i=0;i<n;i++) cin>>b[i],b[i]++; for(int i=0;i<n;i++) cin>>c[i],c[i]++; //求af for(int i=0;i<n;i++) cnt[a[i]]++; for(int i=1;i<N;i++) f[i]=f[i-1]+cnt[i]; for(int i=0;i<n;i++) af[i]=f[b[i]-1]; //清空cnt[]和f[] memset(cnt,0,sizeof cnt); memset(f,0,sizeof f); //求cf for(int i=0;i<n;i++) cnt[c[i]]++; for(int i=1;i<N;i++) f[i]=f[i-1]+cnt[i]; for(int i=0;i<n;i++) cf[i]=f[N-1]-f[b[i]]; //枚舉每個b[i] long long res=0; for(int i=0;i<n;i++){ res=res+(long long)af[i]*cf[i]; } cout<<res<<endl; return 0; }
sort+二分
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; int a[N],b[N],c[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) cin>>c[i]; //排序 sort(a+1,a+n+1); sort(b+1,b+n+1); sort(c+1,c+n+1); long long res=0; //二分 (二分查找到ans時,一定有l(wèi)==r) //枚舉每一個b 查找對應(yīng)a c個數(shù) for(int i=1;i<=n;i++){ //存循環(huán)變量 int bj=b[i]; int l=1,r=n; //對a[i] while(l<r){ int m=(l+r+1)>>1; //左類 if(a[m]<bj){ l=m; } else { r=m-1; } } int ai=0; if(a[l]<bj){ ai=l; } //對c[k] l=1,r=n; while(l<r){ int m=(l+r)>>1; //右類 if(c[m]>bj) r=m; else l=m+1; } int ck=0; //二分查找到ans時,一定有l(wèi)==r if(c[l]>bj) ck=n-l+1; res+=(long long)ai*ck; } cout<<res<<endl; return 0; }
關(guān)于ACwing中怎么遞增三元組就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,可以學(xué)到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。