题解

38 条题解

  • 0
    @ 2015-10-24 11:14:22

    /*

    Author : Slience_K
    Belong : C++
    Pro : NOIP 2013 - 1 - 2

    */
    #include <cstdio>
    #include <algorithm>
    #define sz 100005
    #define LL long long
    using namespace std;
    struct Node{
    int data , pos;
    bool operator < ( const Node &x ) const {
    return data < x.data;
    }
    }a[ sz ] , b[ sz ];
    const int INF = 99999997;
    int n , data[ sz ] , temp[ sz ];
    LL ans;
    void Merge_sort( int l , int r ){
    if ( l >= r ) return;
    int mid = ( l + r ) >> 1 , s , t , len = l - 1;
    Merge_sort( l , mid );
    Merge_sort( mid + 1 , r );
    s = l , t = mid + 1;
    while( s <= mid && t <= r ){
    if ( data[ s ] <= data[ t ] ) temp[ ++len ] = data[ s++ ];
    else{

    temp[ ++len ] = data[ t ];
    ans = ( ans + ( LL )( mid - s + 1 ) ) % INF;
    t++;
    }
    }
    while( s <= mid ) temp[ ++len ] = data[ s++ ];
    while( t <= r ) temp[ ++len ] = data[ t++ ];
    for( int i = l ; i <= r ; i++ )
    data[ i ] = temp[ i ];
    }
    int main(){
    freopen( "match.in" , "r" , stdin );
    freopen( "match.out" , "w" , stdout );
    scanf( "%d" , &n );
    for( int i = 1 ; i <= n ; i++ ) {
    scanf( "%d" , &a[ i ].data );
    a[ i ].pos = i;
    b[ i ].pos = i;
    }

    for( int i = 1 ; i <= n ; i++ )
    scanf( "%d" , &b[ i ].data );
    sort( a + 1 , a + n + 1 );
    sort( b + 1 , b + n + 1 );
    for( int i = 1 ; i <= n ; i++ )
    b[ i ].data = a[ i ].pos;
    sort( b + 1 , b + n + 1 );
    for( int i = 1 ; i <= n ; i++ )
    data[ i ] = b[ i ].pos;
    ans = 0;
    Merge_sort( 1 , n );
    printf( "%I64d" , ans );
    fclose( stdin );
    fclose( stdout );
    return 0;
    }

  • 0
    @ 2015-10-08 16:33:44

    最后两个题解说的很好 想看题解的直接滚到最后去看吧 其他人写的题解不是很好

  • 0
    @ 2015-10-07 23:46:24

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    #define Mod 99999997
    #define N 100010
    int n;
    long long Ans=0;
    struct Node{
    int value;
    int id;
    bool operator < (const Node &a) const {
    return value<a.value;
    }
    }A[N],B[N];
    int f[N],sum[N];
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    inline int lowbit(int x)
    {
    return x&(-x);
    }
    void Update(int x)
    {
    for(int i=x;i<=n;i+=lowbit(i))
    sum[i]++;
    }
    int Get(int x)
    {
    int qwer=0;
    for(int i=x;i>=1;i-=lowbit(i))
    qwer+=sum[i];
    return qwer;
    }
    int main()
    {
    n=read();
    for(int i=1;i<=n;i++)
    {
    A[i].value=read();
    A[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
    B[i].value=read();
    B[i].id=i;
    }
    sort(A+1,A+n+1);
    sort(B+1,B+n+1);
    for(int i=1;i<=n;i++)
    {
    f[A[i].id]=B[i].id;
    }
    for(int i=1;i<=n;i++)
    {
    Update(f[i]);
    Ans=(Ans+i-Get(f[i]))%Mod;
    }
    cout<<Ans<<endl;
    return 0;
    }

  • 0
    @ 2015-09-30 11:28:53

    水水的A了
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    const int mod=99999997;
    struct node{ int data,num; };
    node temp[150000];
    int DiJiDa1[150000],DiJiDa2[150000],hash1[150000],F[150000],tmp[150000];
    int i,n,x,ans;

    bool cmp(node xx,node yy) { return (xx.data<yy.data); }
    /*-----------------------------------------------------------------------------*/
    void Prepare()
    {
    scanf("%d",&n);
    for (i=1; i<=n; i++)
    {
    scanf("%d",&x);
    temp[i].data=x;
    temp[i].num=i;
    }
    sort(temp+1,temp+n+1,cmp);
    for (i=1; i<=n; i++) DiJiDa1[temp[i].num]=i;
    for (i=1; i<=n; i++) hash1[DiJiDa1[i]]=i;

    for (i=1; i<=n; i++)
    {
    scanf("%d",&x);
    temp[i].data=x;
    temp[i].num=i;
    }

    sort(temp+1,temp+n+1,cmp);
    for (i=1; i<=n; i++) DiJiDa2[temp[i].num]=i;

    for (i=1; i<=n; i++) F[i]=hash1[DiJiDa2[i]];
    }
    /*-----------------------------------------------------------------------------*/
    void GB_sort(int L,int mid,int R)
    {
    int i=L,k=L,j=mid+1;
    while ((i<=mid)&&(j<=R))
    {
    if (F[i]<F[j]) tmp[k++]=F[i++]; else
    {
    tmp[k++]=F[j++];
    ans=((ans%mod)+((mid-i+1)%mod))%mod;
    }

    }
    while(i<=mid) tmp[k++]=F[i++];
    while(j<=R) tmp[k++]=F[j++];
    for(int p=L; p<=R; p++) F[p]=tmp[p];

    }
    /*-----------------------------------------------------------------------------*/
    void GB(int L,int R)
    {
    if (L<R)
    {
    int mid=(L+R)/2;
    GB(L,mid);
    GB(mid+1,R);
    GB_sort(L,mid,R);
    }
    }
    /*-----------------------------------------------------------------------------*/

    int main()
    {
    Prepare();
    GB(1,n);
    cout<<ans<<endl;
    }

  • 0
    @ 2015-06-10 22:52:52

    测试数据 #0: Accepted, time = 15 ms, mem = 3656 KiB, score = 10
    测试数据 #1: Accepted, time = 1 ms, mem = 3660 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 3656 KiB, score = 10
    测试数据 #3: Accepted, time = 9 ms, mem = 3660 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 3660 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 3660 KiB, score = 10
    测试数据 #6: Accepted, time = 106 ms, mem = 3656 KiB, score = 10
    测试数据 #7: Accepted, time = 187 ms, mem = 3656 KiB, score = 10
    测试数据 #8: Accepted, time = 484 ms, mem = 3660 KiB, score = 10
    测试数据 #9: Accepted, time = 765 ms, mem = 3660 KiB, score = 10
    Accepted, time = 1628 ms, mem = 3660 KiB, score = 100

    Code

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;

    #define MAXN 100005
    #define MOD 99999997
    int n,id[MAXN],_id[MAXN];
    long long ans;
    struct Match { int val,id,seq;} a[MAXN],b[MAXN];

    bool cmp1(Match A,Match B) { return A.val<B.val;}
    bool cmp2(Match A,Match B) { return A.seq<B.seq;}

    void Merge(int b1,int e1,int b2,int e2)
    {
    int bgn=b1,end=e2;
    int p=b1;
    while(b1<=e1 && b2<=e2)
    {
    if(id[b1]<id[b2]) { _id[p++]=id[b1++]; continue;}
    if(id[b1]>id[b2]) { _id[p++]=id[b2++]; ans+=(e1-b1+1); ans%=MOD; continue;}
    }
    if(b1>e1) while(b2<=e2) _id[p++]=id[b2++];
    if(b2>e2) while(b1<=e1) _id[p++]=id[b1++];

    for(int i=bgn;i<=end;i++)
    id[i]=_id[i];
    }

    void mergesort(int l,int r)
    {
    if(l<r)
    {
    int div=(l+r)/2;
    mergesort(l,div);
    mergesort(div+1,r);
    Merge(l,div,div+1,r);

    }
    }

    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].val, a[i].seq=i;
    for(int i=1;i<=n;i++) cin>>b[i].val, b[i].seq=i;
    sort(a+1,a+n+1,cmp1);
    sort(b+1,b+n+1,cmp1);
    for(int i=1;i<=n;i++) b[i].id=a[i].seq;
    //sort(a+1,a+n+1,cmp2);
    sort(b+1,b+n+1,cmp2);
    for(int i=1;i<=n;i++) id[i]=b[i].id;
    mergesort(1,n);
    cout<<ans%MOD<<endl;
    return 0;
    }

  • 0
    @ 2014-10-28 22:54:28

    先贪心 确定两个数组数字的对应关系 然后整合成一个数组 求数组中的逆序对个数 由于n可能到达100000的数据规模 需要Nlogn的复杂度 可以用树状数组或者归并排序的思想解决。其实n^2的算法由于数据生成随机也是有70分的。Orz

  • 0
    @ 2014-10-26 15:51:35

    记录信息
    评测状态 Accepted
    题目 P1842 火柴排队
    递交时间 2014-10-26 15:49:23
    代码语言 C++
    评测机 上海红茶馆
    消耗时间 654 ms
    消耗内存 2900 KiB
    评测时间 2014-10-26 15:49:24
    评测结果
    编译成功
    测试数据 #0: Accepted, time = 15 ms, mem = 2892 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 2896 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 2896 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 2892 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 2896 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 2900 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 2896 KiB, score = 10
    测试数据 #7: Accepted, time = 78 ms, mem = 2892 KiB, score = 10
    测试数据 #8: Accepted, time = 187 ms, mem = 2896 KiB, score = 10
    测试数据 #9: Accepted, time = 328 ms, mem = 2896 KiB, score = 10
    Accepted, time = 654 ms, mem = 2900 KiB, score = 100
    代码
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<string>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<cmath>
    #include<cctype>
    #define FOR(a,b) for(int i=a;i<=b;i++)
    using namespace std;
    struct hc
    {
    int num;
    int bh;
    }a[100001],b[100001];
    int n,ans=0;
    int c[100001];
    int tmp[100001];
    bool hcsort(const hc &a,const hc &b)
    {
    return a.num<b.num;
    }
    void init()
    {
    FOR(1,n)
    {
    cin>>a[i].num;
    a[i].bh=i;
    }
    FOR(1,n)
    {
    cin>>b[i].num;
    b[i].bh=i;
    }
    }
    void first()
    {
    sort(a+1,a+n+1,hcsort);
    sort(b+1,b+n+1,hcsort);
    FOR(1,n)
    c[a[i].bh]=b[i].bh;
    }
    void gbsort(int l,int m,int r)
    {
    int k=l;
    int lp=l;
    int rp=m+1;
    while(lp<=m&&rp<=r)
    {
    if(c[lp]>c[rp])
    {
    tmp[k++]=c[rp++];
    ans=(ans+(m-lp+1))%99999997;
    }
    else
    {
    tmp[k++]=c[lp++];
    }
    }
    FOR(lp,m) tmp[k++]=c[i];
    FOR(rp,r) tmp[k++]=c[i];
    FOR(l,r) c[i]=tmp[i];
    }
    void gb(int l,int r)
    {
    int m=(l+r)/2;
    if(l<r)
    {
    gb(l,m);
    gb(m+1,r);
    gbsort(l,m,r);
    }
    }
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n;
    init();
    first();
    gb(1,n);
    cout<<ans;
    return 0;
    }

  • 0
    @ 2014-09-04 13:00:15

    ###code
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <climits>
    using namespace std;
    int data1[1000000+5],data2[1000000+5],p1[1000000+5],p2[1000000+5],temp[100000+5];
    int len=0;
    int cnt=0;
    void mange(int,int,int);
    void mangesort(int,int);
    struct pii
    {
    int x;
    int y;
    bool operator <(const pii m) const
    {
    return x<m.x;
    }
    bool operator ==(const pii m) const
    {
    return x==m.x;
    }
    };
    pii l[1000000+5];
    int main()
    { cin>>len;
    for(int i=0;i!=len;++i)
    scanf("%d",&data1[i]);
    for(int i=0;i!=len;++i)
    scanf("%d",&data2[i]);
    memcpy(temp,data1,sizeof(int)*len);
    sort(temp,temp+len);
    for(int i=0;i!=len;++i)
    data1[i]=lower_bound(temp,temp+len,data1[i])-temp;
    memcpy(temp,data2,sizeof(int)*len);
    sort(temp,temp+len);
    for(int i=0;i!=len;++i)
    data2[i]=lower_bound(temp,temp+len,data2[i])-temp;
    for(int i=0;i!=len;++i)
    {
    pii t;
    t.x=data2[i];
    t.y=i;
    l[i]=t;
    }
    sort(l,l+len);
    for(int i=0;i!=len;++i)
    {
    pii t;
    t.x=data1[i];
    t.y=0;
    int p=lower_bound(l,l+len,t)-l;
    data1[i]=l[p].y;
    }
    mangesort(0,len-1);
    cout<<cnt<<endl;
    return 0;
    }

    void mangesort(int l,int r)
    {
    if(l<r)
    {
    int p=(l+r)/2;
    mangesort(l,p);
    mangesort(p+1,r);
    mange(l,p,r);
    }
    }

    void mange(int l,int p,int r)
    {
    int n1=p-l+1;
    int n2=r-p;
    int x=0;
    int *L=new int[n1+1];
    int *R=new int[n2+1];
    for(int i=l;i<=p;++i)
    L[x++]=data1[i];
    x=0;
    for(int i=p+1;i<=r;++i)
    R[x++]=data1[i];
    L[n1]=INT_MAX;
    R[n2]=INT_MAX;
    int px=0,py=0;
    for(int i=l;i<=r;++i)
    if(L[px]<R[py]) data1[i]=L[px++];
    else
    {
    data1[i]=R[py++];
    cnt+=n1-px;
    cnt%=99999997;
    }
    }

  • 0
    @ 2014-08-16 19:45:16

    //我是SkyDec大爷的脑残粉~~
    离散写得丑请无视~
    想复习一下归并所以没有写树状数组……

    #include<cstdio>
    #include<algorithm>
    using namespace std;

    const int Maxn=100000+19,Mod=99999997;
    struct note {int a,num;} A[Maxn],B[Maxn];
    int n,C[Maxn],rank[Maxn],tmp[Maxn],Ans;

    inline int cmp1(note A,note B) {return A.a<B.a;}
    inline int cmp2(note A,note B) {return A.num<B.num;}
    inline void Merge_sort(int L,int R)
    {
    if (L==R) return;
    int Mid=(L+R)>>1;
    Merge_sort(L,Mid);
    Merge_sort(Mid+1,R);
    int tl=L,tr=Mid+1,now=L;
    while (tl<=Mid&&tr<=R)
    {
    if (C[tl]<C[tr]) tmp[now++]=C[tl++];
    else
    {
    tmp[now++]=C[tr++];
    (Ans+=Mid-tl+1)%=Mod;
    }
    }
    while (tl<=Mid) tmp[now++]=C[tl++];
    while (tr<=R) tmp[now++]=C[tr++];
    for (int i=L;i<=R;i++) C[i]=tmp[i];
    }

    int main()
    {
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%d",&A[i].a),A[i].num=i;
    for (int i=0;i<n;i++) scanf("%d",&B[i].a),B[i].num=i;
    sort(A,A+n,cmp1);sort(B,B+n,cmp1);
    for (int i=0;i<n;i++) A[i].a=B[i].a=i;
    sort(A,A+n,cmp2);sort(B,B+n,cmp2);
    for (int i=0;i<n;i++) rank[A[i].a]=i;
    for (int i=0;i<n;i++) C[i]=rank[B[i].a];
    Merge_sort(0,n-1);
    printf("%d\n",Ans);
    }

  • 0
    @ 2014-08-10 23:14:30

    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>

    #define M 101011
    #define MOD 99999997
    #define INF 0x7fffffff

    using namespace std;

    int n;
    int a[M],b[M];
    int f[M];
    int flag[M];
    struct node
    {
    int w;
    int no;
    }str1[M],str2[M];

    struct node1
    {
    int a;
    int b;
    int num;
    }str3[M],str4[M];

    int cmp(const node &a,const node &b)
    {
    return a.w<b.w;
    }

    int cmp1(const node1 &a,const node1 &b)
    {
    return a.a<b.a;
    }

    int cmp2(const node1 &a,const node1 &b)
    {
    return a.b>b.b;
    }

    void init()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    int x;
    scanf("%d",&x);
    str1[i].w=x;
    str1[i].no=i;
    }
    for(int i=1;i<=n;i++)
    {
    int x;
    scanf("%d",&x);
    str2[i].w=x;
    str2[i].no=i;
    }
    sort(str1+1,str1+n+1,cmp);
    sort(str2+1,str2+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
    str3[i].a=str1[i].no;
    str3[i].b=str2[i].no;
    }
    sort(str3+1,str3+n+1,cmp1);
    for(int i=1;i<=n;i++)
    str3[i].num=i;
    for(int i=1;i<=n;i++)
    str4[i]=str3[i];
    sort(str4+1,str4+n+1,cmp2);
    for(int i=1;i<=n;i++)
    flag[i]=str4[i].num;
    }

    int lowbit(int x)
    {
    return x&(-x);
    }

    void add(int x,int w)
    {
    while(x<=n)
    {
    f[x]+=w;
    x+=lowbit(x);
    }
    }

    int getsum(int x)
    {
    int res=0;
    while(x>0)
    {
    res+=f[x];
    x-=lowbit(x);
    }
    return res;
    }

    void start()
    {
    for(int i=1;i<=n;i++)
    f[i]=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
    add(flag[i],1);
    sum=(sum+getsum(flag[i]-1))%MOD;
    }
    printf("%d\n",sum);
    }

    int main()
    {
    init();
    start();
    return 0;
    }

  • 0
    @ 2014-08-04 15:45:16

    ###为什么只有80分啊……
    #include <iostream>
    #include <cstring>
    using namespace std;
    long c[100001],d[100001];
    long s=0;
    void Qsort(long l,long r)
    {
    long i,j,k,mid;
    mid=c[(l+r)/2];
    i=l; j=r;
    while (i<=j){
    while (c[i]<mid) i++;
    while (c[j]>mid) j--;
    if (i<=j){
    k=c[i];
    c[i]=c[j];
    c[j]=k;
    k=d[i];
    d[i]=d[j];
    d[j]=k;
    i++;
    j--;
    }

    }
    if (l<j) Qsort(l,j);
    if (i<r) Qsort(i,r);
    }
    void sort(long l,long mid,long r)
    {
    long i,j,k;
    for (i=l;i<=mid;i++)
    for (j=r;j>=mid+1;j--){
    if (c[i]>c[j]){
    s=(s+j-mid)%99999997;
    break;
    }
    }
    i=l;
    j=mid+1;
    for (k=l;k<=r;k++){
    if ((c[i]<c[j] && i<=mid) || (j>r)){
    d[k]=c[i];
    i++;
    }else {
    d[k]=c[j];
    j++;
    }
    }
    for (i=l;i<=r;i++)
    c[i]=d[i];
    }
    void merge(long l,long r)
    {
    long mid;
    mid=(l+r)/2;
    if (l<mid) merge(l,mid);
    if (mid+1<r) merge(mid+1,r);
    sort(l,mid,r);
    }
    main()
    {
    long a1[100001],a2[100001],b1[100001],b2[100001],i,j,n;
    cin>>n;
    for (i=1;i<=n;i++){
    cin>>a1[i];
    b1[i]=b2[i]=i;
    }
    for (i=1;i<=n;i++) cin>>a2[i];
    memcpy(c,a1,sizeof(a1)); memcpy(d,b1,sizeof(b1));
    Qsort(1,n);
    memcpy(a1,c,sizeof(a1)); memcpy(b1,d,sizeof(b1));
    memcpy(c,a2,sizeof(a2)); memcpy(d,b2,sizeof(b2));
    Qsort(1,n);
    memcpy(a2,c,sizeof(a2)); memcpy(b2,d,sizeof(b1));
    for (i=1;i<=n;i++){
    a1[b1[i]]=i; a2[b2[i]]=i;
    }
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if (a1[i]==a2[j]){ a1[i]=j; break;}
    memcpy(c,a1,sizeof(c));
    merge(1,n);
    cout<<s;
    }

  • 0
    @ 2014-08-04 15:43:40

    为什么只有80分啊……
    #include <iostream>
    #include <cstring>
    using namespace std;
    long c[100001],d[100001];
    long s=0;
    void Qsort(long l,long r)
    {
    long i,j,k,mid;
    mid=c[(l+r)/2];
    i=l; j=r;
    while (i<=j){
    while (c[i]<mid) i++;
    while (c[j]>mid) j--;
    if (i<=j){
    k=c[i];
    c[i]=c[j];
    c[j]=k;
    k=d[i];
    d[i]=d[j];
    d[j]=k;
    i++;
    j--;
    }

    }
    if (l<j) Qsort(l,j);
    if (i<r) Qsort(i,r);
    }
    void sort(long l,long mid,long r)
    {
    long i,j,k;
    for (i=l;i<=mid;i++)
    for (j=r;j>=mid+1;j--){
    if (c[i]>c[j]){
    s=(s+j-mid)%99999997;
    break;
    }
    }
    i=l;
    j=mid+1;
    for (k=l;k<=r;k++){
    if ((c[i]<c[j] && i<=mid) || (j>r)){
    d[k]=c[i];
    i++;
    }else {
    d[k]=c[j];
    j++;
    }
    }
    for (i=l;i<=r;i++)
    c[i]=d[i];
    }
    void merge(long l,long r)
    {
    long mid;
    mid=(l+r)/2;
    if (l<mid) merge(l,mid);
    if (mid+1<r) merge(mid+1,r);
    sort(l,mid,r);
    }
    main()
    {
    long a1[100001],a2[100001],b1[100001],b2[100001],i,j,n;
    cin>>n;
    for (i=1;i<=n;i++){
    cin>>a1[i];
    b1[i]=b2[i]=i;
    }
    for (i=1;i<=n;i++) cin>>a2[i];
    memcpy(c,a1,sizeof(a1)); memcpy(d,b1,sizeof(b1));
    Qsort(1,n);
    memcpy(a1,c,sizeof(a1)); memcpy(b1,d,sizeof(b1));
    memcpy(c,a2,sizeof(a2)); memcpy(d,b2,sizeof(b2));
    Qsort(1,n);
    memcpy(a2,c,sizeof(a2)); memcpy(b2,d,sizeof(b1));
    for (i=1;i<=n;i++){
    a1[b1[i]]=i; a2[b2[i]]=i;
    }
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if (a1[i]==a2[j]){ a1[i]=j; break;}
    memcpy(c,a1,sizeof(c));
    merge(1,n);
    cout<<s;
    }

  • 0
    @ 2014-07-28 20:16:56

    代码奇短无比。
    楼下的skydec大爷说的很明白了。
    第一次交WA了,发现ans没开long long。
    第二次交又WA了,发现没取模。
    #include<cstdio>
    #include<map>
    #define L(x) (x&-x)
    using namespace std;
    map<int,int>Map;
    int f[1000005],n,x,i,now;long long ans=0;
    inline void add(int x) {for (;x<=n;x+=L(x)) f[x]++;}
    inline int ask(int x) {int s=0;for (;x;x-=L(x)) s+=f[x];return s;}

    int main()
    {
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    scanf("%d",&x),Map[x]=i;
    for (i=1;i<=n;i++)
    {
    scanf("%d",&x);now=Map[x];
    ans+=(long long)(i-1-ask(now));
    add(now);
    }
    printf("%I64d",ans%99999997);
    return 0;
    }

    • @ 2015-11-05 17:03:49

      这个代码有点厉害

  • 0
    @ 2014-07-14 21:10:36

    var a,b,c:array[0..100000]of longint;
    n,i,ans:longint;
    procedure ex(var x,y:longint);
    var t:longint;begin t:=x;x:=y;y:=t;end;
    procedure qs(l,r:longint);
    var i,j,m:longint;
    begin
    if l>=r then exit;
    i:=l;j:=r;m:=a[(i+j)>>1];
    repeat
    while a[i]<m do inc(i);
    while a[j]>m do dec(j);
    if i<=j then begin
    ex(a[i],a[j]);
    ex(c[i],c[j]);
    inc(i);dec(j);
    end;
    until i>j;
    qs(l,j);qs(i,r);
    end;
    function lb(k:longint):longint;
    begin exit(k and (-k));end;
    function sum(k:longint):longint;
    begin
    sum:=0;
    while k>0 do begin
    inc(sum,b[k]);
    dec(k,lb(k));
    end;
    end;
    procedure undata(k:longint);
    begin
    while k<=n do begin
    inc(b[k]);
    inc(k,lb(k));
    end;
    end;
    begin
    readln(n);
    for i:=1 to n do begin read(a[i]);c[i]:=i;end;
    qs(1,n);
    b:=c;
    for i:=1 to n do begin read(a[i]);c[i]:=i;end;
    qs(1,n);
    for i:=1 to n do a[b[i]]:=c[i];
    fillchar(b,sizeof(b),0);
    for i:=1 to n do begin
    undata(a[i]);
    inc(ans,i-sum(a[i]));
    ans:=ans mod 99999997;
    end;
    writeln(ans);
    end.

  • 0
    @ 2014-02-19 11:54:21

    用归并,预处理用数组hash。
    for i:=1 to n do f[a[i]]:=i;
    for i:=1 to n do a[i]:=f[aa[i]];
    for i:=1 to n do f[b[i]]:=i;
    for i:=1 to n do b[i]:=f[bb[i]];

  • 0
    @ 2014-02-14 22:33:42

    来之不易啊 一下午+一晚上
    const w=99999997;
    type arr=array[1..100000] of longint;
    var a,b,c,d,key,g:arr;
    i,n:longint;
    ans:int64;
    procedure merge(var a:arr;left,p,right:longint);
    var
    i,j,k:longint;
    tmp:arr;
    begin
    i:=left; j:=p+1; k:=left;
    while (i<=p) and (j<=right) do
    begin
    if a[i]<=a[j] then
    begin tmp[k]:=a[i]; inc(i); end
    else
    begin tmp[k]:=a[j]; ans:=ans+p-i+1; inc(j); end;
    inc(k);
    end;
    while i<=p do
    begin tmp[k]:=a[i];inc(i);inc(k);end;
    while j<=right do
    begin tmp[k]:=a[j];inc(j);inc(k);end;
    for i:=left to right do
    a[i]:=tmp[i];
    end;
    procedure mergesort(var a:arr;left,right:longint);
    var
    mid:longint;
    begin
    if left<right then
    begin
    mid:=(left+right) div 2;
    mergesort(a,left,mid);
    mergesort(a,mid+1,right);
    merge(a,left,mid,right);
    end;
    end;
    procedure qsort(var a:arr;h,l:longint);
    var i,j,m,temp:longint;
    begin
    i:=h;j:=l;m:=a[(i+j) div 2];
    repeat
    while a[i]<m do inc(i);
    while a[j]>m do dec(j);
    if i<=j then
    begin
    temp:=a[i];a[i]:=a[j];a[j]:=temp;
    temp:=g[i];g[i]:=g[j];g[j]:=temp;
    inc(i);dec(j);
    end;
    until i>j;
    if i<l then qsort(a,i,l);
    if j>h then qsort(a,h,j);
    end;
    begin
    readln(n);
    for i:=1 to n do read(c[i]);
    readln;
    for i:=1 to n do read(d[i]);
    for i:=1 to n do g[i]:=i;
    qsort(c,1,n);
    for i:=1 to n do c[g[i]]:=i;
    for i:=1 to n do g[i]:=i;
    qsort(d,1,n);
    for i:=1 to n do d[g[i]]:=i;
    for i:=1 to n do key[d[i]]:=i;
    for i:=1 to n do c[i]:=key[c[i]];
    ans:=0;
    mergesort(c,1,n);
    writeln(ans mod w);
    end.

  • 0
    @ 2013-12-13 18:27:19

    用 BIT 实现的逆序对
    什么你要题解?楼下两位已经说得很明白了~

    #include <stdio.h>
    #include <stdlib.h>

    #define MAXN 100010
    #define lowbit(x) (x & (-x))

    typedef struct {
    int data, no;
    } node;

    node a[MAXN], b[MAXN];
    int tr[MAXN], c[MAXN];
    int n;

    int cmp(const void *a, const void *b) {
    node *aa = (node *)a;
    node *bb = (node *)b;
    if (aa->data == bb->data) {
    return (aa->no - bb->no);
    } else {
    return (aa->data - bb->data);
    }
    }

    void update(int p, int value) {
    int i;

    for(i = p; i <= n; i += lowbit(i)) {
    tr[i] += value;
    }
    }

    int getsum(int p) {
    int i, tmp = 0;

    for (i = p; i > 0; i -= lowbit(i)) {
    tmp += tr[i];
    }
    return tmp;
    }

    int main() {
    int i, ans = 0;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
    scanf("%d", &a[i].data);
    a[i].no = i + 1;
    }
    for (i = 0; i < n; i++) {
    scanf("%d", &b[i].data);
    b[i].no = i + 1;
    }
    qsort(a, n, sizeof(a[0]), cmp);
    qsort(b, n, sizeof(b[0]), cmp);
    for (i = 0; i < n; i++) {
    c[b[i].no] = a[i].no;
    }
    for (i = 1; i <= n; i++) {
    update(c[i], 1);
    ans = (ans + i - getsum(c[i])) % 99999997;
    }
    printf("%d\n", ans);
    return 0;
    }

  • 0
    @ 2013-11-18 18:28:46

    首先把那个式子拆开,用排序不等式貌似可以发现最小值就是先对两个火柴的高度a[],b[]排序,然后对于每一个a[i],只要跟b[i]在一起就是最小的。
    所以我们要做的工作就剩下计算移动量。
    弱菜没想到逆序对,更没想到归并排序...直接模拟,我们从1到n,对于每一个a[i],找到其排序后对应的b[k],显然我们可以不动a[i],只移动b[k]到b[i]处,这样子显然是步数最小的。所以答案就加上k-i,但是移动之后b[k]之前的,b[i]之后的点的坐标都会加1,这个看起来就像树状数组的区间加减,然后每一次只要求单点的值就可以了...然后咱就用树状数组维护每一次移动之后所有点应该在的位置。这样子复杂度就是O(NlogN)的.....

信息

ID
1842
难度
7
分类
(无)
标签
递交数
5085
已通过
1102
通过率
22%
被复制
10
上传者