讨论 - T^T Online Judge

Rating定位赛（2）部分题解bulid by [正牌管理员]萌萌哒管理员 at 2015-07-20 22:11


萌萌哒管理员 Rating:978	A和D都是水题，就不说了 B题。。。假定l[i]表示数组中在a[i]前面且比a[i]小的数的个数，r[i]表示在数组中在a[i]后面且比a[i]大的数的个数，那么答案就可以计算了，用i和j表示Ab和Ac的位置，则这种情况的个数等于l[i]r[j]。然后用前缀和优化该式子可以达到O（N）。求l和r数组用树状数组或线段树，复杂度O（nlogn）。 E题。。。可以知道总情况个数是a^b，这么多情况中，没出现数字i的情况数是(a-1)^b，其他情况出现过i，可能多次但是只计算一次。所以总和就等于a^b-(a-1)^b( 1..n的和 ) 。以下内容于[2015-07-20 22:26:14]补充 #include<stdio.h> #include<algorithm> using namespace std; #define MAXLEN 50001 int c[MAXLEN],n; int A[50005]; int Lowbit(int x)//1<<k (k表示x在二进制下末尾0的个数) { return x&(-x); } /查询1~end的和/ int sum(int end) { int sum=0; while(end>0) { sum+=c[end]; end-=Lowbit(end); } return sum; } /将a[pos]的值加上num/ void update(int pos,int num) { while(pos<=n) { c[pos]+=num; pos+=Lowbit(pos); } } int l[50005]; int r[50005]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&A[i]); c[i]=0; } for(int i=0;i<n;i++){ update(A[i],1); l[i]=sum(A[i]-1); } for(int i=0;i<n;i++){c[i]=0;} for(int i=n-1;i>=0;i--){ update(A[i],1); r[i]=n-i-sum(A[i]-1)-1; } int sum=0; long long ans=0; for(int i=0;i<n;i++){ ans+=(long long)r[i]sum; //printf("%d %d %d*%d\n",l[i],r[i],r[i],sum); sum+=l[i]; } printf("%lld\n",ans); } return 0; }

Rating:978

A和D都是水题，就不说了
B题。。。假定l[i]表示数组中在a[i]前面且比a[i]小的数的个数，r[i]表示在数组中在a[i]后面且比a[i]大的数的个数，那么答案就可以计算了，用i和j表示Ab和Ac的位置，则这种情况的个数等于l[i]*r[j]。然后用前缀和优化该式子可以达到O（N）。求l和r数组用树状数组或线段树，复杂度O（n*logn）。

E题。。。可以知道总情况个数是a^b，这么多情况中，没出现数字i的情况数是(a-1)^b，其他情况出现过i，可能多次但是只计算一次。所以总和就等于a^b-(a-1)^b*( 1..n的和 ) 。

以下内容于[2015-07-20 22:26:14]补充

#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAXLEN 50001
int c[MAXLEN],n;
int A[50005];
int Lowbit(int x)//1<<k (k表示x在二进制下末尾0的个数)
{
    return x&(-x);
}
/*查询1~end的和*/
int sum(int end)
{
    int sum=0;
    while(end>0)
    {
        sum+=c[end];
        end-=Lowbit(end);
    }
    return sum;
}
/*将a[pos]的值加上num*/
void update(int pos,int num)
{
    while(pos<=n)
    {
        c[pos]+=num;
        pos+=Lowbit(pos);
    }
}
int l[50005];
int r[50005];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&A[i]);
            c[i]=0;
        }
        for(int i=0;i<n;i++){
            update(A[i],1);
            l[i]=sum(A[i]-1);
        }
        for(int i=0;i<n;i++){c[i]=0;}
        for(int i=n-1;i>=0;i--){
            update(A[i],1);
            r[i]=n-i-sum(A[i]-1)-1;
        }
        int sum=0;
        long long ans=0;
        for(int i=0;i<n;i++){
            ans+=(long long)r[i]*sum;
            //printf("%d %d %d*%d\n",l[i],r[i],r[i],sum);
            sum+=l[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}