本文主要是介绍蓝桥集训之递增三元组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓝桥集训之递增三元组
-
核心思想：前缀和
- 因为b是中间数 遍历b时 ac没有约束关系
- 所以遍历b 然后求出a有多少比b小的 c有多少比b大的 a*c即可
- 用哈希表将a[i]中每个数出现次数记录
- 求其前缀 得到s[i]为**<=i的个数**
- 分别用as和cs记录比b[i]小的数的个数 简化代码
-
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int a[N],b[N],c[N];int as[N],cs[N];int cnt[N],s[N]; //前缀和数组int main(){int n;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]++;for(int i=0;i<n;i++) cnt[a[i]] ++; //哈希表记录每个数出现次数for(int i=1;i<N;i++) s[i] = s[i-1] + cnt[i]; //求前缀 s[i]表示<=i的数的个数for(int i=0;i<n;i++) as[i] = s[b[i] - 1]; //as[i]表示对应小于b[i]的元素个数memset(cnt,0,sizeof cnt);memset(s,0,sizeof s);for(int i=0;i<n;i++) cnt[c[i]] ++;for(int i=1;i<N;i++) s[i] = s[i-1] + cnt[i];for(int i=0;i<n;i++) cs[i] = s[N-1] - s[b[i]]; //cs[i]表示对应大于b[i]的元素个数LL res=0;for(int i=0;i<n;i++) res += (LL)as[i] * cs[i]; //可能爆intcout<<res;}
这篇关于蓝桥集训之递增三元组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
