这次比赛必须要仔细反省，不能再出现暑假的精神状态。

A – 服务器需求

假设我们有很多服务器了，我们现在按天考虑，进行服务器的分配：假设有一个服务器编号集合\(\{id_i\}\)，考虑一天天分配若干台，这样就可以保证每一台服务器的分配中不会出现同样的日期。

这样就可以分配完了，直接就有\(\sum a_i \leq |id_i| m\)。然后就是傻逼代码了。

// A.cpp
#include <bits/stdc++.h>
typedef long long ll;
 
using namespace std;
 
const int MAX_N = 4e5 + 200;
 
ll n, m, q, ai[MAX_N];
 
int main()
{
    ll ans = 0;
    multiset<ll> ms;
    scanf("%lld%lld%lld", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]), ms.insert(ai[i]), ans += ai[i];
    printf("%lld\n", max(*ms.rbegin(), (ll)(double(ans + m - 1) / double(m))));
    while (q--)
    {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        ans -= ai[x], ms.erase(ms.find(ai[x]));
        ms.insert(ai[x] = y), ans += ai[x];
        printf("%lld\n", max(*ms.rbegin(), (ll)(double(ans + m - 1) / double(m))));
    }
    return 0;
}

B – 沙漠点列

这道题我在考场上只打了 60 分的特判分，还是很好打的。

考虑正解：先求出多少个连通块，然后再处理出有多少个环，来处理\(limit\)极大的情况；当\(limit\)无法直接包揽全部，那么我们优先把所有的割边进行贡献，然后再来破环贡献割边。用 DFS 的方式找出单元环（如果用 Tarjan 直接找就会 GG），然后排序从大到小选即可。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, MAX_E = 2e6 + 2000;

int head[MAX_N], current, n, m, limit, ncnt, dfn[MAX_N], low[MAX_N], ptot, stk[MAX_N], tail;
int SCC, aff[MAX_N], dist[MAX_N], loops[MAX_N], loop_cnt;

struct edge
{
    int to, nxt;
} edges[MAX_E << 1];

int read()
{
    char ch = getchar();
    int x = 0, f = 1;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return f * x;
}

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++ptot, stk[++tail] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            if (dfn[edges[i].to] == 0)
                tarjan(edges[i].to, u), low[u] = min(low[u], low[edges[i].to]);
            else
                low[u] = min(low[u], dfn[edges[i].to]);
    if (dfn[u] == low[u])
    {
        SCC++;
        do
        {
            aff[stk[tail]] = SCC;
        } while (stk[tail--] != u);
    }
}

void find_loop(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            if (dist[edges[i].to] == 0)
            {
                dist[edges[i].to] = dist[u] + 1;
                find_loop(edges[i].to, u);
            }
            else if (dist[edges[i].to] < dist[u] + 1)
                loops[++loop_cnt] = dist[u] - dist[edges[i].to] + 1;
}

int main()
{
    memset(head, -1, sizeof(head));
    n = read(), m = read(), limit = read();
    for (int i = 1, u, v; i <= m; i++)
        u = read(), v = read(), addpath(u, v), addpath(v, u);
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0)
            tarjan(i, 0), ncnt++;
    // get the non-loop component;
    ncnt = SCC - ncnt;
    if (limit <= ncnt)
        printf("%d\n", SCC + limit - ncnt), exit(0);
    limit -= ncnt;
    for (int i = 1; i <= n; i++)
        if (dist[i] == 0)
            dist[i] = 1, find_loop(i, 0);
    int ans = SCC;
    sort(loops + 1, loops + 1 + loop_cnt);
    reverse(loops + 1, loops + 1 + loop_cnt);
    for (int i = 1; i <= loop_cnt; i++)
    {
        limit--;
        ans += min(limit, loops[i] - 1);
        limit -= loops[i] - 1;
        if (limit < 0)
            break;
    }
    printf("%d\n", ans);
    return 0;
}

总结

这场比赛严重暴露了思路垃圾的弱点，之后每天都会固定写几道 CF 的贪心保持智商。