题解

10 条题解

  • 4
    @ 2017-10-02 21:19:15

    复杂度: O(n^2).

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 5010;
    int a[maxn];
    
    int main() {
        ios::sync_with_stdio(false);
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        long long res = 0;
        for (int i = 1; i <= n; i++) {
            long long sum1 = 0, sum2 = 0;
            for (int j = 1; j < i; j++) {
                sum1 += (a[j] < a[i]);
            }
            for (int j = i + 1; j <= n; j++) {
                sum2 += (a[i] < a[j]);
            }
            res += sum1 * sum2;
        }
        cout << res << endl;
        return 0;
    }
    
  • 1
    @ 2021-01-07 20:38:54
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        typedef long long ll;
        
        ll n,a[1<<13];
        
        void main()
        {
            scanf("%lld",&n);
            for (ll i=0;i<n;i++)
                scanf("%lld",&a[i]);
            ll ans=0;
            for (ll i=0;i<n;i++)
            {
                ll cntl=0,cntr=0;
                for (ll j=0;j<i;j++)
                    if (a[j]<a[i])
                        cntl++;
                for (ll j=i;j<n;j++)
                    if (a[i]<a[j])
                        cntr++;
                ans+=cntl*cntr;
            }
            printf("%lld\n",ans);
        }
    };
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2015-01-16 21:11:04

    千万注意最终结果要开longlong....

  • -2
    @ 2014-10-02 14:22:26

    program p1768;
    var
    a:array[1..5000]of longint;
    b,c,i,j,n:longint;
    ans:int64;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=2 to n-1 do begin
    b:=0;c:=0;
    for j:=1 to i-1 do if a[j]<a[i] then inc(b);
    for j:=i+1 to n do if a[j]>a[i] then inc(c);
    ans:=ans+b*c;
    end;
    writeln(ans);
    end.
    呵呵

  • -3
    @ 2016-06-10 19:36:32

    暴力主席树:
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    int i,j,k,n,m,s,t;
    ll ans;
    int root[5005];
    struct node
    {
    int lson,rson,sum;
    } tree[5005*20];
    int a[100005];
    int b[100005];
    int tot,num,cnt;
    void change(int l,int r,int &p,int x)
    {
    tree[++cnt] = tree[p];
    p = cnt;
    tree[p].sum++;
    if (l==r) return;
    int mid = (l+r)>>1;
    if (mid>=x) change(l,mid,tree[p].lson,x);
    else change(mid+1,r,tree[p].rson,x);
    }
    ll ask(int X,int Y,int l,int r,int x,int y)
    {
    if (l==x&&y==r) return tree[Y].sum-tree[X].sum;
    int mid = (l+r)>>1;
    if (mid>=y) return ask(tree[X].lson,tree[Y].lson,l,mid,x,y);
    else if (mid+1<=x) return ask(tree[X].rson,tree[Y].rson,mid+1,r,x,y);
    else return ask(tree[X].lson,tree[Y].lson,l,mid,x,mid)+ask(tree[X].rson,tree[Y].rson,mid+1,r,mid+1,y);
    }
    int main()
    {
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    b[++tot] = a[i];
    }
    sort(b+1,b+1+n);
    tot = unique(b+1,b+1+n)-b-1;
    for (int i=1;i<=n;i++) a[i] = lower_bound(b+1,b+1+n,a[i])-b;
    for (int i=1;i<=n;i++)
    {
    root[i] = root[i-1];
    change(1,tot,root[i],a[i]);
    }
    for (int i=1;i<n;i++)
    for (int j=i+1;j<=n;j++)
    if (a[i]+1<=a[j]-1) ans += ask(root[i-1],root[j],1,tot,a[i]+1,a[j]-1);
    cout<<ans<<endl;
    return 0;
    }

  • -3
    @ 2014-12-06 11:09:50

    P1768顺序对的值
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1768 顺序对的值
    递交时间 2014-12-06 11:09:23
    代码语言 C++
    评测机 VijosEx
    消耗时间 2836 ms
    消耗内存 98228 KiB
    评测时间 2014-12-06 11:09:28

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 98220 KiB, score = 10

    测试数据 #1: Accepted, time = 156 ms, mem = 98220 KiB, score = 10

    测试数据 #2: Accepted, time = 234 ms, mem = 98228 KiB, score = 10

    测试数据 #3: Accepted, time = 327 ms, mem = 98228 KiB, score = 10

    测试数据 #4: Accepted, time = 312 ms, mem = 98228 KiB, score = 10

    测试数据 #5: Accepted, time = 405 ms, mem = 98228 KiB, score = 10

    测试数据 #6: Accepted, time = 374 ms, mem = 98228 KiB, score = 10

    测试数据 #7: Accepted, time = 374 ms, mem = 98224 KiB, score = 10

    测试数据 #8: Accepted, time = 343 ms, mem = 98228 KiB, score = 10

    测试数据 #9: Accepted, time = 296 ms, mem = 98228 KiB, score = 10

    Accepted, time = 2836 ms, mem = 98228 KiB, score = 100

    代码

    #include <iostream>
    #include <cmath>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    int n;
    int i , j;
    int a[5000 + 2];
    int f[5000 + 2][5000 + 2];
    unsigned long long ans;

    int glc( int t[] , int l , int r )
    {
    return t[r] - t[l];
    }

    int main()
    {
    ans = 0;
    scanf( "%d" , &n );
    for( i = 0 ; i < n ; i++ )
    scanf( "%d" , &a[i] );
    for( i = 0 ; i < n ; i++ )
    {
    f[i][0] = ( a[0] < a[i] );
    for( j = 1 ; j < n ; j++ )
    f[i][j] = f[i][j - 1] + ( a[j] < a[i] );

    }
    for( i = 0 ; i < n ; i++ )
    for( j = i + 1 ; j < n ; j++ )
    if( a[j] > a[i] )
    ans += glc( f[j] , i , j ) - glc( f[i] , i - 1 , j );
    cout << ans << endl;
    return 0;
    }

  • -3
    @ 2013-07-26 20:13:39

    楼下的算法
    差不多
    我好像是45ms
    就是树状数组求比一个数大的数的个数时要先倒过来再求
    还有要用long long
    C++scanf/printf的格式符让我悲剧了

    • @ 2014-10-02 02:17:51

      想弱弱的问一句,为什么用一个数左边的比它小的数*右边比它大的数这么做有的点过不了呢?

  • -3
    @ 2012-11-18 09:51:10

    编译通过...

    ├ 测试数据 01:答案正确... (0ms, 912KB)

    ├ 测试数据 02:答案正确... (0ms, 912KB)

    ├ 测试数据 03:答案正确... (15ms, 912KB)

    ├ 测试数据 04:答案正确... (0ms, 912KB)

    ├ 测试数据 05:答案正确... (0ms, 912KB)

    ├ 测试数据 06:答案正确... (15ms, 912KB)

    ├ 测试数据 07:答案正确... (15ms, 912KB)

    ├ 测试数据 08:答案正确... (15ms, 912KB)

    ├ 测试数据 09:答案正确... (15ms, 912KB)

    ├ 测试数据 10:答案正确... (15ms, 912KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 93ms / 912KB

    时间复杂度可以降到NlgN

    首先是n^2的算法,

    对于每个val[i]

    获得左边比他小的数记为sum1[i]

    右边比他大的数记为sum2[i]

    那么对于他来说,所能造成的影响就是sum1[i] * sum2[i]

    降到lgN则是把求sum1和sum2的用树状数组优化。

    • @ 2014-11-02 21:09:30

      请问怎么用树状数组优化?

  • -3
    @ 2012-11-09 13:29:04

    编译通过...

    ├ 测试数据 01:答案正确... (78ms, 98176KB)

    ├ 测试数据 02:答案正确... (219ms, 98172KB)

    ├ 测试数据 03:答案正确... (390ms, 98176KB)

    ├ 测试数据 04:答案正确... (421ms, 98168KB)

    ├ 测试数据 05:答案正确... (453ms, 98172KB)

    ├ 测试数据 06:答案正确... (593ms, 98168KB)

    ├ 测试数据 07:答案正确... (562ms, 98172KB)

    ├ 测试数据 08:答案正确... (577ms, 98176KB)

    ├ 测试数据 09:答案正确... (577ms, 98168KB)

    ├ 测试数据 10:答案正确... (453ms, 98172KB)

    预处理:b[i][j]表示a[1] ... a[j]中比a[i]小的数的数量。



    int get_lower_count(int b[], int l, int r)

    {

    return b[r] - b[l - 1];

    }

    枚举左端点i,右端点j,则 get_lower_count(b[j], i + 1, j) - get_lower_count(b[i], i, j)为a[i]...a[j]的“顺序对的值”。因为a...a[j-1]中的值只有3种情况,要么比a[j]大,要么在a[i]与a[j]之间,要么比a[i]小。比a[i]小的数,必然比a[j]小。所以用比a[j]小的数剪掉比a[i]小的数即可。

    另外累加时需要用long long

    时空复杂度均为n^2

  • -4
    @ 2017-09-03 22:54:02

    #include<iostream>
    using namespace std;

    int a[5005];
    int n;
    long long sum = 0;
    int main(){
    //freopen("test.txt", "r", stdin);
    cin>>n;
    int i, j;
    for(i = 1; i <= n; ++i){
    cin>>a[i];
    }
    int p,q;
    for(i = 1; i < n; ++i){
    p = 0;
    for(j = 1; j < i; ++j){
    if(a[j] < a[i]){
    ++p;
    }
    }
    if(p == 0){
    continue;
    }
    q = 0;
    for(j = i + 1; j <=n; ++j){
    if(a[j] > a[i]){
    ++q;
    }
    }
    sum += p*q;
    }
    cout<<sum;
    return 0;
    }

  • 1

信息

ID
1768
难度
5
分类
数据结构 | 单调队列 点击显示
标签
(无)
递交数
441
已通过
159
通过率
36%
被复制
5
上传者