A.第k小数

Solution


STL nth_element();

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 5e6 + 5;

int a[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;
}

void solve(){
    int n,k;
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    nth_element(a+1,a+k,a+1+n);
    printf("%d\n",a[k]);
}

int main(){
    int T;T=read();
    while(T--){
        solve();
    }
    return 0;
}

B.不平行的直线

Solution

把斜率放入set去重，特判分母为0的情况。

理论上来说数据极限的情况可能会造成精度问题?

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e3 + 5;

int n; 
double x[N],y[N];
set<double> s;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    bool ok=false;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(x[j]!=x[i]) s.insert((y[j]-y[i])/(x[j]-x[i]));
            else ok=true;
        }
    }
    cout<<s.size()+(ok?1:0)<<"\n";
    return 0;
}

C.丢手绢

Solution

尺取纪录最大值即可

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int n,a[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int R=0,d=0,ans=0;
    for(int L=1;L<=n;L++){
        while(d<=sum-d){
            ++R;
            if(R>n) R=R%n;
            d+=a[R];
            ans=max(ans,min(d,sum-d));
        }
        d-=a[L];
    }
    cout<<ans<<'\n';
    return 0;
}

D.二分

Solution

差分
因为读题错误wa了一整场,'+'是猜的数比实际数大,'-'相反。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const ll NINF = -1e18;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int n;
map<ll,ll> M;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x;char c;
        cin>>x>>c;
        if(c=='.') M[x]++,M[x+1]--;
        if(c=='-') M[x+1]++;
        if(c=='+') M[NINF]++,M[x]--;
    }
    ll tmp=0,ans=0;
    for(auto in:M){
        tmp+=in.se;
        ans=max(ans,tmp);
    }
    cout<<ans<<'\n';
    return 0;
}

E.交换

Solution

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int n,a[N],b[N];
bool v[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    int loops=0;
    for(int i=1;i<=n;i++){
        if(!v[i]){
            int j=i;
            while(!v[j]) v[j]=true,j=a[j];
            loops++;
        }
    }
    cout<<n-loops<<'\n';
    return 0;
}