蓝桥杯2018年第九届真题-递增三元组

做法1：暴力枚举

首先考虑暴力做法，三个数组嵌套枚举，O(n3)的时间复杂度

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>


using namespace std;
using ll=long long;

const int N=1e5+10;

int a[N],b[N],c[N];
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;cin>>n;
  int res=0;
  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];
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      for(int k=1;k<=n;k++)
      {
        if(a[i]<b[j]&&b[j]<c[k])
        res++;
      }
    }
  }
  cout<<res;
  return 0;
}

尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。

//前缀和优化
#include <iostream>
#include <string.h>
using namespace std;
const int N=100005;
int n,a[N],b[N],c[N];
int cnt=0;
int num[N],s[N];
int as[N],cs[N];
int main(){
    cin>>n;//输入
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    //处理as
    for(int i=0;i<n;i++) num[a[i]]++;//  记录a[i]出现的次数

    for(int i=0;i<=N;i++) s[i]=s[i-1]+num[i];// 递推求得关于a[i]的所有前缀和s[i]

    for(int i=0;i<n;i++) as[i]=s[b[i]-1];// as代表比b[i]小的数的前缀和
    //还原数组
    memset(num,0,sizeof(num));
    memset(s,0,sizeof(s));

    //处理cs
    for(int i=0;i<n;i++) num[c[i]]++;//  记录c[i]出现的次数

    for(int i=0;i<=N;i++) s[i]=s[i-1]+num[i];//  递推求得关于c[i]的所有前缀和s[i]

    for(int i=0;i<n;i++) cs[i]=s[N]-s[b[i]];//  cs代表比b[i]大的数的前缀和；
    //注意不能是s[N-b[i]],这样求得的是从0到N-b[i]的前缀和，不是b[i]到N的前缀和

    //求结果
    long long res=0;//  数据量较大，用long long
    for(int i=0;i<n;i++)
    res+=(long long)as[i]*cs[i];
    cout<<res<<endl;
    return 0;
}