hdu4000 && hrbust1625 - c++编程基础

ikki的数字

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 22(12 users)

Total Accepted: 9(8 users)

Rating:

Special Judge: No

Description

ikki 最近对数字颇感兴趣。现在ikki在纸上写了连续的N个数字，每个数字都是[1,N]之间任意的一个数而且不重复，即这串数字

是数字1~N的一个排列，数字的序号从1到N，现在ikki想考你一下：

在这N个数字中能找出多少个3个数的组合满足:num[x]

Input

多组测试数据，第一行一个整数T 表示测试数据的个数。

对于每组数据，第一行输入一个整数N表示数列中数字的个数（1<=N<=5000）

第二行输入N个数字表示一个1~N的排列。

Output

对于每组数据，输出”Case #k: p” ,k表示第k组样例，p表示满足要求的3个数字的组合数目，每组输出占一行。

由于结果可能比较大，结果需对100000007取模。

Sample Input

2
6
1 3 2 6 5 4
5
3 5 2 4 1

Sample Output

Case #1: 10
Case #2: 1

Author

周洲@hrbust

隐藏着树状数组~~~根本没看出来，其实主要是没思路，思路出来了才能用树状数组求解

判断满足i

可以先求出（xyz，xzy)的总数量
只需出去x后面多少个比它大的个数n，C(n,2)就是了
然后求出xyz的个数，
对于a，求出比a小的个数low[a],比a大的个数high[a],low[a]*high[a]就是答案

可以借助树状数组求上述个数注意了，整体求解！并不是说单独考虑某个数

#include 
         
          
#include 
          
            #include 
           
             using namespace std; typedef long long LL; const int mod = 100000007; int T,n; int c[5010]; int lowbit(int x) { return x & -x; } LL getsum(int x) { LL sum = 0; while(x > 0) { sum += c[x]; x -= lowbit(x); } return sum; } void update(int x , int val) { while(x <= n) { c[x] += val; x += lowbit(x); } } int main() { #ifdef xxz freopen("in.txt","r",stdin); #endif // xxz cin>>T; int Case = 1; while(T--) { memset(c,0,sizeof(c)); cin>>n; LL ans = 0; for(int i = 1; i <= n; i++) { int temp; cin>>temp; update(temp,1); LL presmaller = getsum(temp - 1); LL prebigger = i-1 - presmaller; LL totbigger = n - temp; LL afterbigger = totbigger - prebigger; ans -= presmaller * afterbigger; if(afterbigger >= 2) { ans += afterbigger*(afterbigger - 1)/2; } } cout<<"Case #"<