牛客游记合集
2024 牛客暑期多校训练营
整个比赛我是单打，脑子根本不够用，不要嘲讽我。
部分本文章同步发表于牛客多校比赛题解区。
为了宣传高端的洛谷文章区渲染方式我的洛谷博客，我会在每个牛客博客后方这段话：
# [强推我的洛谷博客（或者说文章区）](https://www.luogu.com.cn/user/377873#article)
# [如果渲染格式有问题，去我的洛谷博客](https://www.luogu.com.cn/article/zbyqzodf)1
把签到题切了之后看 A，A 经过思考，秒了，开始肝 I，I 用的记搜，边界条件太多，我被秒了，很失败。
赛后肝完了 I，把 B 和 D 研究后做出来了。
A
最后一位是关键，我们可以证明：序列合法与序列中奇数元素的与和是
枚举奇数个数，确保每个前
B
同样，最后一位是关键。
定义合法子序列为与和为
至少有两个合法子序列的方案数等于至少有一个合法子序列的方案数减恰好有一个合法子序列的方案数。
“至少有一个合法子序列的方案数”在 A 题中被我们秒了，我们现在需要求“减恰好有一个合法子序列的方案数”。
还是枚举奇数个数，可以发现，题目中要求的两个合法子序列肯定有一个是由所有奇数组成的子序列。我们定义在奇数中，前
在枚举奇数个数的循环中，我们枚举特殊位数量（从奇数个数到
关于将特殊位分给奇数的方案数：
设特殊位有
C
打卡题。
没了。
D
打卡题进阶版。
在评价题目中看见很多人用了“结论题”这个标签，自习想想也对，赛后讲解没懂，同学给我讲的时候我很懵，突然会了后感觉这题没这么难，我现在在写题解，除了直接写做法好像写不出来什么思考过程。
把题目要求的变形一下，定义数组
我们可以发现，这是一个关于
观察到模数是
对于答案中的每一位，我们可以在对应的桶子中计算与
具体一点：
代码不是特别难写（相比 I）。
E（不会）
F（不会）
G（不会）
H
签到题。
模拟即可，让所有双票选手躲着幸运观众。
I
一个好写的方法：记搜，把每一个格子拆成
连边，跑 dfs，做完了。
这题难点在排重。
自己造的一个 hack 大全：
3 4
----
\-/-
||\|48 个可能的询问，好多都是 hack，自己去试试吧（别让我教你怎么和 std 对拍）。
J（不会）
差不多就是两个坐标分开考虑，数据结构优化。
K（不会）
2
在前一天问了一下比我小一级的三个同校大佬的队，他们第一场切了 5 个题，%%%（我竟然被单调队列了？）。
这次我随机开题，开到了 H，试图强首杀，但是想错了，调了半天，吃饱了罚时才过，把 E、H 秒了，之后思考 C，不就是简单 DP 吗？秒了，开始做 B，感觉像高科技，但是好像根号分治可以卡过去（下面的题解我讲的是根号分治做法），就开始调，在吃了 3 个罚时后肝了出来，之后思考了一个小时 I，发现就是个会加边的 DAG（你叫它 DP 也行），之后 15 分钟秒了，开始摆烂（当时已经封榜了，看着那三个同校小孩哥不断的提交我一点思路都没有的 G，很慌，怕再次被单调队列，但还好他们没调处来。）
A（不会）
B
根号分治做法
我太菜了，只会库鲁斯卡尔算最小生成树，库鲁斯卡尔需要对边排序，通过人类的智慧，我们发现每个询问用到的边应该不会太多，我们分两种情况。
也不能叫根号分治吧，定义
点数大于分治边界的查询在整个边集则在全边集中找有用边跑库鲁斯卡尔，否则两两枚举找有用边。
经过计算
我们找到了这一次有用边组成的边集后进行排序，排序后无脑跑库鲁斯卡尔就行，我的并查集甚至只用了一个路径压缩优化。（是的，我知道你会惊讶地说：“这都能过？！”）
C
定义 dp[i][j] 为 走到 (i,j)，之后要往右走，最大的价值。
转移方程：
dp[1][i] = max(max(val[1][i], val[1][i] + val[2][i]), max(dp[1][i - 1] + val[1][i], dp[2][i - 1] + val[1][i] + val[2][i]));
dp[2][i] = max(max(val[2][i], val[1][i] + val[2][i]), max(dp[2][i - 1] + val[2][i], dp[1][i - 1] + val[2][i] + val[1][i]));D（不会）
E
打卡题。
如果输入是二的正整数次幂，可以证明无解。
否则输出
F（不会）
G
赛时的想法：
首先可以把每一个数扔到完全平方因数后的数的质因数分解抽象成一个二进制数（
题解：
首先可以把每一个数扔掉完全平方因数（记录一下价值）后的数的质因数分解分为“小质数”和“大质数”，以
我们考虑 DP（你可以把它叫 01 背包，但物品重量是按照异或来相加的）。
先处理没有大质数因数的数，之后对于每一个大质数，进行处理，每一个大质数可以被抽象为分组背包，每一组中要去恰好偶数个物品。
具体贡献计算你可以自己思考或者看代码，记得要随时取模。
H
先用前缀和预处理从第一个操作做到当前操作后到达的位置，倒序考虑，维护记录相对位置的桶子即可（桶子里面记录有关最近一个到达那个相对位置的操作序号之类的信息）。
具体方法这题看代码更好理解：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a, b, ans;
char c;
pair<int, int> m[1000005];
map<pair<int, int>, int> t;
signed main()
{
cin >> n >> a >> b;
if (a == 0 && b == 0) {
cout << n * (n + 1) / 2;
return 0;
}
for (int i = 1; i <= n; i++) {
cin >> c;
if (c == 'A') m[i] = {m[i - 1].first - 1, m[i - 1].second + 0};
if (c == 'S') m[i] = {m[i - 1].first + 0, m[i - 1].second - 1};
if (c == 'W') m[i] = {m[i - 1].first + 0, m[i - 1].second + 1};
if (c == 'D') m[i] = {m[i - 1].first + 1, m[i - 1].second + 0};
}
for (int i = n; i > 0; i--) {
t[{m[i].first - a, m[i].second - b}] = n - i + 1;
ans += t[{m[i - 1].first, m[i - 1].second}];
}
cout << ans;
return 0;
}I
为了描述方便，我用图论的说法讲了。
我们先把
节点对应卡片，节点编号对应卡片序号。
第一步，我们先对于任何一个节点，向编号下一个节点连一个边权为“随意”的边。
我们从两张卡片间隔小到大的卡片一次考虑，每一次考虑，我们计算从这种卡片的前面的一张所对应的节点和这种卡片后面的一张的紧接着的后面的卡片对应的点的最长路（其中，“随意”边权的边在这一轮计算时被当做边权为卡片上面的数字的边），计算完最长路后，我们从这种卡片的前面的一张所对应的节点到这种卡片后面的一张的紧接着的后面的卡片对应的点连接一个边权为最长路的边。