A、第k小数

快排看人品，欧皇就可以A，正解可以用STL里面的nth_element平均复杂度On，再来就是基数排序或者计数排序了

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 5e6 + 7; //被一开始2e6卡的死死的
int num[N];

int main() {
    int T = read();
    while (T--) {
        int n = read(), k = read();
        for (int i = 0; i < n; ++i)  num[i] = read();
        nth_element(num, num + k - 1, num + n);
        write(num[k - 1]), putchar(10);
    }
    return 0;
}

B、不平行的直线

没有卡set的精度，正解开个set，统计不同斜率的个数即可，斜率不同，就会相交。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 205;
struct Node {
    int x, y;
}a[N];
set<double> st;

int main() {
    js;
    int n;    cin >> n;
    for (int i = 1; i <= n; ++i)    cin >> a[i].x >> a[i].y;
    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            if (a[j].x == a[i].x)    {
                st.insert(999999999.0);
                continue;
            }
            double k = (a[j].y - a[i].y) * 1.0 / (a[j].x - a[i].x);
            st.insert(k);
        }
    cout << st.size() << endl;
    return 0;
}

C、丢手绢

尺取
题目多了一行输入把我整半天……）看题目把
对于一个1-n的节点，选取另外一个点，起始为2，当从的最小距离小于的最小距离那么距离i的最远点不可能是，可以画个图，正反看一下就知道为什么不行了，那么对于i后方的点，可不可能更新到前面去？如果后面更新的最优解比不上前方的点，那么前面就已经保存了答案。使用前面更新的答案已经保存了。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
int a[N], sum;

int dis(int x, int y) { return a[y - 1] - a[x - 1]; }
int mini(int x, int y) { return min(dis(x, y), sum - dis(x, y)); }

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i)    a[i] = read(), a[i] += a[i - 1];
    sum = a[n];
    int j = 2, ans = 0;
    for (int i = 1; i <= n; ++i) {
        while (j < n and mini(i, j) <= mini(i, j + 1))    ++j;
        ans = max(ans, mini(i, j));
    }
    write(ans), putchar(10);
    return 0;
}

D、二分

乌拉！看完雨巨讲解回来补题拉。突然发现这个题目居然挺简单的。
这个混乱的游戏，我们居然是吧裁判给出的条件转换为一个区间覆盖问题。求最多被覆盖的区间被几个区间覆盖了。
我这里看了别人的代码用的map去离散化，毕竟常数比较大，也可以用快排加去重，根据题目来吧，0x3f3f3f3f居然被卡了……瞬间就不好了，还是用下定义的宏吧……

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

map<int, int> mp;
int main() {
    js;
    int n;    cin >> n;
    while (n--) {
        int num;
        char ch;
        cin >> num >> ch;
        if (ch == '.')    ++mp[num], --mp[num + 1];
        else if (ch == '+')    ++mp[0], --mp[num];
        else ++mp[num + 1], --mp[INT_MAX];  //……看来雨巨的数据很大0x3f3f3f3f死了
    }
    int ans = INT_MIN;
    int sum = 0;
    for (auto it : mp) {
        sum += it.second;
        ans = max(ans, sum);
    }
    cout << ans << '\n';
    return 0;
}

E、交换

找循环节的裸题，赛后才发现，其实可以看到5 4 2 3 1，如果要把元素放到对应位置，5 1一个循环节，4 2 3一个循环节，一个循环节少换1次，总的就是少换循环节的个数次，因为不连续所以要开个map去记位置。当重新回来之后就说明一个循环节统计完毕

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
bool vis[N];
vector<int> v, v1;
map<int, int> mp;

int main() {
    int n = read();
    for (int i = 0; i < n; ++i) {
        int x = read();
        v.push_back(x);
    }
    v1 = v;
    sort(v1.begin(), v1.end());
    for (int i = 0; i < n; ++i)    mp[v1[i]] = i;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            int j = i;
            while (!vis[j])    vis[j] = true, j = mp[v[j]];
            ++cnt;
        }
    }
    write(n - cnt);
    return 0;
}