100 + 90 + 100 + 35，rk 33.

挂分捏。

A

人口普查题。注意使用 getline 和 string.

string s;

bool chk1(char c) {
    if (c <= '9' && c >= '0') return 1;
    else return 0;
}

bool chk2(char c) {
    if (c <= 'z' && c >= 'a') return 1;
    else if (c <= 'Z' && c >= 'A') return 1;
    else return 0;
}

signed main() {
    getline(cin,s);
    int n = s.size();
    for (int i = 0;i < n;++i) {
        if (chk1(s[i]) && chk2(s[i-1])) printf(" ");
        if (chk2(s[i]) && chk1(s[i-1])) printf(" ");
        printf("%c",s[i]);
    }
    return 0;
}

B

首先考虑一个性质：Alice/Bob 每次必然取的都是从大到小排序后的一段前缀。

这个的证明暂时不会，不过可以感性理解。

所以我们考虑 DP。令 f_{0/1,j} 表示 a_j 是由 Alice/Bob 选取的，那么转移方程易得：

f_{0,j} = f_{1,j-1} \\ f_{1,j} = \max f_{0,j-1},f_{1_j-1} + a_j

这个的意义是显然的，直接做 DP，时间复杂度为 \mathcal{O}(n) 的。

const int N = 1e5 + 10;
ll a[N],ans,n,f[2][N],pre[N];
bool flag = 0;
vector <ll> res;

signed main() {
    read(n);
    for (int i = 1;i <= n;++i) read(a[i]),flag |= (a[i] < 0);
    if (!flag || n == 1) {
        for (int i = 1;i <= n;++i) ans += a[i];
        printf("%lld\n",ans);
        return 0;
    }
    sort(a + 1,a + 1 + n);reverse(a + 1,a + 1  +n);
    for (int i = 1;i <= n;++i) pre[i] = pre[i-1] + a[i];
    f[1][0] = -1e18;
    for (int i = 1;i <= n;++i) {
        f[1][i] = max(f[0][i-1],f[1][i-1]) + a[i];
        f[0][i] = f[1][i-1];
    }
    printf("%lld\n",max(f[0][n],f[1][n]));
    return 0;
}

C

考虑枚举这个平均数 x，那么我们考虑令 b_i = a_i - x，则若 [l,r] 为一个平均数为 x 的子段，那么就有 \sum\limits_{i = l}^r b_i = 0。也就是说我们可以在 \mathcal{O}(n) 的时间内处理出前缀和，开一个值域在 [-100n,100n] 的桶实现查询。

总时间复杂度 \mathcal{O}(n)

const int N = 2e5 + 10;
const int D = 1e7;
int n,a[N],pre[N],minn = 0x3f3f3f3f,maxx,b[N];
int buc[20000010];
ll ans;

signed main() {
    read(n);
    for (int i = 1;i <= n;++i) read(a[i]),minn = min(minn,a[i]),maxx = max(maxx,a[i]);
    for (int x = minn;x <= maxx;++x) {
        for (int i = 1;i <= n;++i) {
            b[i] = a[i] - x;
            pre[i] = pre[i-1] + b[i];
        }
        for (int i = 1;i <= n;++i) {
            ans += (ll)buc[pre[i] + D];
            buc[pre[i-1] + D]++;
        }
        for (int i = 1;i <= n;++i) {
            buc[pre[i-1] + D] = 0;
        }
    }
    ans += n;
    printf("%lld\n",ans);
    return 0;
}

D

本题本质：给定 q 条限制，要求 (x,y) 必须在同一个强连通分量内。构造一个有 X 个极大强连通子图和 m 条边的图。

我们考虑对于一个大小为 p 的极大强连通子图，边的范围在 [p,p(p-1)]，如果将两个大小分别为 p_1,p_2 的强连通分量合并，那么新产生的边在 [2,p_1\times p_2] 之间。由此我们可以得出构造出来的边数上下界。

接下来我们判断出来了可行性，考虑如何构造。参考题解，我们需要注意的是：

1. 首先是我们钦定需要处于同一强连通分量内的点，应当真的属于同一强连通分量 可以通过造一个环来满足强连通
2. 强连通分量之间的边不能成环。解决办法也很简单：给每个强连通分量任意定一个编号，只从编号小的分量往编号大的分量 连边，就不会成环

时间复杂度应当是 \mathcal{O}(nk) 的，k 是某个常数。我实现的不好被卡 90 了。

//Autumn leaves falling down like pieces into place
//And I can picture it after all these days
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    int v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
inline int add(int x, int y) {return (x += y) >= mod ? x - mod : x;}
inline int dec(int x, int y) {return (x -= y) < 0 ? x + mod : x;}
inline int mul(int x, int y) {return (ll)x * y % mod;}
const int N = 5e5 + 10;
int n,x,q,f[N];
ll m;   
vector <int> G[N],poi[N];
vector <vector<int> > p;

int find(int x) {return x == f[x] ? f[x] : f[x] = find(f[x]);}

bool cmp(vector <int> a,vector <int> b) {
    return a.size() < b.size();
}

signed main() {
    read(n,m,x,q);
    for (int i = 1;i <= n;++i) f[i] = i;    
    for (int i = 1;i <= q;++i) {
        int x,y;read(x,y);
        f[find(x)] = find(y);
    }
    for (int i = 1;i <= n;++i) {
        poi[find(i)].push_back(i);
    }
    for (int i = 1;i <= n;++i) {
        if (poi[i].size()) p.push_back(poi[i]);
    }
    sort(p.begin(),p.end(),cmp);
    if (p.size() < x) {
        puts("-1");
        return 0;
    }
    while (p.size() > x) {
        auto &a = p[p.size() - 2],&b = p[p.size() - 1];
        swap(a,b);
        a.insert(a.end(),b.begin(),b.end());
        p.pop_back();
    }
    ll l = 0,r = 0,pre = 0;
    for (auto &now : p)  {
        l += (now.size() == 1 ? 0 : now.size());
        r += (ll)(now.size() * (now.size() - 1 + pre));
        pre += now.size();
    }
    if (m < l || m > r) {
        puts("-1");
        return 0;
    }
    for (auto &now : p) {
        int orz = now.size();
        if (orz == 1) continue;
        for (int i = 0;i < orz;++i) printf("%d %d\n",now[i],now[(i + 1) % orz]);
    }
    m -= l;
    vector <int> lst;
    for (auto &now : p) {
        int orz = now.size();
        for (int i = 0;i < orz;++i) {
            for (int j = 0;j < orz;++j) {
                if (i != j && j != (i + 1) % orz) {
                    printf("%d %d\n",now[i],now[j]);
                    if ((--m) == 0) {return 0;}
                } 
            }
            for (auto j : lst) {
                printf("%d %d\n",now[i],j);
                if ((--m) == 0) {return 0;}
            }
        }
        lst.insert(lst.end(),now.begin(),now.end());   
    }
    return 0;
}