因为是久远的比赛，没有什么特别难的题。

没有 DP 好评（）

A

Description

有 $n$ 个大人 $m$ 个小孩，一枚车票一元钱，一个大人可以带很多小孩，一个大人能免费带一个小孩上车，每个小孩都必须有一个大人带。问最少/最多需要花多少钱。

Solution

又水又毒瘤，不写了，看代码。

Code

#include <iostream>
#include <algorithm>
using std::cin;
using std::endl;
using std::cout;
 
int main()
{
    int a, b;
    cin >> a >> b;
    if (a == 0 && b != 0) // 有小孩没大人
        puts("Impossible");
    else if (b == 0) // 有大人没小孩
        cout << a << " " << a << endl;
    else
        cout << std::max(a, b) << " " << a + b - 1 << endl; 
    // 最少就是尽量一个大人带一个小孩，最大就是一个大人带所有小孩
}

B

Description

平面上有两个圆，输出一个能连接这两个圆的圆的最小半径。

Solution

分两个圆相离、内含、相交（相切）算一下就行，具体看代码。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using std::cin;
using std::endl;
using std::cout;

inline double pow2(double x) { return x * x; }

inline void updmi(double &a, double b) { a = std::min(a, fabs(b) / 2.0); }
inline void out(double x) { printf("%.15lf\n", x); }

int main()
{
    double x1, y1, r1, x2, y2, r2;
    cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
    double dis = sqrt(pow2(x1 - x2) + pow2(y1 - y2));
    if (r1 < r2)
        std::swap(r1, r2);
    if (dis > r1 + r2) // 相离，即样例的那两个图
        out((dis - r1 - r2) / 2.0);
    else if (r2 + dis < r1) // 内含，圆的直径是大半径减小半径减两个圆圆心的距离
        out((r1 - r2 - dis) / 2.0);
    else // 相交或相离，显然答案是 0
        out(0.0);
}

C

Description

给出若干个 pair 和 int，你需要把它输出成合法的 c++ 语法，如 pair pair int int int 输出 pair<pair<int,int>,int>，如果无解输出 Error occurred。

Solution

类似一个表达式转化，对于一个 pair 递归两次就行，注意直接用 string 会 TLE，最好先判断一下有没有解。（我这个做法贼蠢，看个乐就行）

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <string>
using std::cin;
using std::endl;
using std::cout;

const int maxn = 1e6 + 10;

int a[maxn];
char s[10];
int n, m;

void work(int &i)
{
    if (a[i] == 0)
        cout << "int";
    if (a[i] == 1)
    {
        cout << "pair<";
        work(++i);
        cout << ",";
        work(++i);
        cout << ">";
    }
}

bool check(int &i)
{
    if (i == n)
        return a[i] == 0 ? 1 : 0;
    if (i == 1 && a[i] == 0)
        return 0;
    if (a[i] == 0)
        return 1;
    bool tmp = 1;
    if (a[i] == 1)
    {
        tmp = check(++i);
        if (tmp == 0)
            return 0;
        tmp = check(++i);
        if (tmp == 0)
            return 0;
    }
    return 1;
}

int main()
{
    cin >> m;
    while (cin >> s)
        a[++n] = s[0] == 'p' ? 1 : 0;
    if (n != m + m - 1)
    {
        puts("Error occurred");
        return 0;
    }
    int i = 1;
    bool ok = check(i);
    if (!ok || i < n)
    {
        puts("Error occurred");
        return 0;
    }
    i = 1;
    work(i);
    cout << endl;
}

D

Description

给定一个长度为 $n$ 的序列 $a_i$ 和 $k$，求满足出现次数最多的数的出现次数小于 $k$​ 的连续子序列的数目。

Solution

由于是连续的子序列，而且发现选的数越多越可能满足，考虑双指针。

对于每个 $l$，我们找到最小的能满足这个条件的 $r$​，然后后面的就随便选了，把它对答案的贡献加进去，就完事了。

至于怎么找 $r$ 呢，我们用一个 map 存每个数的出现次数就行了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using std::cout;
using std::endl;
using std::cin;

const int maxn = 4e5 + 10;
typedef long long ll;

int n, a[maxn], k;
ll ans;
std::map<int, int> mp;

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = 2;        
    mp[a[1]]++;
    for (; l <= n; l++)
    {
        while (r <= n && mp[a[r - 1]] < k)
            mp[a[r]]++, r++;
        if (mp[a[r - 1]] >= k)
            ans += n - r + 2;
        mp[a[l]]--;
    }
    cout << ans << endl;
}

E

Description

给定一个点数为 $n$ 的完全图，从中删除 $m$ 条边，求得到的图的联通块。$n\leq5\times10^5,m\leq10^6$。

Solution

发现一个事情：相对于一个很大的完全图，删除的边数实在少得可怜。量化一下发现最多只能让约 $\dfrac{m}{n}$​​​ 个点成为一个独立的联通块。

这实在是小的可怜。也就是说大部分点实际上是连通的。

考虑到当能删完的时候，$n\approx1500$，那么我们直接找一个在删除的边中出现次数最小的点，把与它相连的点全都取出来当成一个联通块。

剩下的点爆搜一下连通块就行。我的实现非常暴力而且恶心，使用了 map 复杂度大概是 $O(n+(\dfrac{m}{n})^2\log\dfrac{m}{n})$​​。最大的点跑得很慢。

事实上我不知道我这个复杂度到底对不对，反正是卡常卡过去了…

看到有用并查集的做法能做到 $O(n+m)$​，值得一学。。。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
using std::cout;
using std::endl;
using std::cin;

const int maxn = 5e5 + 10;

namespace IO
{
    const int mxsiz = 1 << 20;
    char inbuf[mxsiz], *p1, *p2;
    char outbuf[mxsiz], *op = outbuf;
    struct endio
    {
        endio(){};
        ~endio() { fwrite(outbuf, 1, op - outbuf, stdout); }
    } useless_var;
    inline char gc() { return p1 == p2 && (p2 = (p1 = inbuf) + fread(inbuf, 1, mxsiz, stdin), p1 == p2) ? EOF : *p1++; }
#define isdigit(x) (x >= '0' && x <= '9') // 防止忘记打 <cctype> 头文件
    inline int read()
    {
        int x = 0, f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        return x * f;
    }
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        int f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        x *= f;
    }
#undef isdigit
    inline bool ischar(char x)
    {
        return x >= 'A' && x <= 'z';
    }
    inline char readchar()
    {
        char ch = gc();
        while (!ischar(ch))
            ch = gc();
        return ch;
    }
    inline void push(char ch)
    {
        if (op - outbuf == mxsiz)
            fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
        *op++ = ch;
    }
    template <typename T>
    inline void work_wt(T x)
    {
        if (x > 9)
            work_wt(x / 10);
        push(x % 10 + '0');
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            x = -x, push('-');
        work_wt(x);
    }
    inline void writestr(char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n; i++)
            push(s[i]);
    }
    inline void endln() { push('\n'); }
    inline void space() { push(' '); }
    template <typename T>
    inline void writeln(T x) { write(x), endln(); }
}
using namespace IO;

int times[maxn], n, mm, tot, used[maxn], arcscc[maxn], m;
std::vector<int> scc[maxn];
std::vector<int> e[maxn], e2[maxn / 10];
std::map<int, int> mp[maxn];
std::vector<int> not_used;
std::vector<int> now;
int p[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }
inline void add2(int x, int y) { e2[x].push_back(y), e2[y].push_back(x); }

void dfs(int x, int q)
{
    arcscc[not_used[x - 1]] = q;
    if (x != m + 1 && not_used[x - 1] != n + 1)
        scc[q].push_back(not_used[x - 1]);
    for (int v : e2[x])
        if (!arcscc[not_used[v - 1]])
            dfs(v, q);
}

int main()
{
    n = read(), mm = read(); // 这里的 mm 是原题的 m，我因为变量名冲突改了一下
    for (int x, y, i = 1; i <= mm; i++)
        x = read(), y = read(), times[x]++, times[y]++, add(x, y);
    int mi = 1e9, pos = 0;
    for (int i = 1; i <= n; i++)
        if (times[i] < mi)
            mi = times[i], pos = i;
    scc[++tot].push_back(pos), used[pos] = 1, arcscc[pos] = 1;
    for (int v : e[pos])
        used[v] = 1;
    for (int i = 1; i <= n; i++)
        if (!used[i] && i != pos)
            scc[tot].push_back(i), arcscc[i] = 1;
        else if (used[i])
            not_used.push_back(i);
    // 以上是找到出现次数最小的点并将与他相连的点删掉
    for (int i : not_used)
    {
        int cnt = 0;
        for (int v : e[i])
            if (arcscc[v] == 0)
                mp[i][v] = mp[v][i] = 1;
            else
                cnt++;
        if (cnt == scc[1].size())
            mp[i][n + 1] = mp[n + 1][i] = 1;
    }
    m = not_used.size(); // 删掉之后原图剩余点数
    not_used.push_back(n + 1); // 除了剩余的点，刚刚删除的点也作为一个联通块加进去
    for (int i = 1; i <= not_used.size(); i++)
        now.push_back(i), p[i] = not_used[i - 1];
    for (int i = 1; i < m + 1; i++)
        for (int j = i + 1; j <= m + 1; j++)
            if (!mp[p[i]][p[j]])
                add2(i, j); // 重新建图
    dfs(m + 1, 1);
    for (int i = 1; i <= m; i++)
        if (!arcscc[not_used[i - 1]])
            dfs(i, ++tot);
    writeln(tot);
    for (int i = 1; i <= tot; i++)
    {
        write(scc[i].size()), space();
        for (int j : scc[i])
            write(j), space();
        endln();
    }
    return 0;
}