牛客寒假算法集训营第一场题解：双指针、树形DP与字符串DP实战

牛客寒假算法基础集训营第一场这套题我印象挺深。难度曲线并不是那种“签到题送到嘴边、压轴题劝退所有人”的极端分布前几道确实送分但从G题开始就进入双指针、树形DP、字符串DP这些正经考点最后两道又考模型转化和临场取舍。这篇文章不打算把十道题全部流水账式过一遍我把几道有代表性的题拿出来重新推一遍包含完整思路、可提交的代码以及我实际提交时踩过的坑。你如果正在补题可以直接对着思路写如果还没做过建议先别看代码自己推一遍再看。1. 这套题的难度分区和补题顺序1.1 题目结构速览先把整场的印象版图列出来。A题是格点三角形计数属于典型公式题推清楚分类就不难但特别容易重复计数。B题是模拟签到按题意统计就行代码不展开。C题是坐标系里的计数问题需要把几何模型抽象成一维区间考场上一旦方向偏了很容易耗掉大量时间。D题是缺失数字E题是因子个数迭代这两道就是给新人热手的。F题是树上黑白点路径计数标准正难则反。G题和H题都是滑动窗口/双指针一个求最短一个求最长恰好是一对很好的对比。I题是字符串DP考的是状态设计和后缀匹配。J题是压轴模型比较综合我在考场上也没有写出来后面补题才理清楚。题号核心考点难度感知建议策略A格点几何计数简单偏中推导后直接O(1)公式B模拟签到快速过C几何转一维区间较难先略过最后补D缺失数字签到异或或求和E因子个数迭代签到数论基础F树形DP/补集计数中等重点掌握G滑动窗口/枚举中等重点掌握H双指针中等重点掌握I字符串DP中等重点掌握J综合贡献计数较难量力而行1.2 我推荐的补题顺序先说结论建议按照 A - D - E - B - G - H - F - I - C - J 的顺序来。A题虽然要推公式但它独立性强适合先花时间想清楚。D、E、B三道可以在半小时内全部写完能尽快建立信心。G和H是双指针的正面教材和反面教材放在一起做收获最大。F题需要树的基础建议在双指针之后单独花时间理解“总数减非法”。I题字符串DP其实不难但状态转移要想清楚后缀匹配的边界。C和J放到最后不是因为它们多难而是因为它们更吃考场策略补题的时候反而不着急。2. 签到题里的隐藏考点A、D、E2.1 A题格点三角形计数重点在去重A题给了一个n行m列的格点阵要在里面数面积恰好为1、且至少有一条边平行于x轴或y轴的三角形数量。数据范围很大显然是公式题不能枚举三点。面积等于1底和高必须满足两类情况底边长度为1、高为2或者底边长度为2、高为1。因为格点之间的距离都是整数其他组合给不出面积1。先看底边水平长度为1的情况。每一行有m-1条长度为1的水平边但并不是每一行都能找到距离为2的顶点行。对于第r行只有r-2和r2这两行在界内时才有合法顶点行。把所有行的合法顶点行数加起来结果是2(n-2)。顶点落在合法的行上之后列可以任选有m种。所以第一类数量是(m-1) * 2(n-2) * m同理底边水平长度为2时每行有m-2条底边合法顶点行是r-1和r1总数为2(n-1)。数量是(m-2) * 2(n-1) * m垂直方向的两种情况完全对称。底边垂直长度为1、高为2时数量是(n-1) * 2(m-2) * n底边垂直长度为2、高为1时数量是(n-2) * 2(m-1) * n到这里新手很容易直接把四个结果加起来提交然后WA。问题在于重复计数。一个三角形如果同时存在长度为1的水平边和长度为2的垂直边它既会被第一类计数也会被第三类计数。同样同时存在长度为2的水平边和长度为1的垂直边的三角形会被第二类和第四类重复计数。重复项也可以用O(1)公式算。水平和垂直方向互相独立直接相乘。第一类重复数量是4(m-1)(n-2)第二类重复数量是4(m-2)(n-1)。最终答案就是前四项之和减去这两个重复项。给一份能直接提交的C参考代码#include bits/stdc.h using namespace std; const long long MOD 1000000007; int main() { long long n, m; scanf(%lld%lld, n, m); long long ans 0; if (n 3 m 2) { ans (ans (m - 1) % MOD * (2 * (n - 2) % MOD) % MOD * (m % MOD)) % MOD; } if (n 2 m 3) { ans (ans (m - 2) % MOD * (2 * (n - 1) % MOD) % MOD * (m % MOD)) % MOD; } if (m 3 n 2) { ans (ans (n - 1) % MOD * (2 * (m - 2) % MOD) % MOD * (n % MOD)) % MOD; } if (m 2 n 3) { ans (ans (n - 2) % MOD * (2 * (m - 1) % MOD) % MOD * (n % MOD)) % MOD; } ans (ans - 4 * (m - 1) % MOD * (n - 2) % MOD MOD) % MOD; ans (ans - 4 * (m - 2) % MOD * (n - 1) % MOD MOD) % MOD; printf(%lld\n, ans); return 0; }这里有两个容易踩的坑。第一减法取模之后要加MOD再取模否则可能出现负数。第二n或m比较小的时候某些项会变成0甚至负所以每一项都要判断合法性去重项也不能想当然直接减。2.2 D题缺失数字别一上来就排序D题题意很直接给你n-1个数字范围是1到n找出缺失的那个。最朴素的做法是排序再扫一遍但完全没必要。求和方法最简单先算1到n的和减去输入数字的总和剩下的就是缺失值。也可以用异或把1到n和所有输入数字全部异或一遍成对出现的会消掉最后剩下的就是答案。这道题虽然简单但有个细节值得注意有的版本里数字可能很大求和要用long long防止溢出。用异或就没有这个顾虑。两个方法复杂度都是O(n)。2.3 E题因子个数迭代注意1的边界E题要求对一个数反复求因子个数直到结果变成2问迭代了多少次。因子个数函数就是质因数分解后每个指数加1再相乘。如果n是1因子个数是1直接看题意要求要不要特判。如果n是质数因子个数就是2迭代0次就结束。其他情况下比如12的因子个数是66的因子个数是44的因子个数是33的因子个数是2一共迭代4次。单次数论分解就够了数据范围不大复杂度大概是O(sqrt(n))。唯一要注意的是别把因子个数和质因数个数混在一起我第一次写的时候就直接返回了质因数个数样例都过不去。3. 双指针的两道经典考法G和H3.1 G题包含至少k个相同字符的最短子串G题的意思是给一个字符串要找一个最短连续子串使得其中某个字符至少出现k次。这里有一个很常见的套路不需要真的去滑动窗口而是把每个字符的出现位置单独存下来。对于字符c如果它出现了cnt次位置数组是pos[0]到pos[cnt-1]那么包含连续k个c的最短子串长度就是pos[ik-1] - pos[i] 1枚举i取最小值。枚举所有字符最终答案就是这些最小值里的最小值。def solve(s, k): pos {} for i, ch in enumerate(s): pos.setdefault(ch, []).append(i) ans float(inf) for p in pos.values(): if len(p) k: continue for i in range(len(p) - k 1): ans min(ans, p[i k - 1] - p[i] 1) return -1 if ans float(inf) else ans这个算法的复杂度是O(n)因为每个字符的位置数组加起来长度就是n。G题的关键是意识到“最短子串”一定以某个目标字符的第一次出现开头、以第k次出现结尾中间多出来的字符没有意义。3.2 H题最多改k个字符求最长连续相同子串H题给一个01串最多可以把k个字符改成另一个字符要求修改后最长的连续相同子串有多长。这个和G题正好相反G求最短H求最长而且H需要维护的是一个可变窗口。思路是分两次做一次是让最终全变成0一次是让最终全变成1。以全变成0为例窗口中0的个数是不需要修改的1的个数是需要修改的。我们需要保证窗口内1的个数不超过k然后不断扩展右端点左端点只在窗口非法时前进。def longest(s, k, target): n len(s) l 0 need 0 ans 0 for r in range(n): if s[r] ! target: need 1 while need k: if s[l] ! target: need - 1 l 1 ans max(ans, r - l 1) return ans def solve(s, k): return max(longest(s, k, 0), longest(s, k, 1))写的时候最容易犯的错误就是搞混need统计的是目标字符还是非目标字符。这里统计的是“需要修改成目标字符”的数量也就是非目标字符的数量。另一个容易错的地方是窗口非法后要先移动左指针再更新答案我见过有人把ans的更新放在while之前导致窗口不合法时也算进去了。3.3 双指针题的共同易错点这两个题放在一起看特别有意思。G题用的是位置数组因为要找最短覆盖直接枚举起点更干净。H题用的是双指针因为要找最长合法窗口窗口的左边界会动态右移。共同点是都要注意区间边界的开闭以及答案更新时窗口一定处于合法状态。我自己的习惯是双指针题先写一个暴力双层循环的版本做对拍再改成双指针。这样一旦双指针写错暴力结果能立刻告诉你哪里不对。4. F题树上的黑点路径计数4.1 正难则反总数减去全白路径F题给一棵树每个点染成黑色或白色问有多少条简单路径至少经过一个黑点。直接统计经过黑点的路径很麻烦因为一条路径可能经过多个黑点去重很容易乱。正难则反先算整棵树上的简单路径总数再减去一条黑点都没经过的路径。如果路径定义为两个不同点之间的路径总路径数是n*(n-1)/2。全白路径就是只由白色点组成的连通块内部路径。把所有白点连通块大小求出来每个大小为s的连通块贡献s*(s-1)/2累计就是全白路径数。答案就是总数减去这个值。4.2 用DFS统计白色连通块统计白色连通块可以DFS也可以并查集。DFS更直接从一个白点出发只走白点能访问到的所有点构成一个连通块。#include bits/stdc.h using namespace std; const int N 100005; vectorint g[N]; int color[N]; int vis[N]; int dfs(int u) { vis[u] 1; int sz 1; for (int v : g[u]) { if (!vis[v] color[v] 0) { sz dfs(v); } } return sz; } int main() { int n; scanf(%d, n); string s; cin s; for (int i 1; i n; i) { color[i] s[i - 1] - 0; } for (int i 0; i n - 1; i) { int u, v; scanf(%d%d, u, v); g[u].push_back(v); g[v].push_back(u); } long long total 1LL * n * (n - 1) / 2; long long bad 0; for (int i 1; i n; i) { if (!vis[i] color[i] 0) { long long sz dfs(i); bad sz * (sz - 1) / 2; } } printf(%lld\n, total - bad); return 0; }这里有一个容易忽略的点DFS只访问白点但建图的时候黑点边也要建否则无法判断一个白点的邻居是不是白点。我一开始只加白点之间的边导致连通块统计不完整。4.3 另一种按黑点统计的思路除了补集法也可以直接按黑点统计。让每个黑点作为路径上“最靠近根的那个黑点”或者“编号最小的黑点”然后统计经过它且不经过其他已统计黑点的路径这样能避免重复。但实现起来细节更多需要维护黑点周围的白色连通块大小。对于新手我更推荐补集法代码短思路也不容易出错。补集思想在树上计数里非常常用值得多刷几道类似题巩固。5. I题字符串DP别被niconiconi吓到5.1 题面背后的状态设计I题是典型的字符串DP。给定一个字符串里面如果出现子串nico可以加a分出现niconi可以加b分出现niconiconi可以加c分问最大得分。看到这种“匹配特定模式获得分数”的题第一反应就是定义dp[i]为前i个字符能得到的最大分数。转移很自然第i个字符可以不参与匹配所以dp[i]至少等于dp[i-1]如果最后4个字符恰好是nico那么dp[i]可以由dp[i-4]a转移过来如果最后6个字符是niconi可以由dp[i-6]b转移如果最后10个字符是niconiconi可以由dp[i-10]c转移。这里的关键是“最后几个字符”的判断。不要用KMP因为模式串是固定的直接比较后缀就行。Python里可以用endswithC里可以用substr但substr会拷贝字符串效率略低也可以直接从后往前逐位比较。5.2 一份可以直接跑的DP实现def solve(s, a, b, c): n len(s) dp [0] * (n 1) for i in range(1, n 1): dp[i] dp[i - 1] if i 4 and s[i - 4:i] nico: dp[i] max(dp[i], dp[i - 4] a) if i 6 and s[i - 6:i] niconi: dp[i] max(dp[i], dp[i - 6] b) if i 10 and s[i - 10:i] niconiconi: dp[i] max(dp[i], dp[i - 10] c) return dp[n]这个DP的复杂度是O(n)三种模式串都是固定长度后缀判断是常数时间。要注意的是三个模式的长度分别是4、6、10不要记错尤其是niconiconi不是niconiconiconi我一开始把长度写成了12样例直接错。5.3 重叠匹配会不会重复计分很多人会问字符串里出现“niconico”前面的“nico”和后面的“niconi”有重叠DP会不会重复加分不会。因为dp[i]定义的是前i个字符的最优值每次转移都是把最后一段当成一个完整模式剩下的前缀是dp[i-len]。重叠的部分不是同时计分而是会被max取最大值。换句话说DP天然处理了重叠问题不需要额外加状态。这一点理解了I题就没什么难度了。6. 考场上的取舍C题和J题怎么处理6.1 C题的建模方向C题是坐标系里的一类计数问题核心是把二维几何关系压缩成一维区间。现场看到几何题不要慌先想清楚题目要数什么能不能把每个点的位置按照某个方向投影到一条线上。很多几何计数题最后都会变成“区间覆盖”或者“滑动窗口”问题一旦完成这个转化后面的计算反而是常规操作。C题真正难的不是算法而是模型抽象。很多人包括我自己很容易陷入暴力枚举直线的细节里越写越乱。补题的时候我重新做了一遍发现只要把方向相同的点归到同一组问题会立刻清晰很多。6.2 J题的贡献拆分思路J题是压轴考的是贡献拆分加前缀和优化。这类题的特点是答案很大直接枚举一定超时必须思考每一个元素对答案的贡献。本质和F题的“正难则反”有相似之处只是J题需要更细致的去重。如果考场上遇到这种题我的建议是先写出O(n^2)的暴力哪怕只能过部分数据也能帮助理解题面。然后再想怎么把某个重复计算的部分用前缀和批量处理。不要指望一步到位很多压轴题都是先暴力后优化。6.3 时间分配的通用策略这套题里C和J如果卡住超过40分钟直接跳过先把后面的题拿分。竞赛不是把所有题做完才赢是把能拿的分都拿到。先把G、H、F、I这些中等题稳定拿下比死磕一道压轴题划算得多。我补题的时候也发现C和J的模型一旦想通代码量其实不大关键还是卡在了模型转换那一步。7. 常见问题与避坑清单7.1 取模运算的细节这套题里涉及取模的题不少尤其是A题。取模不是最后做一次就行中间每一步都可能溢出所以乘法要边乘边模。减法取模时先加MOD再模防止负数的出现。这里有个习惯我特别推荐所有涉及取模的中间变量都用long long不要用int因为两个1e9级别的数乘起来就是1e18int必炸。7.2 递归爆栈问题F题如果数据范围大DFS递归可能爆栈尤其是链状树。比赛环境里Python递归默认深度很低C一般递归深度取决于栈空间。稳妥的做法是把DFS改成显式栈或者用并查集统计白色连通块。我现在写树的题默认第一反应是并查集反而少了很多递归栈的烦恼。并查集版本的核心就是先把所有白色点相邻的白色点合并然后统计每个白色连通块的size再算组合数。代码更稳也方便调试。7.3 双指针死循环的排查双指针题最常见的死循环原因是左指针没有前进。检查的时候可以打印每一步的l、r、need很快就能定位。另外右指针移动到末尾之后还要考虑窗口收缩到合法的过程中是否有更新H题的写法里已经把答案更新放在while之后就是因为窗口收缩后可能得到新的最长长度。7.4 用暴力对拍保证正确性我补这套题的时候对G、H、I都写了暴力版用来对拍。G题暴力枚举所有子串H题暴力枚举所有修改方案I题暴力DFS枚举分割方式。数据量开到100以内随机生成几十组基本上能覆盖大部分边界情况。对拍不是浪费时间它能帮你找出那些“样例过了但提交WA”的隐藏问题尤其是边界下标和空串这类情况。7.5 最后分享一个实际体会这东西我后来补题时感受特别深G题和H题放在一起看一个用位置数组枚举起点一个用双指针维护窗口看似都是滑动窗口但思考方式完全不同。A题则是所有计数题的一个缩影公式好推去重才是重点。如果你正在刷基础集训营建议把每道题都用自己的话把思路写一遍再对着标准题解查漏。能讲清楚一道题比能把代码默写出来重要得多。这套题到现在回头看依然是很好的练习材料值得二刷。