今天是夏至,发现今天是这个月第一次写文章。最近在准备比较重要的几场比赛,加上临近期末很多繁琐的大作业要完成,所以咕咕咕了接近三周。这一个多月珠三角的疫情反反复复,很多活动和安排都受到影响,希望能够赶紧缓和下来,一切都恢复正常吧。
说回这几场比赛,从结果来看,符合我预期目标,所以也还是挺满意的,这几个月的努力没有白费,自己努力的方向好像也没有多大问题。首先是院内的选拔赛,去年的选拔赛,由于赛前一个多月精神状态不好,一直在通过各种途径恢复,所以没有很专注地训练,最后很遗憾地排在第四名,没有进入最强的一队,这一年度的比赛,虽然个人赛事取得了一些成绩,但 XCPC 赛事打得还是有些挣扎的。今年靠着罚时锁定第二,不过看看题目,开场两分钟抢一血被题面演了连 WA 两发,才发现原来是个矩阵快速幂,写得很少,靠着回忆把模板套了上去,接着再拿了一个裸倍增题的一血,有道简单的二分贪心竟然想歪了,打到后面真有点脑袋不够灵活了。应该是最后一个 XCPC 赛季了,再玩一年。
前些年学院的竞赛成绩比较差,氛围也不太好,甚至外出比赛的资格都很难争取,同时也导致训练的条件越来越差。为了出成绩,每年在少数坚持打比赛的选手里选拔最强的几个人来组队。最近这两年,老师给我们集训队的关照多了,几个同学和学弟一起把训练带起来了,而且招生规模也大大增加,能够参与到算法竞赛的新鲜血液也越来越多,院内选手的实力已经有了一个质的飞跃。与我们当初摸着石头过河相比,现在新加入的选手可以站在前人的肩膀上,至少可以少走一些弯路了,学习效率也一定会大大提高,大一几位学弟的努力程度和比赛实力我们都有目共睹。在这样的前提下,我会更希望之后的组队形式要突出“团队”二字,也就是不必一定按照选拔的排名从高到低去组队,只要一个队伍在过往的比赛表现不错,队员实力处在一个合理的区间,相处得不错,就不必每年拆队重组了,毕竟一个团队之间只有存在长时间训练培养出来的默契和相辅相成的擅长点,才能产生三个一相加大于三的效果。
校赛的资格赛就没多少好说的了,毕竟两个队友在第一场已经拿到了资格,我上去直接看 B 抢下全场一血,一看榜还以为只有我一个人在玩,怀疑是不是进错片场了,接着又拿 C 题背包变形的一血。最后读错 A 题的题意,被绕进去了,两个多小时后才过,然后就挂机写大作业去了。
最后是昨天的省赛,体验很好,过程精彩刺激。开场找签到,一看 L 没有输入,反馈给队友,队友说是数学期望,看看还有没有更裸的签到。两分钟后刷了下榜,发现一车人交了 L ,于是赶紧读题, B.R 说直接用随机数暴力模拟一下,我继续看了 J ,和前两天补的一道题是类似的,直接 BFS 就行,这时 B.R 已经模拟出 L 是输出 $3.5$ 了,过了之后我跟 yyyg 确认了一下 J 的做法,完善了一些细节就直接上机写,一发过掉,手感不错。然后 B.R 发现 A 直接二分可做,于是我尝试一下推 G 题的博弈, A 很快过掉了以后,顺便再把 I 题的简单立体几何搞定,这时我们幸运地落在了金牌区的末尾。经过一段时间的手推,发现 G 题, Bob 只要开始拆分 $2$ ,那么他必输,直接统计两人的“安全操作”的次数然后比较大小即可,再次 1A 。此时看榜,过题较多的是 D 题,队友好像想复杂了,我看了一下题意,一个人只能跟相邻的人比赛,而且只是问某个人是否可能成为最后的胜者,一个人赢 $30$ 次或以上,那么他一定就无敌了,跟队友说直接暴力 $O(nloga)$ 的复杂度就行,啪的一下很快啊,直接上机写,造了几组样例验证后过掉。
比赛时间还没过半,但剩下的题好像过的人不多,感觉能够看看的就只有 B 、 C 、 K 了。 B 一开始以为是个矩阵快速幂递推,后来 B.R 发现小于 $10^7$ 的斐波那契数很少,我猜可以试试用折半枚举,他认为可以转化成背包,于是我就并没有进一步确认折半枚举的做法了; C 知道每次询问只需要处理长度为 $k$ 的子串即可,但不会后缀自动机没法优化; K 题 yyyg 发现可以用二维线段树或者二维树状数组来做,可惜我们都没有二维维护最值的模板。
计算了下时间和空间复杂度,发现 B 应该能跑过,毕竟只有 $3 \times 10^8$ 的运算量加上 $10^6$ 的输入输出,于是 B.R 上机写,我在一旁辅助。精彩的来了,我造了几组简单的样例验证后提交,竟然超时,确认已经关闭同步流,于是换成 scanf / printf 来输入输出,再把代码数据类型统一,以免运算过程中转换类型消耗时间,再次提交,又超时,这时我已经觉得很迷了,卡常不会卡得这么精准吧?瓶颈在于预处理,但我看了下,这个做法确实没法再做优化了,队友怀疑是输入输出耗费时间太长,于是把询问注释掉,只提交了预处理部分代码,发现没有超时,结合牛客的判题机制,判断预处理没问题,确实是输入输出超时,那就赶紧找模板写按字符快读,终于写好,竟然还是超时。此时已经绝望, B.R 问了一句你们有没有想用其它语言试试的? yyyg 随口一答要不试试 C ?于是马上把所有 C++ 特性删掉换成 C ,确认样例后再次提交,只见两三秒后几行绿绿的恭喜通过信息显示在屏幕,我们三个都直接跳起来地大喊,这也是我第一次在赛场上如此激动,以至于志愿者都过来提醒我们安静下来……
最后 7 题拿银,达到目标了,其实最后卡常过掉的 B 并不影响获奖,但过程实在太刺激且戏剧了。赛后听题解,正解确实是折半枚举,而且用 DP 的话,如果结合斐波那契数列前缀和的性质可以有 $O(n)$ 的做法,还是想少了一步。但翻看其它队伍的代码,发现有复杂度跟我们一样却一发过的。回来 B.R 在我们的 OJ 上测试,结果发现评测机抖动得厉害,我们赛时 TLE 的代码能过,最后 AC 的那份反而过不了。 懂了,原来我们的代码是抖动探测器啊。
那么到目前为止,可以说开始了新的阶段了,暑假还有一场校赛,只剩下两门课的考试,打算这两天好好休息一下,沉淀一下自己,计划接下来的事情了。因为这两周忙, CF 和 AtCoder 比赛都打得少,要回顾的题很多还是之前攒起来的,也还是有些难度的吧。另外还整理了一下 LCA 和 Dijkstra 的模板,平时训练可以直接套用。
E - White Pawn
题目链接: E - White Pawn
题意:
给定一个 $(2N+1)\times(2N+1)$ 的网格,从第二行开始,有一些黑棋子散落分布,在第一行的第 $N$ 列,有一个白棋子,在正中央,当满足以下条件之一时,白棋子可以操作:
- 正下方没有黑棋子,可以走到正下方;
- 斜下方如果有黑棋子,可以走到有黑棋子的位置;
问白棋子有可能走到最下面一行的多少个格子。
解题思路:
很容易想到按行递推,由当前可行的位置递推到下面一行的可行位置,但这样会超时。发现题目黑棋子的个数是较少的,如果围绕黑棋子个数来处理,则可行。
于是想到维护当前行的可行位置集合,遍历下一行的所有黑棋子位置,对于某个黑棋子:
- 如果它的正上方的位置存在于集合,则这个位置需要删去
- 如果它的左上角或右上角在集合,则这个位置可以在下一行的可行位置集合中,需要加上;
这样就可以解决了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
map<int, set<int>> mp;
for (int i = 0; i < m; i ++ )
{
int x, y;
cin >> x >> y;
mp[x].insert(y);
}
set<int> S;
S.insert(n);
for (auto &[x, ys] : mp)
{
set<int> add, del;
for (auto &u : ys)
{
if (S.count(u + 1) || S.count(u - 1)) add.insert(u);
if (S.count(u)) del.insert(u);
}
// 注意顺序
for (auto &u : del) S.erase(u);
for (auto &u : add) S.insert(u);
}
cout << (int) S.size() << '\n';
return 0;
}
D - Shortest Path on a Line
题目链接: D - Shortest Path on a Line
题意:
$n$ 个点在一个数轴上,可以加上 $m$ 条边,第 $i$ 条边的限制是加在 $[a_i, b_i]$ 之间,且长度为 $c_i$ ,问从 $1$ 走到 $n$ 的最短路。
解题思路:
最好画图来观察,可以直接加上 $m$ 条边,每条边都是从 $a_i$ 到 $b_i$ ,长度为 $c_i$ ,再给除了最左边的点以外的所有点,加上一条到左边的点的边,长度为 $0$ ,对图跑一边最短路即可。
代码如下:
#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long) 1e18;
template <typename A, typename B>
vector<A> Dijkstra(const vector<vector<pair<int, B> > > &g, int start, A INF = numeric_limits<A>::max()) {
int n = static_cast<int>(g.size());
assert(start >= 0 && start < n);
vector<A> dist(n, INF);
dist[start] = 0;
priority_queue<pair<A, int>, vector<pair<A, int> >, greater<pair<A, int> > > heap;
heap.emplace(dist[start], start);
while ((int) heap.size() > 0) {
auto [d, u] = heap.top();
heap.pop();
if (dist[u] != d) {
continue;
}
for (auto &[v, w] : g[u]) {
if (dist[v] > w + dist[u]) {
dist[v] = w + dist[u];
heap.emplace(dist[v], v);
}
}
}
// returns INF if there's no path
return dist;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
for (int i = 1; i < n; i ++ ) g[i].emplace_back(i - 1, 0);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
a -- , b -- ;
g[a].emplace_back(b, c);
}
auto dist = Dijkstra(g, 0, INF);
if (dist.back() == INF) dist.back() = -1;
cout << dist.back() << '\n';
return 0;
}
D - Match Matching
题目链接: D - Match Matching
题意:
火柴拼数问题,给定 $m$ 根火柴,只能出现某 $n$ 个数字,问能拼出来的最大数字是多少。
解题思路:
比较数的大小首先要比较位数,再从高位比较到低位,因此可以考虑用 DP ,找到能够拼出的位数最多的数,最后倒推找方案即可。
注意事项:
因为要保证找到最大的数,因此找方案时拼数的顺序要和一开始拼数的顺序是相反的。
代码如下:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
cin >> m >> n;
vector<int> a(n);
for (auto &u : a) cin >> u;
// 从小到大拼数
sort(a.begin(), a.end());
vector<int> cost{0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
vector<int> f(m + 1, -1);
f[0] = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j <= m; j ++ )
{
int tot = j + cost[a[i]];
if (tot <= m) f[tot] = max(f[tot], f[j] + 1);
}
int len = f[m], cur = m;
vector<int> res;
while (len -- )
{
// 从大到小倒推
for (int i = n - 1; i >= 0; i -- )
{
int pre = cur - cost[a[i]];
if (pre >= 0 && f[pre] != -1 && f[cur] - f[pre] == 1)
{
cur = pre;
cout << a[i];
break;
}
}
}
cout << '\n';
return 0;
}
D - Double Landscape
题目链接: D - Double Landscape
题意:
给定一个 $n\times m$ 的网格, $1$ 到 $n\times m$ 都出现且仅出现一次,给出每行的最大值和每列的最大值,问有多少种排列方法满足。
解题思路:
每个数如果出现在多个行或者多个列,答案肯定为 $0$ 。
维护两个数组, $r[x]$ 表示 $x$ 所在的行, $c[x]$ 表示所在的列,再维护两个变量, $row$ 表示已经填了至少一个数的行的个数, $col$ 表示已经填了至少一个数的列。
然后考虑从大到小填上所有数,可以这个数在某一行或列填上的第一个数,那么它一定数这行或列的最大值;如果它不是某行或列的最大值,那么它一定不能作为任何行或列的第一个数来填。
对于某个数 $x$ ,有以下情况:
- 如果它是某一行的最大值,且是某一列的最大值,那么它的位置确定的, $row$ 和 $col$ 分别递增;
- 如果它是某一行的最大值,那么它可以填在 $col$ 个位置上, $row$ 递增;
- 如果它是某一列的最大值,那么它可以填在 $row$ 个位置上, $col$ 递增;
- 否则它有 $row\times col$ 个候选位置,但需要和已经填的所有数的个数比较,看是否还有空位。
代码如下:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = (int) 1e9 + 7;
int main()
{
int n, m;
cin >> n >> m;
vector<int> r(n * m, -1);
int res = 1;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
x -- ;
if (r[x] != -1) res = 0;
else r[x] = i;
}
vector<int> c(n * m, -1);
for (int j = 0; j < m; j ++ )
{
int x;
cin >> x;
x -- ;
if (c[x] != -1) res = 0;
else c[x] = j;
}
int row = 0, col = 0;
for (int x = n * m - 1; x >= 0; x -- )
{
if (r[x] != -1 && c[x] != -1) row ++ , col ++ ;
else if (r[x] != -1) res = (long long) res * col % mod, row ++ ;
else if (c[x] != -1) res = (long long) res * row % mod, col ++ ;
else
{
int cand = row * col;
// 要查看是否有空位
res = (long long) res * max(0, cand - (n * m - 1 - x)) % mod;
}
}
res = (res % mod + mod) % mod;
cout << res << '\n';
return 0;
}
E. New Year Parties
题目链接: E. New Year Parties
题意:
在一个数轴上,某些位置有若干个人,每个人只可以原地不懂,或者走到相邻的两旁,问最少和最多可以使得多少个位置上有人。
解题思路:
最少和最多分开处理。
最少的情况,从左到右枚举,遇到第一个非 $0$ 位置 $x$ ,直接让它们都走到 $x+1$ , 此时 $x+2$ 可以不用考虑,因为如果有的人的话,这里的人也可以走到 $x+1$ ,如果没有人,也不会使得情况更差,因此直接考虑 $x+3$ ,继续上面的过程即可。
最多的情况,因为每个人最多给答案贡献 $1$ ,因此只要有空位就占就行,从左到右枚举,尽量让人往左边分配,如果 $x$ 位置上有人,看 $x-1$ 是否有人,如果没有,则分配一个过去,如果有,则不用分配,然后看当前位置是否有大于 $1$ 个人,如果有多余的话,则可以往右边分配一个人,最后统计有人的位置即可。
注意事项:
注意处理最少的情况时,不能求出连续的非 $0$ 段,然后对长度除以 $3$ 上取整,比如 $[1,0,1]$ ,求出 $2$ ,但实际上可以是 $1$ 。
代码如下:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 2);
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
a[x] ++ ;
}
int mn = 0;
for (int i = 1; i <= n; i ++ )
if (a[i])
{
mn ++ ;
i += 2;
}
int mx = 0;
for (int i = 1; i <= n; i ++ )
{
if (a[i] && !a[i - 1]) a[i - 1] ++ , a[i] -- ;
if (a[i] > 1) a[i + 1] ++ , a[i] -- ;
}
for (int i = 0; i <= n + 1; i ++ ) mx += !!a[i];
cout << mn << ' ' << mx << '\n';
return 0;
}
E. The Contest
题目链接: E. The Contest
题意:
三个人有若干个数,这些数两两不同,每次操作可以使一个数从一个人到另一个人手上,问最少操作多少次可以使得第一个人的数都是这个数列的前面一段,第三个人的数都是这个数列的后面一段,第二个人的数是剩下的全部数。
解题思路:
一开始想建图,但发现没什么想法,于是遇事不决上 DP 。数组 $at[i]$ 表示 $i$ 初始时在第几个人的手上,完成操作后,$at[i]$ 应该是一个不递减的数列。
定义 $f[i][j]$ 为 $i$ 到 $n$ 已经分配完成,且 $i$ 在第 $j$ 个人的手上,操作的方案,属性数最小值,这样的话转移就很简单了,直接看代码应该就可以了。
代码如下:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
vector<int> sz(3);
int n = 0;
for (auto &u : sz) cin >> u, n += u;
vector<vector<int>> a(3);
vector<int> at(n);
for (int i = 0; i < 3; i ++ )
{
a[i].resize(sz[i]);
for (auto &u : a[i])
{
cin >> u;
u -- ;
at[u] = i;
}
}
vector<vector<int>> f(n, vector<int>(3));
for (int j = 0; j < 3; j ++ ) f[n - 1][j] = (int) (at[n - 1] != j);
for (int i = n - 2; i >= 0; i -- )
for (int j = 0; j < 3; j ++ )
{
int mn = INF;
for (int k = j; k < 3; k ++ ) mn = min(mn, f[i + 1][k]);
f[i][j] = mn + (int) (at[i] != j);
}
cout << min(f[0][0], min(f[0][1], f[0][2])) << '\n';
return 0;
}
E. 1-Trees and Queries
题目链接: E. 1-Trees and Queries
题意:
给定一棵树,多次询问,每次询问给定 $x, y, a, b, k$ ,表示给 $x$ 和 $y$ 加上一条边,是否存在一种走法, $a$ 到 $b$ 经过 $k$ 条边,其中边和点都可以重复走。
解题思路:
加边以后,有以下五种情况:
- 从 $a$ 出发,在中间的两个点重复走,走到 $b$ ;
- 从 $a$ 走到 $x$ ,在 $x$ 和 $y$ 之间重复走,从 $x$ 走到 $b$ ;
- 从 $a$ 走到 $y$ ,在 $y$ 和 $x$ 之间重复走,从 $y$ 走到 $b$ ;
- 从 $b$ 走到 $x$ ,在 $x$ 和 $y$ 之间重复走,从 $x$ 走到 $a$ ;
- 从 $b$ 走到 $y$ ,在 $y$ 和 $x$ 之间重复走,从 $y$ 走到 $a$ ;
分类讨论一下重复走需要的奇偶性即可,只要五种情况符合一种,就存在。
代码如下:
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
template <typename A>
class Lca {
public:
int n, root, lg;
vector<A> dist;
vector<int> depth;
vector<vector<int>> fa;
Lca(const vector<vector<int>> &g, int root) {
n = static_cast<int>(g.size());
lg = 32 - __builtin_clz(n);
fa.resize(n);
dist.resize(n);
depth.resize(n);
for (int i = 0; i < n; i++) {
fa[i].resize(lg);
}
depth[root] = 0;
fa[root][0] = root;
vector<int> q;
q.push_back(root);
for (int qq = 0; qq < (int) q.size(); qq++) {
int u = q[qq];
for (int i = 1; i < lg; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (auto &v : g[u]) {
if (v == fa[u][0]) {
continue;
}
depth[v] = depth[u] + 1;
dist[v] = dist[u] + 1;
fa[v][0] = u;
q.push_back(v);
}
}
}
int getLca(int a, int b) const {
assert(a >= 0 && a < n && b >= 0 && b < n);
if (depth[a] < depth[b]) {
swap(a, b);
}
for (int k = lg - 1; k >= 0; k--) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) {
return a;
}
for (int k = lg - 1; k >= 0; k--) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
A getDist(int a, int b) const {
assert(a >= 0 && a < n && b >= 0 && b < n);
int anc = getLca(a, b);
return dist[a] + dist[b] - 2 * dist[anc];
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
cin >> a >> b;
a -- , b -- ;
g[a].emplace_back(b);
g[b].emplace_back(a);
}
Lca<int> lca(g, 0);
int q;
cin >> q;
while (q -- )
{
int x, y, a, b, k;
cin >> x >> y >> a >> b >> k;
x -- , y -- , a -- , b -- ;
bool flag = false;
// a -> b
int dab = lca.getDist(a, b);
if (k >= dab && (k - dab) % 2 == 0) flag = true;
int dax = lca.getDist(a, x);
int day = lca.getDist(a, y);
int dxb = lca.getDist(x, b);
int dyb = lca.getDist(y, b);
// a -> x -> b
if (k - dax - dxb >= 0 && (k - dax - dxb) % 2 == 0) flag = true;
// a -> x -> ... -> y -> b
if (k - dax - dyb >= 0 && (k - dax - dyb) % 2 == 1) flag = true;
// a -> y -> b
if (k - day - dyb >= 0 && (k - day - dyb) % 2 == 0) flag = true;
// a -> y -> ... -> x -> b
if (k - day - dxb >= 0 && (k - day - dxb) % 2 == 1) flag = true;
cout << (flag ? "YES\n" : "NO\n");
}
return 0;
}
E. Gold Transfer
题目链接: E. Gold Transfer
题意:
一棵树初始时只有一个点,第 $i$ 次操作是以下其中一种:
- 给树中某个点加上一个点,它有 $a_i$ 个物品,单价 $c_i$ ,保证小于它的父节点的单价;
- 给定 $v$ 和 $w$ ,要在 $v$ 到根节点路径上的所有点购买 $w$ (若不够则买完)个物品,输出购买的个数和花费最少值。
解题思路:
一道很有意思的题目,一个重要的性质是子节点的花费一定比父节点的要大,因此每次买物品,一定优先买靠近根节点的物品,每次加入一个点时,就维护它的倍增数组 $f[i][j]$ 表示从 $i$ 走 $2^j$ 步可以走到的位置。如果要从 $v$ 到根节点的路径购买 $w$ 个物品,则找到最靠近的根节点的还有物品的点,尽量买,直到 $w$ 或 $a[v]$ 为 $0$ 。
注意事项:
因为是在线询问,每次操作都是永久的,因此时间复杂度并不会太高。
代码如下:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int q;
cin >> q;
vector<long long> a(q + 1), c(q + 1), p(q + 1, -1), son(q + 1);
cin >> a[0] >> c[0];
vector<vector<int>> f(q + 1, vector<int>(20));
for (int i = 1; i <= q; i ++ )
{
int type;
cin >> type;
if (type == 1)
{
cin >> p[i] >> a[i] >> c[i];
f[i][0] = p[i];
for (int j = 1; j < 20; j ++ )
f[i][j] = f[f[i][j - 1]][j - 1];
}
else
{
int v;
long long w;
cin >> v >> w;
long long cnt = 0, cost = 0;
while (a[v] > 0 && w > 0)
{
int cur = v;
for (int j = 20 - 1; j >= 0; j -- )
if (a[f[cur][j]])
cur = f[cur][j];
long long take = min(a[cur], w);
w -= take;
a[cur] -= take;
cnt += take;
cost += take * c[cur];
}
cout << cnt << ' ' << cost << endl;
}
}
return 0;
}
大佬关注了
谢谢~