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

比赛链接：https://ac.nowcoder.com/acm/contest/5773

A.第k小数
题意
求第k小数
题解
这道题有点毒，sort会被卡掉，其实只要把前k个小的数排出来就行了，所以用nth_element(a,a+k-1,a+n);意思就是只把第k个小的数放在k的位置，第 k个元素之前的元素都小于它，但不必是有序的。同样，第 k个元素后的元素都大于它，但也不必是有序的。
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 5e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

int a[N];
void solve(){
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    nth_element(a,a+k-1,a+n);
    cout<<a[k-1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

B不平行的直线
题意
给一些不重合的点，可以两两成直线，问最多选多少两两相交的直线
题解
找斜率不同的直线个数即可，注意垂直x轴情况
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
int x[201],y[201];
void solve(){
    int n;cin>>n;
    set<double>s;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    int f=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(x[i]==x[j])f=1;
            else{
                s.insert(1.0*(y[i]-y[j])/(x[i]-x[j]));
            }
        }
    }
    cout<<s.size()+f;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

C.丢手绢
题意
给你一些点，围成一个圈，每两相邻个点有距离，求两个点之间的最大距离，距离定义为圆的弧长
题解
选一个参考点，求所有点到这点的距离，通过相差就可以求出任意两点的距离，然后枚举每一个点，求这点到其他点最大距离，我们发现这是一个凸函数，直接三分即可
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
int sum[N],a[N];
int judge(int x,int y){
    if(x==y)return 0;
    //cout<<x<<' '<<y<<' '<<min(abs(sum[x]-sum[y]),a[1]-abs(sum[x]-sum[y]))<<endl;
    return min(abs(sum[x]-sum[y]),a[1]-abs(sum[x]-sum[y]));
}
void solve(){
    int n;cin>>n;
    for(int i=2;i<=n;i++)cin>>a[i],sum[i]+=sum[i-1]+a[i];
    cin>>a[1];a[1]+=sum[n];
    int ans=0;
    for(int i=1;i<=n;i++){
        int l=0,r=n+1;
        while(l+1<r){
            int lm=(l+r)>>1,rm=(lm+r)>>1;
            if(judge(lm,i)>judge(rm,i))r=rm;
            else l=lm;
        }
        ans=max(ans,judge(l,i));
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

D.二分
题意
不好描述
题解
差分裸题，三种情况讨论

 if(s=="+")m[x]--,now++;//负无穷到x-1,全部加一
 if(s=="-")m[x+1]++;//x+1到正无穷全部加一
 if(s==".")m[x]++,m[x+1]--;//x加一

统计时算一下前缀和就好了
可以离散化一下，亦可以直接map记录
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

void solve(){
    map<int,int>m;
    int n;cin>>n;
    int now=0;
    for(int i=0;i<n;i++){
        int x;string s;cin>>x>>s;
        if(s=="+")m[x]--,now++;
        if(s=="-")m[x+1]++;
        if(s==".")m[x]++,m[x+1]--;
    }
    int ans=0;
    for(auto i:m){
        now+=i.se;
        ans=max(ans,now);
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

E.交换
题意
给你一个个数列，问最少交换几次才能使其从大到小有序
题解
第一反应可能是逆序对，或者最长上升子序列之类的，但是这个要求可以任意换，可以不相邻，比如说312，可以3-2,2-1，其实在2-1时成了一个环，每出现一个环答案就会减一，所以找环的个数
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
int a[N],b[N],v[N];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    sort(a+1,a+1+n);
    int now=0;
    for(int i=1;i<=n;i++){
        if(!v[i]){
            int k=lower_bound(a+1,a+1+n,b[i])-a;
            v[i]=1;
            while(!v[k]){
                v[k]=1;
                k=lower_bound(a+1,a+1+n,b[k])-a;
            }
            now++;
        }
    }
    cout<<n-now;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}