Day 1

篮球 - Basketball

前 30% 的数据

直接枚举上场状态和中间断开的点，由于上场状态只有上场和不上场，所以总的复杂度是$\Theta(2^n n)$。

正解

我们发现球员的数位非常小，且上场球员也非常少。那么，我们可以考虑设计一个前缀异或和还有后缀与和，那么在相同的数字上相乘即可得到结果。$prefix[i][j]$表示前$i$个中，能凑成$j$的方案数，$suffix[i][j]$表示$[i, n]$中，能凑成$j$的方案数。相乘的时候要固定后缀部分一定要选当前球员，这样可以避免算重。

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

using namespace std;

const int MAX_N = 1030, mod = 1e9 + 7;

int prefix_xor[MAX_N][MAX_N], suffix_and[MAX_N][MAX_N];
int n, seq[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    for (int i = 1; i <= n; i++)
    {
        prefix_xor[i][seq[i]] = 1;
        for (int j = 0; j < 1024; j++)
            prefix_xor[i][j] = (1LL * prefix_xor[i][j] + 1LL * prefix_xor[i - 1][j ^ seq[i]]) % mod;
        for (int j = 0; j < 1024; j++)
            prefix_xor[i][j] = (1LL * prefix_xor[i - 1][j] + 1LL * prefix_xor[i][j]) % mod;
    }
    for (int i = n; i >= 1; i--)
    {
        suffix_and[i][seq[i]] = 1;
        for (int j = 0; j < 1024; j++)
            suffix_and[i][j & seq[i]] = (1LL * suffix_and[i][j & seq[i]] + 1LL * suffix_and[i + 1][j]) % mod;
        for (int j = 0; j < 1024; j++)
            suffix_and[i][j] = (1LL * suffix_and[i + 1][j] + 1LL * suffix_and[i][j]) % mod;
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < 1024; j++)
            ans = (1LL * ans + 1LL * prefix_xor[i - 1][j] * (1LL * suffix_and[i][j] - 1LL * suffix_and[i + 1][j] + 1LL * mod) % mod) % mod;
    printf("%d", ans);
    return 0;
}

旅行 - Travel

前 50% 的数据

直接跑最短路即可，时间复杂度视最短路算法而定。

正解

这是一道分层图最短路的裸题，由于数据非常大，所以这道题应该使用带堆优化的 Dijkstra 算法。分层图的模型来自于 2004 年肖天的国家集训队论文，具体了解可以上网搜索或者转至国家集训队的 GitHub 仓库。

建图部分：我们把坐了$i$次火车作为一层（$i \in [0, m_2]$），顶点$x$在第$i$层的节点编号为$x + n \times i$。首先把飞机的路径复制$m_2 + 1$层，然后再把火车路径$(u, v)$复制$m_2$层，在第$i$层为$(u + i \times n, v + (i + 1) \times n), i \in [0, m_2 - 1]$。合法的答案就在每一层的$n$号节点。所以，跑完最短路直接扫一遍$dist$数组即可。记得开 long long。

// travel.cpp
#include <bits/stdc++.h>
typedef long long ll;
#define pr pair<ll, int>

using namespace std;

const int MAX_N = 6e5 + 200;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int head[MAX_N], current, n, m1, m2;
ll dist[MAX_N];
bool vis[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N * 10];

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

void shortest_path(int src)
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pr> pq;
    pq.push(make_pair(0, src)), dist[src] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 1, u, v, w; i <= m1; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        for (int layer = 0; layer <= m2; layer++)
            addpath(u + layer * n, v + layer * n, w);
    }
    for (int i = 1, u, v; i <= m2; i++)
    {
        scanf("%d%d", &u, &v);
        for (int layer = 0; layer < m2; layer++)
            addpath(u + layer * n, v + (layer + 1) * n, 0);
    }
    shortest_path(1);
    for (int layer = 0; layer <= m2; layer++)
        if (dist[layer * n + n] < INF)
            printf("%d\n%lld", layer, dist[layer * n + n]), exit(0);
    puts("-1");
    return 0;
}

回文树 - Palindrome

前 40% 的数据

随便乱做，对于每一个作为根节点的节点，$\Theta(n^2)$时间枚举路径即可。总的时间复杂度为$\Theta(n^3)$。

前 60% 的数据

我们发现字符集数量很小，所以我们把每一个字符变成$2^i$作为边权，发现合法的路径其实就是路径上异或和为$0$或者为$2^i$的情况（奇数回文串的情况）。所以，可以直接在子树内用$\Theta(n)$的时间内进行记录，放到桶子里统计即可。

正解

考虑每一次在子树内枚举，损失了太多已知信息。我们考虑进行启发式合并，然后就可以优化到$\Theta(n \log n)$。具体也可以看这篇博客。

// palindrome.cpp
// dsu on tree;
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5 + 200;

int head[MAX_N], current, n, fa[MAX_N], siz[MAX_N], lft[MAX_N], rig[MAX_N], ptot;
int son[MAX_N], dep[MAX_N], anti[MAX_N], book[1 << 23], answer[MAX_N], dist[MAX_N];
char opt[10];

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

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

void predfs(int u)
{
    lft[u] = ++ptot, siz[u] = 1, dep[u] = dep[fa[u]] + 1, anti[ptot] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        dist[edges[i].to] = dist[u] ^ edges[i].weight, predfs(edges[i].to), siz[u] += siz[edges[i].to];
        if (siz[son[u]] < siz[edges[i].to])
            son[u] = edges[i].to;
    }
    rig[u] = ptot;
}

void dfs(int u, bool save)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != son[u])
            dfs(edges[i].to, false), answer[u] = max(answer[u], answer[edges[i].to]);
    if (son[u] != 0)
        dfs(son[u], true), answer[u] = max(answer[u], answer[son[u]]);
    if (book[dist[u]] != 0)
        answer[u] = max(answer[u], book[dist[u]] - dep[u]);
    // iterate the mid char;
    for (int ch = 0; ch <= 21; ch++)
        if (book[dist[u] ^ (1 << ch)])
            answer[u] = max(answer[u], book[dist[u] ^ (1 << ch)] - dep[u]);
    book[dist[u]] = max(book[dist[u]], dep[u]);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != son[u])
        {
            for (int id = lft[edges[i].to]; id <= rig[edges[i].to]; id++)
            {
                int curt = anti[id];
                if (book[dist[curt]])
                    answer[u] = max(answer[u], dep[curt] + book[dist[curt]] - (dep[u] << 1));
                // iterate the mid char;
                for (int ch = 0; ch <= 21; ch++)
                    if (book[dist[curt] ^ (1 << ch)])
                        answer[u] = max(answer[u], book[dist[curt] ^ (1 << ch)] + dep[curt] - (dep[u] << 1));
            }
            for (int id = lft[edges[i].to]; id <= rig[edges[i].to]; id++)
                book[dist[anti[id]]] = max(book[dist[anti[id]]], dep[anti[id]]);
        }
    if (save == false)
        for (int id = lft[u]; id <= rig[u]; id++)
            book[dist[anti[id]]] = 0;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
        scanf("%d%s", &fa[i], opt + 1), addpath(fa[i], i, 1 << (opt[1] - 'a'));
    predfs(1), dfs(1, true);
    for (int i = 1; i <= n; i++)
        printf("%d ", answer[i]);
    return 0;
}

Day 2

太空 - Space

前 50% 的数据

直接$\Theta(n^2)$枚举点对，然后记录最小值。

正解

平面最近点对板子题，详细见：

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

using namespace std;

const int MAX_N = 1000001, INF = 0x3f3f3f3f;

int n;
struct point
{
    double x, y;
    bool operator<(const point &pt) { return x < pt.x || (x == pt.x && y < pt.y); }
} pts[MAX_N], tmp[MAX_N];

bool compareByY(const point &a, const point &b) { return a.y < b.y || (a.y == b.y && a.x < b.x); }

double pow2(double bas) { return bas * bas; }

double getDist(point a, point b) { return sqrt(pow2(a.x - b.x) + pow2(a.y - b.y)); }

double solve(int l, int r)
{
    if (l == r)
        return INF;
    else if (l + 1 == r)
        return getDist(pts[l], pts[r]);
    int mid = (l + r) >> 1;
    double current_ans = min(solve(l, mid), solve(mid + 1, r));
    int tot = 0;
    for (int i = l; i <= r; i++)
        if (fabs(pts[i].x - pts[mid].x) <= current_ans)
            tmp[++tot] = pts[i];
    sort(tmp + 1, tmp + 1 + tot, compareByY);
    for (int i = 1; i <= tot; i++)
        for (int j = i + 1; j <= tot && fabs(tmp[i].y - tmp[j].y) < current_ans; j++)
            current_ans = min(current_ans, getDist(tmp[i], tmp[j]));
    return current_ans;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &pts[i].x, &pts[i].y);
    sort(pts + 1, pts + 1 + n);
    printf("%.4lf", solve(1, n));
    return 0;
}

原子理论 - Atom

前 20% 的数据

其实就是分解质因数，然后找到最大且不为自己的因数即可，时间复杂度为$\Theta(\sqrt{n})$

前 60% 的数据

可以用$\Theta(n \log n)$的时间求出这$n$个数字与$a_i$的$\gcd$，然后分解质因数找到最大不为自己的因数即可。时间复杂度为$\Theta(n \log n + n \sqrt{n})$。

正解

我们发现次大公约数肯定是$a_1$的因数之一，所以我们可以用$\Theta(\sqrt{a_1})$的时间把$a_1$分解并存下其因数，然后再将$a_i$除这些因数找到最大不为自己的因数。总的时间复杂度为$\Theta(\sqrt{a_1} + n \log n)$。

// atom.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAX_N = 1e6 + 200;

ll n, ai[MAX_N], primes[MAX_N];

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    for (int i = 1; 1LL * i * i <= ai[1]; i++)
        if (ai[1] % i == 0)
        {
            primes[++primes[0]] = i;
            if (ai[1] / i != i)
                primes[++primes[0]] = ai[1] / i;
        }
    sort(primes + 1, primes + 1 + primes[0]);
    for (int i = 1; i <= n; i++)
    {
        bool flag = true;
        ll di = gcd(ai[1], ai[i]);
        for (int j = 1; j <= primes[0]; j++)
            if (di % primes[j] == 0 && di / primes[j] < di)
            {
                printf("%lld ", di / primes[j]);
                flag = false;
                break;
            }
        if (flag)
            printf("-1 ");
    }
    return 0;
}

韭菜国 - Winnie

有一个坑点：权贵的时间非常值钱，所以每一个权贵都期望他那$m$个时间单位刚好用尽。所以没有把 DP 赋值成负无穷的同学可能会错。

前 50% 的数据

直接上 01 背包即可，复杂度为$\Theta(nm)$。

正解

这道题其实就是 01 背包前 k 优解的板子题，看过背包九讲应该可以秒掉。

首先回忆 01 背包的 DP 递推式：
$$
dp[j] = \max{ dp[j], dp[j - weight_i] + value_i }
$$
我们可以尝试加一维，记录为第$x$优解：$dp[x][j]$。如何从之前的更优解合并为次优解是这道题的难点。首先我们发现，对于每一个$j$，${ dp[1][j], dp[2][j], dp[3][j], \dots }$是单调下降的。那么，我们如果要合并出一个新的单调下降序列，我们就可以使用归并排序的合并方式：只不过不是在两个序列上，而是在两种决策中选择，我们可以把选择第$i$个的和不选择的答案虚拟成两个长度为$k$的序列，然后用归并的方式合并。

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

using namespace std;

const int MAX_N = 5050;

int dp[55][MAX_N], k, m, n, wi[MAX_N], vi[MAX_N], tmp[MAX_N];

int main()
{
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &wi[i], &vi[i]);
    memset(dp, 128, sizeof(dp));
    dp[1][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= wi[i]; j--)
        {
            int ptr1 = 1, ptr2 = 1, ptr = 0;
            while (ptr <= k)
                if (dp[ptr1][j] > dp[ptr2][j - wi[i]] + vi[i])
                    tmp[++ptr] = dp[ptr1++][j];
                else
                    tmp[++ptr] = dp[ptr2++][j - wi[i]] + vi[i];
            for (int pt = 1; pt <= k; pt++)
                dp[pt][j] = tmp[pt];
        }
    int ans = 0;
    for (int i = 1; i <= k; i++)
        ans += dp[i][m];
    printf("%d", ans);
    return 0;
}

总结 - Conclusion

对于新高一的选手来说，这一套卷子的暴力分非常足，有 240 分（30+50+0+50+60+50）的弱智分。而对于其他更熟练的选手，本套卷子更是提供了 440 分（30+100+60+100+100+50）的无脑暴力。对于新高一的选手，这套题考查的东西是暴力能力；对于熟练的选手而言，这道题就是在测稳定度还有基础能力，因为剩下的题几乎全是板子题。

祝大家 CSP-S 2019 取得好成绩。

出题人：江西师范大学附属中学 2021 级 17 班黄晨曦