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 班黄晨曦