大意：

告訴你一個(gè)有n個(gè)數(shù)的序列 （1 -- n） 問(wèn)其中有多少組 （a[i], a[j], a[k]) 滿足i < j < k 并且 a[i] < a[k] < a[j]

?

分析：

這個(gè)題跟那個(gè)中間為峰值的題很像 ? 我的第一反應(yīng)為樹狀數(shù)組

求的就是在這個(gè)序列當(dāng)中 ?小大中 一共會(huì)出現(xiàn)多少次

小大中 = （小中大 + 小大中） — 小中大

（小中大 + 小大中） 也就是說(shuō)只要前面這個(gè)數(shù)是小的 ?后面的大的數(shù)中任取兩個(gè)就可以了

用兩個(gè)數(shù)組來(lái)維護(hù)

一個(gè)qian[]用來(lái)存前邊有多少個(gè)小于這個(gè)數(shù) ?另一個(gè)hou[]維護(hù)后面有多少個(gè)大于這個(gè)數(shù)

小中大的個(gè)數(shù)就是 ?sum（qian[i] * hou[i]）==

求小XX的過(guò)程中我腦袋抽筋了

我一開始用的是這種思路

對(duì)于每一位

用比它小的個(gè)數(shù) * （C（大于它的g個(gè)數(shù)， 2）） ?

看起來(lái)貌似很合理

但是其實(shí)有個(gè)嚴(yán)重的問(wèn)題

在求小中大的過(guò)程我們可以那么考慮是因?yàn)橹虚g的是唯一的

所以無(wú)論我們?cè)趺闯啥疾粫?huì)重復(fù)

但是這個(gè)若只是考慮小于它的和大于等于它的想成就會(huì)出現(xiàn)重復(fù)的

怎么避免重復(fù)呢

只要按照求小中大的思路

我們可以確定一個(gè)最小的 ?那么 ?之后的就是以這個(gè)為基準(zhǔn)的 而不會(huì)出現(xiàn)重復(fù)

小XX = sum（C（大于該位， 2） ）；

?

代碼：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const long long maxn = 100005; 7 const long long mod = 100000007; 8 long long c[maxn]; 9 long long n, a[maxn]; 10 long long qian[maxn], hou[maxn], hh[maxn]; 11 12 long long lowbit(long long x) { 13 return x & ( - x ) ; 14 } 15 16 void add(long long i) { 17 while(i <= n) { 18 c[i] += 1; 19 i += lowbit(i); 20 } 21 } 22 23 long long sum(long long i) { 24 long long s = 0; 25 while(i > 0) { 26 s += c[i]; 27 i -= lowbit(i); 28 } 29 return s; 30 } 31 32 void init() { 33 memset(c, 0, sizeof(c)); 34 for(long long i = 1; i <= n; i++) { 35 qian[i] = sum(a[i]); 36 add(a[i]); 37 } 38 memset(c, 0, sizeof(c)); 39 for(long long i = n; i >= 1; i--) { 40 add(a[i]); 41 hou[i] = n - i + 1 - sum(a[i]); 42 } 43 } 44 45 int main() { 46 long long t; 47 scanf("%I64d",&t); 48 for(long long kase = 1; kase <= t; kase++) { 49 scanf("%I64d",&n); 50 for(long long i = 1; i <= n; i++) scanf("%I64d",&a[i]); 51 init(); 52 long long sum1 = 0; 53 for(long long i = 1; i <= n; i++) { 54 sum1 += qian[i] * hou[i]; 55 sum1 %= mod; 56 } 57 long long sum2 = 0; 58 for(long long i = 1; i <= n; i++) { 59 sum2 += (hou[i] * (hou[i] - 1) / 2); 60 sum2 %= mod; 61 } 62 printf("Case #%I64d: ", kase); 63 long long ans = (sum2 - sum1 + mod) % mod; 64 printf("%I64d\n", ans); 65 } 66 return 0; 67 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhanzhao/p/4031933.html

總結(jié)

以上是生活随笔為你收集整理的HDU4000Fruit Ninja【树状数组+组合数】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。