您的位置: 首页  >  IT文章  >  POJ3378_Crazy Thairs

POJ3378_Crazy Thairs

分类: IT文章 • 2022-09-01 12:48:34

这个题目很有意思，也是一个很好的题目，涉及的知识点比较广，要求较高。

题目是这样的，给定你一个n个数的数列，问你有多少个长度为5的上升序列。

首先看到有50000，我们就知道肯定不会是DP。（但是不知道为什么我居然在DP优化这个章节里面做到了这个题）

由于给的数是在int范围里面的，我们需要首先将其离散化，这样相当于每个数的范围只有5000了。

剩下的就是这个题目的最最精华的地方了。

其实这里的统计是用树状数组来实现的。但是不是单单由一个树状数组实现的，而是5个。

什么意思呢？我们用f[i][j]表示不大于j的长度为i的上升序列有多少个。

这样就是一个递推了哦。而对于每一个查询我们都是通过树状数组来实现的，每次查询前面每一个长度，然后加入当前这个数字，这样每次操作的时间复杂度都是O(n*log(n))。

这样答案就呼之欲出了。

但是，你确定？

自己算一下就会发现，如果给你的数为50000个上升的数字，你的程序就直接跪了。

什么意思呢？你可以算一算，C(50000,5)> 2^64，也就是说超过了long long的范围。

这个嘛，有点那个啥。

不过我们可以这样做，保存和更新的只需要是长度为4的有多少个，C(50000,4)是不会超的。这样对于最后一次加法，直接用一个高精度数组保存答案和输出就可以了。

代码如下：

 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define maxn 50500
 6 #define M 1000000000
 7 using namespace std;
 8 
 9 typedef long long ll;
10 struct node{
11     ll num,pos;
12 }a[maxn];
13 
14 struct big{
15     ll b[20],top;
16     void Clear()
17     {
18         memset(b,0,sizeof b);
19         top=0;
20     }
21     void output()
22     {
23         printf("%I64d",b[top]);
24         for (ll i=top-1; i>=0; i--) printf("%09I64d",b[i]);
25         printf("
");
26     }
27     void Add(ll x)
28     {
29         ll cur=0;
30         while (x) b[cur++]+=x%M,x/=M;
31         for (ll i=0; i<top; i++) b[i+1]+=b[i]/M,b[i]%=M;
32         while (b[top]>=M) b[top+1]+=b[top]/M,b[top]%=M,top++;
33     }
34 }ans;
35 
36 
37 ll f[6][maxn],g[maxn];
38 ll n,tep;
39 
40 bool cmp(node n1,node n2) { return n1.num<n2.num; }
41 
42 void rankthem()
43 {
44     ll cur=0;
45     for (ll i=1; i<=n; i++)
46     {
47         if (a[i].num!=a[i-1].num) cur++;
48         g[a[i].pos]=cur;
49     }
50 }
51 
52 ll lowbit(ll x) { return x&(-x); }
53 
54 void add(ll u[],ll x,ll v) { while (x<maxn) u[x]+=v,x+=lowbit(x); }
55 
56 ll sum(ll u[],ll x)
57 {
58     ll tot=0;
59     while (x) tot+=u[x],x-=lowbit(x);
60     return tot;
61 }
62 
63 int main()
64 {
65     a[0].num=~0U>>1;
66     while (scanf("%I64d",&n)!=EOF)
67     {
68         ans.Clear();
69         for (ll i=1; i<=n; i++) scanf("%I64d",&a[i].num),a[i].pos=i;
70         sort(a+1,a+1+n,cmp);
71         rankthem();  
72         memset(f,0,sizeof f);
73         for (ll i=1; i<=n; i++)
74         {
75             ans.Add(sum(f[4],g[i]-1));
76             for (ll j=4; j>1; j--)
77             {
78                 tep=sum(f[j-1],g[i]-1); 
79                 add(f[j],g[i],tep);
80             }
81             add(f[1],g[i],1);
82         }
83         ans.output();
84     }  
85     return 0;
86 }

相关推荐