2026牛客杭电多校补题速记

前言整个暑假打的非常红温感觉之前从来没写过这么难的题。给我一种“全世界算竞水平提升一倍唯独我不变”的感觉。一堆题都不会但也学到了很多新知识。由于本人水平有限只根据自身水平进行补题题解写的也比较简单还没补的题后续可能还会补。如有错误还请指出。牛客多校1G Precision Error?!这题也是题注意到允许存在不超过0.01的误差那么我们可以在距离为 1 的两堆各放 n 个点保证相邻两个点在距离在误差范围内即可。代码咕咕~J Show Hand大模拟似乎没什么好说的对每一种状况赋一个权值分别枚举对方与你选的牌即可。代码C Fish Eating题解写的是用Kruskal重构树不过好像也可以只用一个并查集题目中有一个地方很关键鱼的大小是非递减放置的。如果把每个鱼看成是一个节点新加进去的鱼一定能够吃掉周围所有的鱼。所以第一问的答案就是当前鱼的集合的大小。难点在第二问。如果新的鱼 u 能够吃掉一个集合里最大的鱼 v 那么就把集合最大的鱼的父节点指向当前的鱼。fa[v]u令 i 节点鱼的大小为 a[i]子树大小为 sz[i]如果 v 节点要吃掉 u那么 a[v]a[u]-sz[i]1。我们令 up[i] 表示节点 i 要吃掉父节点所需的最小大小那么第二问的答案就是 max(0,up[i]-a[i]) 。我们可以动态维护每个节点的 up[i] 。如果新加进来一个节点要把他子树里所有的 up 都取 max这里可以直接在并查集里的 find 函数里实现父节点向子节点传递信息。核心代码int find(int x) { if (fa[x] ! x) { int temp find(fa[x]); up[x] max(up[fa[x]], up[x]);//父节点向子节点传递up fa[x] temp; } return fa[x]; }代码H Rock-Paper-Scissors Master又是一个模拟题...如果 k 很小我们可以直接暴力枚举两个人出的牌和获得的牌并计算期望。如果 k 很大注意到当经过了足够多的轮次双方的牌型逐渐趋于固定每回合增加的得分也逐渐趋于固定。于是我们可以暴力枚举到10000轮超过的部分根据每一轮增加的得分可以直接等比例计算得到。思路并不难只不过枚举双方的状态和计算期望的代码比较复杂。代码牛客多校2整个暑假打的最史的一把B Bitwise Maximization线性基什么时候变成人人都会的签到题了没学过线性基的可以看我之前的笔记。令 sum 表示所有数的异或和当 sum 的第 i 位为1时说明第 i 位有奇数个1那么我们无论怎么放第 i 位都只能有一个1的贡献所以我们只考虑sum 第 i 位为0时能否拆成两个1。对于每一个 a[i]为了不考虑 sum为1的位置可以将 a[i] 异或上 ~sum再插入到线性基中线性基中的最大值 res 可以分出两个贡献答案就是 res*2sum。代码G GCD Graph这题怎么过了这么多人个人感觉这题并没有那么简单分治莫比乌斯DAG DP。如果 i 与 n 互质那么 cost(i,n)1。现在问题是如果不互质cost是多少感性的想i 与 n 不互质那么 i 与 n 中间一定会有一个数 j 使得 j 与 i 和 n 都互质即 cost(i,n)2通过打表也可以发现这种情况大多情况都成立。那么我们就猜测 cost 只存在1和2的情况。然而写了一版给WA了那么只能说明存在 cost 大于2。继续思考令 j 为第一个小于 n 的质数如果 ijn那么 cost 必然小于等于2计算 i 到 j 中有多少个数与 n 互质可以用莫比乌斯反演快速得到。 如果 ij由于 j 与 n 相差很小可以直接用DAG DP暴力求。代码L Lazy Shuffling求拓扑序的状压DP题感觉这题远比G简单可惜赛时被前面的题卡了没时间看这题。如果 p[i]p[j] (ij) 那么交换位置后必然会产生 1 或者 -1 的贡献由于想要和的绝对值的答案最大所有的贡献一定全是 1 或全是 -1。而且这两种情况是对等的只需要计算其中一种情况的答案乘2就是最终的答案。我们给所有 p[j]p[i] 建立一条有向边于是就变成了求一个有向图的拓扑序数量。用mask标记每个节点之前要选哪些节点状压DP即可解决。代码F Fabulous Tree一道比较复杂的树形DP题。令 dp[u][i] 表示节点 u 的子树中的最小值比 u 节点的值小 i 的情况下与最大值是多少那么 u 节点的答案就是最小的 dp[u][i]i 。如果 u 节点与子节点 v 相差了 w 那么有两种情况如果 u 节点值大于 v 节点那么最小值与根节点 u 的差从 i 变成了 iw最大值变成了 max(0,dp[v][i]-w)如果 u 节点值小于 v 节点那么最小值与根节点 u 的差从 i 变成了 i-w最大值变成了 dp[v][i]w。同一颗子树里同一个 i 要取 min 不同的子树间同一个 i 要取 max。为了避免不同子树间的影响可以用一个 tmp 数组记录一下。核心代码void dfs(int u, int fa) { for (auto [v, w] : vec[u]) { if (v fa) continue; vectorint tmp(W * 2 5, INF); dfs(v, u); for (int i 0; i W * 2; i) { if (i w W * 2)//a[u]a[v] tmp[i w] max(0, dp[v][i] - w); if (i - w 0)//a[u]a[v] tmp[i - w] min(tmp[i - w], dp[v][i] w); } for (int i 0; i W * 2; i) dp[u][i] max(dp[u][i], tmp[i]); } for (int i 0; i W * 2; i) ans[u] min(ans[u], dp[u][i] i); }代码牛客多校3B Buy One More人人都会的推公式题唯独我不会推...咕咕~F Not Aqre 2矩阵快速幂优化一行总共满足条件的状态数量有矩阵快速幂的时间复杂度是这种状态表示显然会超时需要对状态进一步优化。考虑到每一行的状态不是由具体的数字决定而是由该行的形状决定如第 i 个数要么等于第 i-2 个数要么与 i-1 和 i-2 都不同。那么我们就可以省去第一个数将状态压缩到代码写的好一点刚好可以极限通过代码G Matrix Marking二维差分离散化还是比较好想的。对每个数分开考虑对同一个数坐标离散化。枚举每一个数从左往右枚举列对于某一列要给这一列的最低点与他左侧最高点所构成的矩形1这一列的最高点与他右侧最低点所构成的矩形1。预处理每一列的前缀最小值和后缀最大值再用二维差分实现矩形加法。代码牛客多校4C Retest Queue状压DP高维前缀和用 st 记录当前状态下每个测试点是否被选令 f[i][st] 表示在 st 状态下通过第 i 个测试点所消耗的时间。用高维前缀和可在实现。之后答案的状态转移就比较简单了。一个很大的问题是写成 f[1M][M]会超时写成f[M][1M] 就过了。代码牛客多校5I Sequence Operation 2构造题对于第 i 位如果第 i 位是 1 并且那么可以在第 i 位异或上 i 在二进制下的最高位。例如54^1148^6。从而消掉第 i 位的1并将1从高位往低位传递。但由于异或的数不能为0所以在时没法消掉1。于是在这一步操作后我们只剩下了上的1。剩下的1我们可以从低位往高位两两合并这样就只剩下最多一个1了。如果某一位异或上了他本身这种情况不合法特判即可。代码C Number比较抽象的构造题如图先考虑十进制下是如何构造的Q向右偏移两位进位与不进位穿插这样会多出两个位置再按图中方式塞回到原来的地方。知道十进制是如何构造的之后B进制仿照十进制的方法构造即可。B小于等于2和奇数的情况打表发现不存在B等于4时上述构造规则不成立需要特判。不过这种构造方法感觉有点离谱赛时很难想出来......代码B Enlarged Badge666闵可夫斯基和都来了暂时不打算学...咕咕~牛客多校6F Full AlphabetKMP/Z函数拓扑序状压DP令第 i 位开始的 border 长度为 x那么第 x1 位的字符必须严格小于第 ix 位的字符。border 可以用 KMP或 Z 函数快速得到。之后再对这两个字符建立一条有向边于是就得到了26个字母的拓扑序。求该26个字母的拓扑序数量方法和第二场的 L 题一模一样用mask标记每个节点之前要选哪些节点状压DP即可解决。代码I Integer Function超超超复杂的数位DP令 dp[i][flag][b1][b2][jin] 表示第 i 位为止是否贴紧上边界第一个数是否选过第二个数是否选过第二个数是否进位。由于加法存在进位的影响所以从低位往高位DP。对于每一位 i 枚举这一位是否选令第一个数选了 numd 的第 i 位为 pd那么第二个数就是 (numpdjin)%2新的进位就是 (numpdjin)/2然后再枚举这一位是否选就可以得到递推式。如果之前某个数已经选过了那么这一次就不能再选了。从低位往高位计算时可以用记忆化搜索。代码牛客多校7A Infiltrate Angels Domain超复杂的贪心题从高位往低位枚举如果某一位能不异或就不异或否则就将这一位异或并计算答案。这样贪心显然是对的但最大的问题是如何判断这一位能不能不异或。我们可以记录一下当前必须要异或的有哪些位置。当枚举到第 i 位时想要让整个序列保持不递减那么每个数要尽可能小。所以从左往右枚举每一个数找第一个大于等于前一个数的数。如何找第一个大于等于前一个数的数呢我的做法是从高位往低位DP找第一个大于前一个数和是否等于前一个数。官方的方法似乎更简洁从高位往低位判断该位不选是否仍然大于等于前一个数。代码D Tenkaichi Budōkai贪心树状数组/线段树感觉是这三题里最简单的一题。令P当前待选 p[i]Q当前待选 q[i]显然如果 p[i]等于q[i] 则立即停止如果其中有一个等于冠军选手 x 则必然选另一个。如果这两个人都不是 x 那就要考虑谁胜谁败。感性的想离停止即在另一个数组里前面还有几个人最近的人一定先选因为这个距离失败最近的人最危险。如何计算一个人在另一个数组里前面还有几个人如果当前删掉的人的编号为 i 在另一个数组里的位置为 j 那么就在另一个数组里的第 j 位置1表示这个位置删掉了一个人第 i 位置前面删掉了几个人就是他的前缀和。由于这个前缀和需要动态维护所以可以用树状数组或线段树动态维护单点加和区间查询。代码H Modulo Triples超阴间的构造题如图构造 xyz把3的倍数拎出来按如图方式构造最后剩下的一个数单独和1与0组。我并不清楚人类的大脑要如何才能在赛时想出这种构造方法......牛客多校8M KV Cache纯字典树题添加字符串时统计字典树中边的数量如果数量超过上限了优先把最晚出现的节点删掉如果有多个节点同时出现优先把深度最大的节点删掉。代码咕咕~牛客多校9D Escape Root很喜欢这道树上启发式合并的题记录每个节点有哪些人同时记录每个人到达根节点的时间点。把每一个节点还没消失的人传递给他的父节点同时记录他的父节点有哪些人在同一时刻到达根节点。对于每一个节点我们可以知道当前节点子树内有哪些人没有消失同时还知道当前节点的子树内有哪些人在同一时刻到达根节点再把同一时刻到达根节点的人删掉再把没消失的人传递给父节点。如果暴力的将一个节点所有没有消失的人传递给父节点最坏的情况下所有的节点都把所有的人传递给父节点时间复杂度是O(nm)肯定会超时。由于一个节点需要获取子树的所有没消失的人孩子节点信息要传递给父节点不同的子树间不能有影响这显然是树上启发式合并的板子题时间复杂度O(mlogn)。代码F Light the Lamp贪心状压如图一开始每个点都能看成一个1x1的正方形用栈维护正方形从左往右枚举每一个正方形看看当前正方形能不能与前一个栈顶正方形合并能合并就合并然后放回栈内。代码牛客多校10本场比赛我们队一共只过了三题第一道计算几何第二道推公式求极限第三道推公式求积分算法题写成了数学题...K Team Formation状压DP对于每一种状态先固定一个必须要选的人再枚举剩下要选的两个人再用记忆化搜索优化。不过我不清楚这个时间复杂度为什么是够的......代码B Slot Machine不知道咋队友推出的这个公式...暂时先不补咕咕~杭电多校11004 搭积木每个节点视为一个连通块记录每个连通块的 A 值与 B 值把所有连通块放到堆里按照 A/B 升序排序每次取出最小的两个合并再放回堆里。Submit #14660杭电多校21004 坪厕鸡大模拟把每支队伍最早的提交放到等待队列里再把等待队列里提交时间最早的放到评测队列里把最早评测完成的队伍的最早提交再放到等待队列里。Submit #41461007 另一个 shu 论问题树上启发式合并莫比乌斯反演对于每一个节点需要找出所有子树中是该节点倍数的点的数量和不同子树内gcd等于该节点的点的数量。对于每一个节点他的子树内有哪些点需要用树上启发式合并快速找到。要找出所有子树中是该节点倍数的点的数量只需要在找一个节点的同时计算子树内有几个点是父节点的倍数。要计算不同子树内gcd等于该节点的点的数量可以先找出所有节点两两组合gcd为该节点的数量再减去同一个子树内gcd等于父节点的数量两两组合的gcd可以用莫比乌斯反演快速求出。代码咕咕~杭电多校31004 toys本人不会网络流等学会了再补喵~1002 The World Cup数学题如果只考虑赌夺冠对于第 i 支队伍夺冠花费1元可以获得 x[i] 元也就是说想要获得1元需要花费 1/x[i] 元。由于答案求的是最坏情况那么答案每加1需要花费元。如果只考虑赌不夺冠对于第 i 支队伍夺冠令其他队伍花费1元可以获得 y[i] 元也就是说想要获得一元需要花费 1/y[i] 元。由于答案求的是最坏情况那么答案每加1需要花费元。如果 c1花费的钱小于等于赚的钱正收益大答案就是 m/c。否则将 y[j] 从大到小排序如果要押注 i 支队伍赚1元所需花费枚举 i 取max即可。Submit #15083杭电多校41006 F. Median Shuffle构造题已知 a 是一个排列那么能直接得出哪些数被作为了中位数。对于一个排列中的第 i 个数可以知道他最晚可以作为第 min(i, n - i 1) 个中位数。令 b[i]min(i, n - i 1)对每一个数赋 b[i] 的优先级按 b[i]从小到大排序。根据优先级依次填入中位数如果前一个中位数小于当前中位数 i 那么就要放一个 i 和一个比 i 大的数如果前一个中位数大于当前中位数 i 那么就放一个 i 和一个比 i 小的数。如果放不了则说明不存在。Submit #5637杭电多校51012 仙人掌图超复杂的DFS对于一条边 {u,v,c} 如果 c1那么这条边一定在一条长度为 c-1 的链上。这条链有三种连接方式只跟 v 的子节点连跟 u 的另一个子节点连跟 u 的父节点连。对于一个节点 u 将 c 相同但是在不同子节点上的链互相连接成长度为 c-1 的链如果和父节点连的 c 相同则考虑是否需要将一条链延伸到父节点。每次将子节点的所有链两两配对返回当前节点与父节点的链长。答案为相同的 c 连接成长度为 c-1 的链的方案数的累乘。如果无法将所有子节点两两配对则无法构成仙人掌图。Submit #114141004 探索宝物超复杂的推公式令W为所有w之和令当前手中的宝物价值为 x 如果要重新选那么期望价值会增加可知 E 是随 x 递减的所以能找到一个分界点 t 当 xt 时一定探索否则一定不探索。令重新探索一次的概率期望探索次数。对于 xt 所贡献的期望为。对于 xt 所贡献的期望为。最后答案减去期望花费的钱。Submit #13441杭电多校61001 Grand Mex2-SAT无论怎么操作一定存在一个权值为0的节点因此mex一定不为0。对于这棵树如果让所有的父节点都指向其中一个孩子节点那么所有节点的权值都小于2因此mex最大为2。根据上面两条性质可知答案mex只能为1或2。现在只需判断什么情况下mex为1。对于当前 u 节点令与 u 节点有关的最晚的两条边为 x 和 y。如果不存在 y 那么 x 必须不能指向 u 如果存在 y 那么不能同时满足 x 指向 u 并且 y 不指向 u 。两个条件满足其一这是一个经典的2-SAT问题。根据上面两条规则建立有向边跑一个Tarjan缩点如果一条边满足与不满足两个状态在同一个SCC中则说明无法构造mex为1否则就按 dfn 给边赋值。Submit #137861006 Gcd Master快速傅里叶变换FFT欧拉函数吓哭了我将严肃学习gcd公式化简令原式A可以预处理右边部分显然是一个卷积的形式可以枚举因子 x用FFT求出每个 j 的答案最后答案累加。Submit #13283杭电多校71009 今晚吃草莓线性DP滑动窗口令 dp[i][j][k] 表示冲刺 i 次撞墙 j 次 最后停留在 k 点的最小草莓数量。对于撞墙和移动距离为 k 的情况可以直接暴力枚举进行状态转移。对于移动距离小于 k 的情况草莓数量是 [-k1,k-1] 区间内的最小值需要用滑动窗口实现状态转移。Submit #92621011 今晚吃电脑配件启发式合并把每个点看成一个连通块对于同一个连通块内的点我们对这些点进行01染色。不难发现如果对同一个颜色的数值k另一个颜色的数值就会-k。对于每两个有大小关联的点我们将这两个点所在的连通块合并。对于这两个点存在这些情况如果这两个点的数值都已经固定那么这两个数之和也是确定的这两个连通块内所有点也都固定如果其中一个点已经固定那么另一个没有固定的点也要标记为固定这两个连通块内所有点也都固定如果这两个点的数值都没有固定如果这两个点不在同一个连通块内那么就合并两个连通块并重新计算连通块内每个数的数值并染色如果这两个点在同一个连通块内并且颜色相同那么这两个点可以同时加上一个整数之后整个连通块的数都固定如果颜色不同那么无论怎么加减这两个数之和都是固定的。如果两个点数值固定但之和不等于2c则说明无法构造。可以统计每个连通块的每个颜色有哪些点暴力合并两个连通块的所有点时间复杂度是用启发式合并可以将复杂度降到。Submit #12768杭电多校81003 太近就不合法了线性DP组合数学首先假设不考虑不选 x 对于长度为 n 的数组令第 i 个编号位置为 b[i]相邻的两个编号只差绝对值不小于k则 b[i]-b[i-1]k当已经选了 m 个编号那么中间必须要空出 (m-1)(k-1) 个位置只要剩下的位置里面挑 m 个选方案数就是由递推式线性求解。现在考虑不选 x 的情况考虑容斥答案是总方法数减去选 x 的方案数。如果要选 x 左边可以选右边可以选答案就是。Submit #124831008 分数越小还是越大越好树形DP对于最小可能得分如果这棵树是一条链那么把0和1放在链的两端点mex和为 2n-1否则把 0,1,2 分别放在三个端点上mex和为 n1。对于最大可能得分对于一条长度没为 m 的链想要这条链的贡献最大一定是将 0 到 m-1 的所有事都放在这条链上并且 m 一定是放在链的两端点那么这条链的最大值就是将 m 分别放到链的两端点的答案取 max。找一条链上一个端点的前一个端点可以换根求。Submit #12237杭电多校91007 小乖的在益起随机哈希树状数组/线段树一共有 k 种口味给前 k-1 种口味赋一个随机哈希值再给最后一种口味赋负的前 k-1 种口味的哈希值求和这样如果每种口味的数量都相同哈希值求和也相同。单点修改哈希值区间查询哈希值之和用线段树或树状数组很容易实现。Submit #84381010 合法括号构造题如果这个括号串是合法括号串显然我们都知道第一个括号一定是左括号最后一个括号一定是右括号。对于一个右括号他对答案的贡献为左边的左括号数量减去左边右括号的数量。如果把减去的右括号的数量单独拎出来可以发现这是一个等差数列求和。所以现在将答案转化每个右括号左边左括号数量求和。题目给定了一个条件给定的字符串中 ? 必然连续即只存在一串连续的 ? 那么先把整个字符串分成以 ? 串作为分割的三部分已知所有左括号和右括号的数量还知道当前字符串内有多少左括号和右括号那么也能知道这个?串内有几个左括号和右括号。左部分和右部分的右括号他左边的左括号的数量都是确定的中间部分右括号左边也一定有左部分左括号的数量那么就能求出中间部分右括号对答案的总贡献。现在核心问题转化为 当前有 x 个左括号y 个右括号总贡献为 t 当前多出 left 个左括号你需要构造出这个字符串。因为左括号放右边可能不合法放左边一定合法可以优先把左括号全放左边但是这样会多出一些贡献再一次看能不能把右括号放回前面。这样就能完成构造了。核心代码void cal(int x, int y, int t, int left)//x个左括号,y个右括号,要有t个贡献,有left个多余的左括号 { t x * y - t;//左括号全放左边多出t个贡献 while (x || y) { if (left 0 || y 0)//左边没左括号了当前只能放左括号 { cout (; x--; left; } else if (x 0)//没左括号了只能放右括号 { cout ); y--; left--; } else if (t x)//当前可以放右括号 { cout ); t - x; y--; left--; } else//当前只能放左括号 { cout (; x--; left; } } }Submit #6126​​​​​​杭电多校101003 大户爱的宿舍又是网络流等我学会了再补喵~咕咕~1004 大户爱的干草堆J函数不过我怎么是第一次听说Jordan 函数啊冷知识只要预处理所有因子出现的位置查询的时候枚举 k 的所有因子计算每个因子在区间内出现次数答案累加就完成了。没学过J函数或许也有别的推法吧Submit #8210