2020年牛客算法入门课练习赛1 题解

这次比赛真的。。。槽点满满啊。。。A,C,D,E都有问题。。。（害我罚时高到飞起）

A.第k小数

读完题，我：这nlogn直接艹，问题不大！

然后。。。

段错误*n

我:???

然后，天真的以为sort出锅了，码了个基排。。。

然后。。。

段错误*n

我:???

之后，自暴自弃，数组开个1e7，于是。。。

答案正确。

我:???

emmm，这题，没啥技巧，sort被卡了，直接上无脑基排吧。。。

注意分正数和负数两个情况讨论

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1;
int a[N],d[N],n,k;
const int base=256,mod=255;
int b[N],c[4][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 >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
inline void base_sort(){
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;++i){
        c[0][a[i]&mod]++;
        c[1][(a[i]>>8)&mod]++;
        c[2][(a[i]>>16)&mod]++;
        c[3][(a[i]>>24)]++;
    }
    for(int i=1;i<=mod;++i){
        c[0][i]+=c[0][i-1];
        c[1][i]+=c[1][i-1];
        c[2][i]+=c[2][i-1];
        c[3][i]+=c[3][i-1];
    }
    for(int i=n;i;--i){
        b[c[0][a[i]&mod]--]=a[i];
    }
    for(int i=n;i;--i){
        a[c[1][(b[i]>>8)&mod]--]=b[i];
    }
    for(int i=n;i;--i){
        b[c[2][(a[i]>>16)&mod]--]=a[i];
    }
    for(int i=n;i;--i){
        a[c[3][(b[i]>>24)]--]=b[i];
    }
}
int main(){
    int T=read();
    while(T--){
        n=read(),k=read();int e=0,p=0;
        for(int i=1;i<=n;++i){
            int x=read();
            if(x<0){
                d[++e]=x;
            }else{
                a[++p]=x;
            }
        }
        int reflag=1;
        if(e>=k){
            n=e;reflag=-1;
            for(int i=1;i<=n;++i){
                a[i]=-d[i];
            }
        }else{
            n=p;
        }
        base_sort();
        printf("%d\n",a[k]*reflag);
    }
    return 0;
}

B.不平行的直线

比较斜率是否一样即可（注意讨论没有斜率的情况）

因为double可能出精度，直接可能炸，于是。。。将分子和分母用pair存起来，然后直接上set就行了。

（为了正确比较，记得化成最简分数，且由于可能为负，我们规定分子必须为非负，就行了）

复杂度:

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=201;
int x[N],y[N];
set<pair<int,int> >sp;
int main(){
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x[i],&y[i]);
    }
    bool flag=0;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(x[i]==x[j]){
                flag=1;
                continue;
            }
            int X=y[i]-y[j],Y=x[i]-x[j];
            if(X<0)X=-X,Y=-Y;
            int D=__gcd(X,Y);
            X/=D,Y/=D;
            sp.insert(make_pair(X,Y));
        }
    }
    int res=sp.size()+flag;
    printf("%d",res);
    return 0;
}

C.丢手绢

我们枚举每一个点，然后算出离这个点最远的点离这个点的距离就行了。

如果暴力，明显不可行。

观察到可以直接二分/三分。直接上模板即可

复杂度:

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1;
int s[N],pos[N],n;
inline int calc(int x,int y){
    if(x>y){
        swap(x,y);
    }
    return min(abs(pos[x]-pos[y]),pos[x]+s[n]+pos[n]-pos[y]);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&s[i]);
    }
    scanf("%lld",&s[n]);//这句话看情况加不加吧/xk题面问题
    for(int i=2;i<=n;++i){
        pos[i]=pos[i-1]+s[i-1];
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        int l=1,r=n,res=0;
        while(l<=r){
            int lc=l+(r-l)/3,rc=r-(r-l)/3;
            int L=calc(i,lc),R=calc(i,rc);
            if(L>R){
                res=L,r=rc-1;
            }else{
                res=R,l=lc+1;
            }
        }
        ans=max(ans,res);
    }
    printf("%lld",ans);
    return 0;
}

D.二分

这题也是诡异。。。

输入描述有这句：

接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。

然后，样例解释是：

当目标数组是5时，5 . 5 . 8 - 这三个回答都是正确的

两者明显矛盾了。。。/xk

通过我的多次提交牺牲（qwq），我们发现，输入描述的是正确的，我们按输入描述的做就行了。。。

我们首先，对于每个回答，算出它的可行解的范围。

那么，很明显的，答案就是在最多的可行解范围内的点所包含的可行解范围。（有点绕/xk）

但是，每个可行解的范围其实很大的，我们不可能直接统计，怎么办？

注意到，非端点的数字其实没什么用处（也就是说我们把所有的端点都算一遍就可以求出答案了）

那么，我们直接将所有可行解离散化一遍，然后就是简单的区间加，单点查询问题了，套个数据结构就可以了（ps:建议数组开大点，玄学。。。）

复杂度:

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
#define int long long
struct node{
    int l,r;
}t[N];
int b[N],s[N],m,e,inf;
inline int lowbit(int x){
    return x&-x;
}
inline void insert(int x,int y){
    while(x<=e){
        s[x]+=y;x+=lowbit(x);
    }
}
inline int find(int x){
    int ans=0;
    while(x){
        ans+=s[x];x-=lowbit(x);
    }
    return ans;
}
signed main(){
    int n;
    scanf("%lld",&n);
    e=0,inf=1e17;
    for(int i=1;i<=n;++i){
        int x;char y;
        cin>>x>>y;
        if(y=='.'){//x-x ans+1
            t[i]=(node){x,x};
        }else if(y=='-'){
            t[i]=(node){x+1,inf};
        }else{
            t[i]=(node){-inf,x-1};
        }
        b[++e]=t[i].l,b[++e]=t[i].r;
    }
    sort(b+1,b+e+1);
    m=unique(b+1,b+e+1)-b-1;
    for(int i=1;i<=n;++i){
        t[i].l=lower_bound(b+1,b+m+1,t[i].l)-b;
        t[i].r=lower_bound(b+1,b+m+1,t[i].r)-b;
        insert(t[i].l,1),insert(t[i].r+1,-1);
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        ans=max(ans,find(i));
    }
    printf("%d",ans);
    return 0;
}

E.交换

一开始以为是交换相邻的,然后光荣贡献了罚时

这道题，直接上结论就行了。

我们把一个点和它排完序后的位置连一条单向边，那么答案就是点的个数-环的个数/每个环的大小-1的和

直接跑暴力一遍就行了，因为每个点都只会被访问一次，所以复杂度是

(看我开的数组就可以猜到我经历了什么qwq)

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000001;
int a[N],b[N],nex[N];
bool vis[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int ans=0;
    for(int i=1;i<=n;++i){
        int x=lower_bound(b+1,b+n+1,a[i])-b;
        nex[i]=x;
    }
    for(int i=1;i<=n;++i){
        if(nex[i]==i||vis[i])continue;
        int tot=0,now=i;
        while(!vis[now]){
            ++tot,vis[now]=1;now=nex[now];
        }
        ans+=(tot-1);
    }
    printf("%d",ans);
    return 0;
}