首页 > 代码库 > HDU4000Fruit Ninja【树状数组+组合数】

HDU4000Fruit Ninja【树状数组+组合数】

2024-07-27 18:19:41   222人阅读

大意：

告诉你一个有n个数的序列 （1 -- n） 问其中有多少组 （a[i], a[j], a[k]) 满足i < j < k 并且 a[i] < a[k] < a[j]

 

分析：

这个题跟那个中间为峰值的题很像   我的第一反应为树状数组

求的就是在这个序列当中  小大中 一共会出现多少次

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

（小中大 + 小大中） 也就是说只要前面这个数是小的  后面的大的数中任取两个就可以了

用两个数组来维护

一个qian[]用来存前边有多少个小于这个数  另一个hou[]维护后面有多少个大于这个数

小中大的个数就是  sum（qian[i] * hou[i]）==

求小XX的过程中我脑袋抽筋了

我一开始用的是这种思路

对于每一位

用比它小的个数 * （C（大于它的g个数， 2））  

看起来貌似很合理

但是其实有个严重的问题

在求小中大的过程我们可以那么考虑是因为中间的是唯一的

所以无论我们怎么成都不会重复

但是这个若只是考虑小于它的和大于等于它的想成就会出现重复的

怎么避免重复呢

只要按照求小中大的思路

我们可以确定一个最小的  那么  之后的就是以这个为基准的 而不会出现重复

小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

 

HDU4000Fruit Ninja【树状数组+组合数】


联系
我们