Test20190814 Solution

T1 apple

T2 matrix

前缀和优化更佳

T3 x3

异或……

观察一下,可以发现在 $\sum_{i=1}^{n}\sum_{j=i+1}^{n} x_i xor x_j$中,在二进制中只有在同一位上不同数字 0与1的组合才会对答案有所贡献,所以就统计每一位上0、1的个数,乘法原理搞定。

#include<bits/stdc++.h>
using namespace std;
int const MAXN=1000010;
long long n,ans,maxn=-1;
long long fo[MAXN];
int b[10000][2];
int main(){
    freopen("x3.in","r",stdin);
    freopen("x3.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&fo[i]);
        long long tot=0;
        while(fo[i]){
            b[tot++][fo[i]&1]++;
            fo[i]=fo[i]>>1;
        }
        maxn=max(tot,maxn);
    }
    for(int i=1;i<=n;i++){
        b[i][0]=n-b[i][1];
    }
    unsigned long long a=1;
    for(int i=0;i<=n;i++){
        ans+=a*b[i][1]*b[i][0];
        a*=2;
    }
    printf("%lld\n",ans);
    return 0;
}

T4 dance

贪心

思路为每一个希望与比自己高的人,找与其身高差最小的异性

#include<bits/stdc++.h>
using namespace std;
int const MAXN=1000010;
int n,tot1,tot2,ans;
int as[3000][2],bs[3000][2];
int scan(){
    char c=getchar();
    int x=1,i=0;
    while(c<'0' || c>'9'){if(c=='-')x=-1;c=getchar();}
    while(c>='0' && c<='9'){i=i*10+c-'0';c=getchar();}
    return i*x;
}
int main(){
    freopen("dance.in","r",stdin);
    freopen("dance.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int h=scan();
        if(h<0){
            as[abs(h)][0]++;
        }else{
            bs[abs(h)][0]++;
        }
    }
    for(int i=1;i<=n;i++){
        int h=scan();
        if(h<0){
            as[abs(h)][1]++;
        }else{
            bs[abs(h)][1]++;
        }
    }
    for(int i=1500;i<=2500;i++){
        if(bs[i][0]==0 && bs[i][1]==0)continue;
        //printf("%d %d %d\n",i,bs[i][0],bs[i][1]);
        for(int p=i+1;p<=2500;p++){
            if(as[p][0]==0 && as[p][1]==0)continue;
            //printf("%d %d %d\n",p,as[p][0],as[p][1]);
            if(bs[i][1]){
                int minn=min(as[p][0],bs[i][1]);
                ans+=minn;
                as[p][0]-=minn;
                bs[i][1]-=minn;
            }
            if(bs[i][0]){
                int minn=min(as[p][1],bs[i][0]);
                ans+=minn;
                as[p][1]-=minn;
                bs[i][0]-=minn;
            }
            if(bs[i][1]==0 && bs[i][0]==0)break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

T5 sort

题目保证每一个反转的sloape长度为偶数

当我们将第一次的所有sloape反转过来之后,可以知道接下来可以反转的sloape定$<=2$。

再考虑一下每一次操作对逆序对的贡献。

第一波反转:设共有 tot 段需要反转,其中一次长度为k,则本段总贡献为$k\times(k-1)\div 2$,

第二轮反转:1

则总反转次数为 $总逆序对数 - \sum_{i=1}^{tot} k_i\times(k_i-1)\div 2+1$

#include<bits/stdc++.h>
using namespace std;
int const MAXN=100000;
long long n,ans;
int a[MAXN];
long long tree[MAXN];
int lowbit(int x){return x & (-x);}
void insert(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))tree[i]+=v;
}
int ask(int x){
    int sum=0;
    for(int i=x;i;i-=lowbit(i))sum+=tree[i];
    return sum;
}
struct point{
    int x,id;
}p[MAXN];
bool cmp(point x,point y){
    return x.x<y.x;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        p[i]=(point){a[i],i};
    }
    int k=1;
    for(int i=2;i<=n;i++){
        if(a[i-1]>a[i])k++;
        else{
            ans-=k*(k-1)/2-1;k=1;
        }
    }
    ans-=k*(k-1)/2-1;k=1;
    sort(p+1,p+n+1,cmp);
    for(int i=n;i>=1;i--){
        ans+=ask(p[i].id-1);
        insert(p[i].id,1);
    }
    printf("%lld\n",ans);
    return 0;
}

T6 chess

挖个坑

boshi大佬说是一道广搜卡常题,正常是$O(n^2*T)$,而用bitset可以做到$O(n^2*T \div 32)​$

cy叫我们看标程

Emm……不敢恭维

Last modification:August 17th, 2019 at 08:57 am

One comment

  1. Illusions

    辛苦了辛苦了!

    我也来写篇试试吧 ୧(๑•̀⌄•́๑)૭

Leave a Comment