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]<num[z]<num[y]且x<y<z,当中x,y,z为这三个数字的下标。
|
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<j<k且num[i]<num[k]<num[j]的总组数利用树状数组能够求出一个数前面比它小的数的个数,进而能够知道前面比它大的数的个数,总的比它大的个数减去前面比它大的个数等于后面比它大的个数,Cn2 = x*(x-1)/2;
然后肯定要减去后面的全部组成的i<j<k且a[i]<a[j]<a[k]的个数;
- 能够先求出(xyz,xzy)的总数量
- 仅仅需出去x后面多少个比它大的个数n,C(n,2)就是了
- 然后求出xyz的个数,
- 对于a,求出比a小的个数low[a],比a大的个数high[a],low[a]*high[a]就是答案
- 能够借助树状数组求上述个数
注意了,总体求解!
并非说单独考虑某个数
#include <iostream> #include <cstring> #include <cstdio> 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 #"<<Case++<<": "<<ans%mod<<endl; } return 0; }
|
版权声明:本文博主原创文章,博客,未经同意不得转载。