题解

49 条题解

  • 2
    @ 2019-06-26 18:30:25
    //高考后第一次回vijos,看来手感还没下降太多QwQ
    //此题与选择客栈有一点相似之处
    //找到我们要的数的位置,然后从这个位置往左往右分别扫一遍
    //往右扫的过程中,y[i]表示b右边比b大的数有i个的区间的数量(很绕是不是)
    //z[i]就表示b左边比b小的数有i个区间的数量
    //这里为了防止数组下标出现负数,把初值设为n
    //这样的话所有y[]*z[]加起来就是答案
    //注意z[0]与与y[0]还要单独加上
    //另外b本身作为一个区间也是可以的,所以答案要再+1
    #include<iostream>
    using namespace std;
    int a[100010],z[200010],y[200010];
    int main()
    {
        int n,b,i,w,now,sum=0;
        cin>>n>>b;
        for(i=1;i<=n;i++)
         {
            cin>>a[i];
            if(a[i]==b)
             w=i;
         }
        now=n;
        for(i=w+1;i<=n;i++)
         {
            if(a[i]>a[w])
             now++;
            else
             now--;
            y[now]++;
         }
        now=n;
        for(i=w-1;i>0;i--)
        {
            if(a[i]>a[w])
             now--;
            else
             now++;
            z[now]++;
        }
        for(i=0;i<=2*n+1;i++)
         sum+=z[i]*y[i];
        sum+=z[n]+y[n];
        cout<<sum+1;
        return 0;
    }
    
  • 2
    @ 2017-11-12 23:23:13
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int maxn = 100010;
    int n, b, pos, a[maxn], f[maxn * 2];
    ll res;
    
    int main() {
        scanf("%d %d", &n, &b);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if (a[i] == b) {
                pos = i;
            }
        }
        ll cur = 0;
        for (int i = pos; i >= 1; i--) {
            cur += (a[i] < b);
            cur -= (a[i] > b);
            f[cur + 100000]++;
        }
        cur = 0;
        for (int i = pos; i <= n; i++) {
            cur += (a[i] > b);
            cur -= (a[i] < b);
            res += f[cur + 100000];      
        }
        printf("%lld\n", res);
        return 0;
    }
    
  • 0
    @ 2020-04-27 11:05:14
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn = 100005;
    
    int num[maxn];
    int sum[maxn];
    int cnt[maxn << 1];
    
    int main()
    {
        int n, b, k, index = -1;
        cin >> n >> b;
        for (int i = 1; i <= n; i++)
        {
            cin >> k;
            if(k < b)
                num[i] = -1;
            else if(k == b)
                index = i;
            else
                num[i] = 1;
            sum[i] = sum[i - 1] + num[i];
            if(index == -1)
                cnt[sum[i] + n]++;
        }
    
        cnt[n]++;       //前缀和为0时, 就是表示区间1~i, 不能直接用前缀差表示, 就是i的前缀和
        
        int ans = 0;
        for (int i = index; i <= n; i++)
            ans += cnt[sum[i] + n];
        cout << ans << endl;
    
        return 0;
    }
    
    
  • 0
    @ 2017-07-17 14:47:00

    #include<iostream>
    using namespace std;
    int n,b;
    int da[100010];
    int lct[2][100010],rct[2][100010];
    int main () {
        
        ios::sync_with_stdio(false);
        cin>>n>>b;
        int pos=0;
        for(int i=1;i<=n;i++) {
            cin>>da[i];
            if (da[i]<b) da[i]=-1;
            else if (da[i]>b) da[i]=1;
            else pos=i,da[i]=0;     
        }
        int sum=0;
        for(int i=pos;i>=1;i--) {
            sum+=da[i];
            if (sum>0) lct[1][sum]++;
            else lct[0][-sum]++;
        }
        sum=0;
        for(int i=pos;i<=n;i++) {
            sum+=da[i];
            if (sum<0) rct[1][-sum]++;
            else rct[0][sum]++;     
        }
        int ans=0;
        for(int i=0;i<=100010;i++) 
          for(int j=0;j<=1;j++) 
            ans+=lct[j][i]*rct[j][i];
        cout<<ans<<endl;
        return 0;
        
    }
    

    哦,对了,记住是排序,b只会出现一次。

    • @ 2017-10-07 20:57:47

      sans还行qwq

  • 0
    @ 2017-07-12 11:38:05

    过气Pascal最后的续命....
    刚开始没处理好边界,狂刷10次全WA...

    比之前交的代码更短了,就18行,时间内存都优化了,但可读性变差了,代码已经瘦的不成样了......
    不要什么数据结构,统计一下就行了。楼下的楼下有个相似方法,但C++的代码比我长,因为--C++没有负的数组下标,要特殊处理.....
    每读一个数处理一次,读完答案也出来了,已经没法再快了。
    var
    a,n,b,i,m,ans,sum:longint;
    left:array[-100000..100000] of longint;
    begin
    readln(n,b);
    fillchar(left,sizeof(left),0);
    sum:=0; left[0]:=1;
    for i:=1 to n do
    begin
    read(a);
    if a>b then inc(sum) else if a<b then dec(sum) else if a=b then begin m:=i+1; break end;
    inc(left[sum]);
    end;
    ans:=left[sum];
    for i:=m to n do
    begin read(a); if a>b then inc(sum) else if a<b then dec(sum); ans:=ans+left[sum]; end;
    writeln(ans);
    end.

    总计50ms,1MB,复杂度O(n),应该都是最小的了吧。评测机变牛逼了,<15ms已经不能糊弄程0ms了,0msAC已成上古神话......

  • 0
    @ 2017-01-25 18:23:03

    #include <bits/stdc++.h>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;

    const int N = 100000 + 5;

    int n, b, num[N], a[N], sum[N][2];

    int main() {
    scanf("%d%d", &n, &b);
    int pos = 0;
    for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] == b) { num[i] = num[i - 1]; pos = i; }
    else if (a[i] < b) num[i] = num[i - 1] - 1;
    else if (a[i] > b) num[i] = num[i - 1] + 1;
    }
    int ans = 0;
    for (int i = pos; i >= 1; i--) {
    int x = num[pos] - num[i - 1];
    if (x < 0) sum[-x][0]++;
    else if (x > 0) sum[x][1]++;
    else sum[0][0]++;
    }
    for (int i = pos; i <= n; i++) {
    int x = num[i] - num[pos];
    if (x > 0) ans += sum[x][0];
    else if (x < 0) ans += sum[-x][1];
    else ans += sum[0][0];
    }
    printf("%d\n", ans);
    return 0;
    }

  • -1
    @ 2017-01-26 17:14:37

    偷懒用了个map,不然可以再快些

    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    using namespace std;

    #define rep(id,a,b) for(int id=(a);id<(b);++id)
    #define irep(id,a,b) for(int id=(a);id>(b);--id)
    #define reset(arr,c) memset(arr,c,sizeof(arr))

    typedef long long int64;

    #include <map>

    const int maxN = 100000 + 5;

    int N, B;
    int s[maxN];

    void input()
    {
    scanf ("%d%d", &N, &B);
    rep (i, 0, N) scanf ("%d", s + i);
    }

    int64 solve()
    {
    int64 ans (1);
    map<int, int> cnt;
    int pos = 1;
    while (s[pos] != B) ++pos;
    int tp = 0;
    irep (i, pos - 1, -1)
    {
    if (s[i] < B) ++tp;
    else --tp;
    if (tp == 0) ++ans;
    if (!cnt.count (tp) ) cnt[tp] = 1;
    else ++cnt[tp];
    }
    tp = 0;
    rep (i, pos + 1, N)
    {
    if (s[i] > B) ++tp;
    else --tp;
    if (tp == 0) ++ans;
    ans += cnt[tp];
    }
    return ans;
    }

    int main()
    {
    input();
    printf ("%lld\n", solve() );
    return 0;
    }

  • -1
    @ 2017-01-23 23:44:50

    大神帮我看看错哪了,显示Runtime Error
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a[100001], s[100001], f[100001];
    int main()
    {
    int n, b, k = 1, ans = 0;
    scanf("%d%d", &n, &b);
    for (int i = 1; i <= n; i++)
    {
    scanf("%d", &a[i]);
    if (a[i] == b) k = i, a[i] = 0;
    else if (a[i] > b)a[i] = 1;
    else a[i] = -1;
    }
    for (int i = k - 1; i > 0; i--)
    s[i] = s[i + 1] + a[i];
    for (int i = k + 1; i <= n; i++)
    s[i] = s[i - 1] + a[i];
    for (int i = k; i > 0; i--)
    f[s[i]]++;
    for (int i = k; i <= n; i++)
    ans += f[-s[i]];
    cout << ans << endl;
    return 0;
    }

  • -1
    @ 2016-11-07 11:51:02
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cctype>
    #include<cstdlib>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    using namespace std;
    typedef bool boolean;
    #define smin(a, b)  (a) = min((a), (b))
    #define smax(a, b)  (a) = max((a), (b))
    template<typename T>
    inline void readInteger(T& u){
        char x;
        while(!isdigit((x = getchar())));
        for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
        ungetc(x, stdin);
    }
    
    int n, m;
    int pos;
    int* list;
    
    inline void init(){
        readInteger(n);
        readInteger(m);
        list = new int[(const int)(n + 1)];
        for(int i = 1; i <= n; i++){
            readInteger(list[i]);
            if(list[i] == m)    pos = i;
        }
    }
    
    inline int calc(int less, int more){
        return (less < more) ? (n - less + more) : (less - more);
    }
    
    int result;
    int* buffer;
    inline void solve(){
        buffer = new int[(const int)(n * 2 + 1)];
        int more = 0, less = 0;
        memset(buffer, 0, sizeof(int) * (n * 2 + 1));
        buffer[0] = 1;
        for(int i = pos + 1; i <= n; i++){
            if(list[i] > list[pos]) more++;
            else less++;
            buffer[calc(less, more)]++;
        }
        more = less = 0;
        for(int i = pos; i >= 1; i--){
            if(list[i] > list[pos]) more++;
            else if(i != pos)   less++;
            result += buffer[calc(more, less)];
        }
        printf("%d", result);
    }
    
    int main(){
        init();
        solve();
        return 0;
    }
    
  • -1
    @ 2016-03-27 20:24:18
  • -1
    @ 2015-10-05 20:59:33

    记录信息
    评测状态 Accepted
    题目 P1549 中位数
    递交时间 2015-10-05 20:52:24
    代码语言 C++
    评测机 VijosEx
    消耗时间 76 ms
    消耗内存 2620 KiB
    评测时间 2015-10-05 20:52:26
    评测结果

    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:46:24: warning: unknown conversion type character 'l' in format [-Wformat=]
    printf("%lld\n",ans);
    ^
    foo.cpp:46:24: warning: too many arguments for format [-Wformat-extra-args]

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 76 ms, mem = 2620 KiB, score = 100
    代码

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <memory>
    #include <iostream>
    using namespace std;

    int num[100001],sum[100001],l[200001],r[200001],n,b,point;
    long long ans;

    int main()
    {
    scanf("%d %d\n",&n,&b);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&num[i]);
    if(num[i]>b)
    {
    num[i]=1;
    }
    else if(num[i]==b)
    {
    num[i]=0;
    point=i;
    }
    else num[i]=-1;
    }
    l[n]=1;
    r[n]=1;
    for(int i=point-1;i>=1;i--)
    {
    sum[i]=sum[i+1]+num[i];
    l[sum[i]+n]++;
    }
    for(int i=point+1;i<=n;i++)
    {
    sum[i]=sum[i-1]+num[i];
    r[sum[i]+n]++;
    }
    for(int i=0;i<=2*n-1;i++)
    {
    ans+=l[i]*r[2*n-i];
    }
    printf("%lld\n",ans);
    return 0;
    }

    AC60题啦!纪念一下。。。不要吐槽。。。。

  • -1
    @ 2015-08-06 20:29:17

    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int MAXN=100000 + 10;

    long int num[MAXN], f[MAXN], sum[MAXN][2];

    int main()
    {
    int n, a, b, bri, ans=0;
    scanf("%d%d",&n,&b);

    for(int i=1; i<=n; i++){
    scanf("%d",&num[i]);
    if(num[i] < b)
    f[i] = f[i-1] - 1;
    else if(num[i] > b)
    f[i] = f[i-1] + 1;
    else if(num[i] == b){
    bri = i;
    f[i] = f[i-1];
    }
    }
    for(int i=bri-1; i>=0; i--){
    a = f[bri] - f[i];
    if(a < 0)
    sum[-a][0]++;
    else if(a > 0)
    sum[a][1]++;
    else
    sum[0][0]++;
    }
    for(int j=bri; j<=n; j++){
    a = f[j] - f[bri-1];
    if(a > 0)
    ans += sum[a][0];
    else if(a < 0)
    ans += sum[-a][1];
    else
    ans += sum[0][0];
    }
    printf("%d",ans);
    return 0;
    }
    水一发~~

  • -1
    @ 2015-02-10 23:40:43

    P1549中位数
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1549 中位数
    递交时间 2015-02-10 23:40:23
    代码语言 C++
    评测机 VijosEx
    消耗时间 361 ms
    消耗内存 1944 KiB
    评测时间 2015-02-10 23:40:24

    评测结果

    编译成功

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 361 ms, mem = 1944 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <map>

    using namespace std;

    int n , b;
    int i;
    int a[100000 + 10];
    int is[100000 + 10];
    int pre[100000 + 10];
    int pos;
    map < int , int > m;
    int ans;

    int main()
    {
    scanf( "%d %d" , &n , &b );
    for( i = 0 ; i < n ; i++ )
    scanf( "%d" , &a[i] );
    for( i = 0 ; i < n ; i++ )
    if( a[i] > b )
    is[i] = -1;
    else if( a[i] < b )
    is[i] = 1;
    else
    {
    pos = i;
    is[i] = 0;
    }
    pre[0] = is[0];
    for( i = 1 ; i < n ; i++ )
    pre[i] = pre[ i - 1 ] + is[i];
    for( i = pos ; i < n ; i++ )
    if( m.find( pre[i] ) != m.end() )
    m[ pre[i] ]++;
    else
    m[ pre[i] ] = 1;
    for( i = 0 ; i < pos ; i++ )
    ans += m[ pre[i] ];
    ans += m[ 0 ];
    cout << ans << endl;
    return 0;
    }

  • -1
    @ 2015-01-24 13:30:18

    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <math.h>
    #include <vector>
    #include <cstdio>
    #include <string>
    #include<string.h>
    #include <fstream>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define exp 1e-8
    #define maxn 100010
    #define set(a,b) memset(a,b,sizeof(a));
    void bug(string st="bug")
    {cout<<st<<endl;}
    int num[maxn];
    int lmin[maxn]={0};
    int lmax[maxn]={0};
    int rmin[maxn]={0};
    int rmax[maxn]={0};
    int main()
    {
    int n,d;
    scanf("%d %d",&n,&d);
    int idx=0;
    for(int i=1;i<=n;i++)
    {
    int temp;
    scanf("%d",&temp);
    if(temp==d)
    idx=i;
    else if(temp>d)
    num[i]=1;
    else num[i]=-1;
    }
    int sum=0;
    for(int i=idx+1;i<=n;i++)//r
    {
    sum+=num[i];
    if(sum>=0)
    rmax[sum]++;
    else
    rmin[-sum]++;
    }
    sum=0;
    for(int i=idx-1;i>=1;i--)//r
    {
    sum+=num[i];
    if(sum>=0)
    lmax[sum]++;
    else
    lmin[-sum]++;
    }
    int ans=lmax[0]+rmax[0]+1+lmax[0]*rmax[0];
    for(int i=1;i<=n;i++)
    {
    if(lmax[i]!=0)
    ans+=lmax[i]*rmin[i];
    if(lmin[i]!=0)
    ans+=lmin[i]*rmax[i];
    }
    cout<<ans<<endl;
    return 0;
    }

  • -1
    @ 2014-04-16 14:23:05

    {
    将小于b的数改为-1,等于b的改为0,大于b的改为1,统计前缀和
    并建立主席树,设b的位置为pos
    枚举左端点0..pos-1
    对答案贡献为[pos,n]里sum[i]出现的次数
    O(nlogn)
    }
    const
    maxn = 5000000;
    type
    node = record
    a,b : longint;//[a,b]
    l,r : longint;//left,right
    data : longint;//Data : 里面数字的个数
    end;
    var
    seg : array[0..maxn] of node;
    tot : longint;
    a,tmp,head : array[0..100010] of longint;
    n,i,x,b,pos : longint;
    ans : int64;
    procedure build(a,b : longint);
    var
    mid,id : longint;
    begin
    inc(tot);
    id := tot;
    seg[id].a := a;
    seg[id].b := b;
    if a = b then exit;
    mid := (a + b) >> 1;
    seg[id].l := tot+1;
    build(a,mid);
    seg[id].r := tot+1;
    build(mid+1,b);
    end;
    procedure insert(x,nownode : longint);
    var
    mid : longint;
    begin
    inc(tot);
    seg[tot].a := seg[nownode].a;
    seg[tot].b := seg[nownode].b;
    seg[tot].data := seg[nownode].data+1;
    mid := (seg[tot].a + seg[tot].b) >> 1;
    if x <= mid then
    begin
    seg[tot].r := seg[nownode].r;
    if seg[nownode].l > 0 then begin
    seg[tot].l := tot+1;
    insert(x,seg[nownode].l);
    end;
    end
    else
    begin
    seg[tot].l := seg[nownode].l;
    if seg[nownode].r > 0 then begin
    seg[tot].r := tot+1;
    insert(x,seg[nownode].r);
    end;
    end;
    end;
    function query(k,l,r : longint) : int64;
    var
    mid : longint;
    begin
    repeat
    if seg[r].a = seg[r].b then exit(seg[r].data-seg[l].data);
    mid := (seg[r].a + seg[r].b) >> 1;
    if k <= mid then
    begin
    r := seg[r].l;
    l := seg[l].l;
    end
    else
    begin
    r := seg[r].r;
    l := seg[l].r;
    end;
    until false;
    end;
    begin
    read(n,b);
    for i := 1 to n do
    begin
    read(x);
    if x = b then
    begin
    pos := i;continue;
    end;
    if x < b then
    tmp[i] := -1
    else
    tmp[i] := 1;
    end;
    a[0] := n+1;
    for i := 1 to n do a[i] := a[i-1]+tmp[i];
    build(1,n*2+10);
    head[0] := 1;
    for i := 1 to n do
    begin
    head[i] := tot+1;
    insert(a[i],head[i-1]);
    end;
    for i := 0 to pos-1 do
    ans := ans + query(a[i],head[pos-1],head[n]);
    writeln(ans);
    end.

  • -1
    @ 2013-11-15 21:58:48

    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    using namespace std;

    #define MAXN 300000
    #define D 100001

    int f[MAXN];
    int a[MAXN];
    int b,n,t;
    int s1[MAXN],s2[MAXN];

    int main(){
    scanf("%d%d",&n,&b);
    s1[0]=0;
    s2[0]=0;
    for (int i=0;i++<n;){
    scanf("%d",&a[i]);
    if (a[i]<b){
    s1[i]=s1[i-1]+1;
    } else s1[i]=s1[i-1];
    if (a[i]>b){
    s2[i]=s2[i-1]+1;
    } else s2[i]=s2[i-1];
    if (a[i]==b){
    t=i;
    }
    }
    memset(f,0,sizeof(f));
    f[0+D]=1;
    for (int i=t;i++<n;){
    f[(s2[i]-s2[t])-(s1[i]-s1[t])+D]++;
    }
    /* for (int i=-10;i<=10;i++){
    printf("%d:%d\n",i,f[i+D]);
    }*/
    int ans=0;
    for (int i=0;i++<t;){
    // printf("%d:%d\n",i,f[-((s2[t-1]-s2[i-1])-(s1[t-1]-s1[i-1]))+D]);
    ans+=f[-((s2[t-1]-s2[i-1])-(s1[t-1]-s1[i-1]))+D];
    }
    printf("%d\n",ans);
    return 0;
    }

  • -1
    @ 2009-09-18 20:01:22

    h:array[-100000..100000]of longint;

    用hash表求f[i]+f[j]=0的个数,根据排列组合的原则,hash表一定不能开成boolean!我在这了wa几次。

  • -1
    @ 2009-08-09 11:41:33

    如对本题有疑问可以参看我的题解:http://xujieqi.blog.hexun.com/35722312_d.html

  • -1
    @ 2009-08-07 22:01:35

    20行的程序。。。

    很爽。。

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

    Accepted 有效得分:100 有效耗时:0ms

    补充“三代水影·游”的最后一步。。

    用一个数组来记录值为s[i]时有多少个,

    无外乎这几句,

    for i:=k downto 1 do inc(f[s[i]]);

    for i:=k to n do inc(ans,f[s[i]]);

    因为s是统计大了多少个和小了多少个的差,

    中间有一个S值为零的K,两边一共是偶数个,加上中间的一个,

    这样就一定是奇数个了。。。

    得证,最后结果不需要奇偶判断。。。。。

    不过我的F数组要开很大。。

    空间需求大(空间换时间)。。。

  • -1
    @ 2009-08-07 15:53:27

    超水

    O(rec)就可以出解 rec表示中位数所在的位置编号

    hash表记录一下就行了

信息

ID
1549
难度
5
分类
模拟 | 数据结构 | Hashing 点击显示
标签
递交数
1609
已通过
519
通过率
32%
被复制
3
上传者