程序设计工作室1月28日内部训练赛 题解先说一下整体情况。这次内部训练赛一共6道题定位是给工作室春季招新前做一次全员摸底难度从签到到压轴逐步拉高覆盖了字符串处理、前缀和、二分答案、背包DP、带约束线性DP、状态压缩BFS这些竞赛里出场率极高的经典套路。赛后有不少同学反馈说题目看着眼熟但写起来总差一口气这其实就是典型的练习量没跟上思路。所以我把每道题的完整解法、推导过程、参考代码和一些踩坑记录整理出来希望对正在刷题的你有帮助。题目难度不算大入门级到进阶级之间非常适合拿来检验自己的基础是否扎实。除了题解本身我更想借这篇内容聊聊出题人为什么这么排题、每题背后在考察什么能力、以及赛后复盘应该怎么做。毕竟训练赛的意义不是把题AC掉就结束而是通过一套题把自己的知识盲区暴露出来。1. 训练赛的整体结构与题目编排思路1.1 为什么把签到题放在首位A题是一道非常朴素的字符串统计题没有任何思维门槛只要会用数组计数就能过。把它放在第一位目的不是考倒谁而是让大家在开赛前10分钟内先热手。竞赛和平时写作业不一样比赛一开始心态往往是紧绷的直接上难题容易出现低级错误比如数组开小、循环边界写错、忘记初始化。先做一道能稳妥AC的题既能建立信心也能把状态切换到竞赛节奏。这里给第一次参加训练赛的同学一个建议开赛后别急着看后面的题先花5分钟把A题这种签到题干净利落地写完。不要追求炫技写法用你最熟悉、最不容易出错的实现方式。等到提交显示绿色AC后再回头慢慢啃其他题心里会踏实很多。1.2 知识点覆盖是怎么设计的6道题分别对应了6个不同的基础能力点题号考察方向核心知识点难度定位A字符串处理计数数组、字典序比较签到B区间查询前缀和、差分思想简单C最优性问题二分答案 BFS验证中等D资源分配01背包、滚动数组中等E带约束递推线性DP、状态拆分中等偏上F状态搜索状态压缩BFS压轴这套组合是从基础编码能力→常见算法模板→组合优化思维层层递进的。前两题只要认真学过语法就能做中间两题需要掌握经典算法后两题则要求你能够为题目加入的约束条件设计新的状态表示。压轴题F虽然代码量也不大但如果没有接触过状态压缩很难想到用二进制位去表示钥匙的持有情况。1.3 内部赛常用罚时规则与做题策略工作室内部赛通常沿用ACM赛制每道题提交错误会产生罚时最终排名先按AC题数再按总用时排序。这意味着贪快乱交会付出代价。比较稳妥的策略是先通读全部6道题花几分钟判断哪些题是自己有把握的然后按难度梯度由易到难依次解决。不要在一道题上死磕超过40分钟。如果卡住了大概率是某个知识点存在盲区先跳过去做后面你能拿分的题比站在原地纠结更划算。比赛结束后再回头深挖没做出来的题补上知识漏洞这才是训练赛的正确打开方式。2. 基础题详解字符串统计与区间前缀和2.1 A题统计出现次数最多的字符题意简述给定一个只包含小写字母的字符串S长度不超过100000要求输出出现次数最多的字符。如果有多个字符出现次数相同输出字典序最小的那个。这道题的核心解法就是开一个大小为26的计数数组遍历字符串时对应位置加一最后找到最大值的同时记录字符下标。需要注意的是字典序最小这个条件因为下标从小到大对应a到z所以只要在更新最大值时使用严格大于而不是大于等于前面较小的字符就会天然获胜。参考代码#include bits/stdc.h using namespace std; int cnt[26]; int main() { string s; cin s; for (char c : s) { cnt[c - a]; } int idx 0; for (int i 1; i 26; i) { if (cnt[i] cnt[idx]) { idx i; } } cout char(a idx) \n; return 0; }2.2 A题的两个易错陷阱第一个陷阱是字符读取问题。有些同学喜欢用scanf(%c)逐字符读如果没处理好换行符第一个字符就变成了\n统计结果直接出错。建议直接用cin s读整个字符串省心安全。第二个陷阱是把字符转换成下标时忘记减去a或者反过来输出时忘记加回去。这类问题在练习时出现一次比赛时就容易因为紧张再次出现所以平时就要养成写完立马自查一遍的习惯。2.3 B题区间查询里的前缀和优化题意简述给定长度为n的数组a以及m次询问每次询问给出区间 [l, r]要求输出区间内所有元素的和。n和m最大均为100000。最朴素的做法是每次询问都遍历一次区间时间复杂度O(n*m)在数据范围下达到10^10量级这显然是无法接受的。前缀和的核心思想是预处理一个数组pre[i]表示前i个元素的和那么区间 [l, r] 的和就是pre[r] - pre[l-1]单次查询降到O(1)。实际写代码时建议把前缀和数组下标从1开始这样pre[0] 0的自然边界可以避免l1时的特殊判断。这是写前缀和题最常见也最优雅的边界处理方式。参考代码#include bits/stdc.h using namespace std; const int N 100005; long long a[N], pre[N]; int main() { int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } while (m--) { int l, r; cin l r; cout pre[r] - pre[l - 1] \n; } return 0; }2.4 为什么说前两题是手感题这两道题本身没什么思维难度但它们承担了一个很重要的功能检验基础是否牢固。比如A题考察的计数思想是后面所有哈希类题目的雏形B题考察的前缀和是二维前缀和、差分数组、树上差分等一系列进阶技巧的基石。如果你在这两道题上还出现WA、RE那说明你的代码习惯还需要重点打磨建议往后一段时间多刷一些基础题把一次写对的能力练出来。3. 常规算法题详解二分答案与01背包3.1 C题最大化最小值的二分框架题意简述一条河上有n块石头小企鹅在第1块石头上需要跳到第n块石头。企鹅一次最多跳d格距离每块石头有一个承受重量 w[i]企鹅每踩一块石头石头就会被压下去一定深度如果企鹅的重量超过石头的最大承重石头就会碎掉。假设企鹅重量是W问W最大可以是多少使得小企鹅仍然存在一条从第1块到第n块的完整跳跃路径起点和终点石头不碎。这题最关键的转化是给定一个重量W问题就变成只经过那些 w[i] W 的石头能否从1跳到n。这是一个可达性判断用BFS或者DFS都行。而W越大能走的石头越少可行性呈单调变化。所以可以对W做二分找到最大的可行W。单调性理解如果企鹅重量为W时可行那么重量更小的时候一定也可行因为更轻意味着更多石头能承受路径只会更多不会更少。这正好满足二分答案的单调条件。BFS部分的参考代码#include bits/stdc.h using namespace std; const int N 100005; int n, d; int w[N]; vectorint edges[N]; bool can(int W) { vectorint vis(n 1, 0); queueint q; q.push(1); vis[1] 1; while (!q.empty()) { int u q.front(); q.pop(); if (u n) return true; for (int v : edges[u]) { if (!vis[v] w[v] W) { vis[v] 1; q.push(v); } } } return false; } int main() { cin n d; for (int i 1; i n; i) cin w[i]; for (int i 1; i n; i) { for (int j i 1; j n j i d; j) { edges[i].push_back(j); } } int L 1, R 1e9, ans 1; while (L R) { int mid (L R) / 2; if (can(mid)) { ans mid; L mid 1; } else { R mid - 1; } } cout ans \n; return 0; }3.2 C题的二分边界与复杂度分析二分边界是很多同学最容易写崩的地方。我习惯用左闭右闭区间[L, R]初始时L取理论最小值1R取足够大的值比如数组中的最大承重或1e9循环条件是L R更新时L mid 1或R mid - 1最终ans单独记录最后一次可行的mid。这样写的好处是不会出现死循环也避免了L和R相差1时中位数取整导致的边界遗漏。每次check做一次BFS复杂度是O(n)。二分次数约log(1e9)约等于30次总复杂度O(n log V)在n100000时完全可行。这里有一个实际编码细节w[1]和w[n]作为起终点其承重是否参与判断训练赛数据里约定起终点石头不会碎所以实际判断时直接认为这两块总是可达的起点终点即可否则需要额外判断w[1] W。建议读题时看清楚这类约定不同题面处理方式不同。3.3 D题01背包的状态设计与滚动数组题意简述有n件物品每件物品有体积v[i]和价值w[i]背包总容量为V问在不超过背包容量的前提下最多能带走多少总价值。n不超过1000V不超过10000。01背包是最经典的DP入门题。定义dp[j]表示容量为j时能获得的最大价值。遍历每一件物品时需要从大到小更新dp[j]因为每件物品只能选一次。如果从小到大更新同一件物品会被重复选用那就会变成完全背包了。每次更新的转移方程是dp[j] max(dp[j], dp[j - v[i]] w[i])前提是j v[i]。最终答案是dp[V]。参考代码#include bits/stdc.h using namespace std; const int N 1005; int v[N], w[N]; int dp[10005]; int main() { int n, V; cin n V; for (int i 1; i n; i) { cin v[i] w[i]; } for (int i 1; i n; i) { for (int j V; j v[i]; j--) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout dp[V] \n; return 0; }3.4 背包题里常被忽视的三个细节第一个细节是dp数组的初始值。如果题目要求恰好装满初始值要设为负无穷只有dp[0] 0如果只要求不超过容量初始值全为0即可。本题属于后者初始化为0没问题。第二个细节是最外层循环遍历物品、内层循环遍历容量这个顺序不能反过来。如果先遍历容量再遍历物品状态转移就会混乱导致同一个物品被计算多次或者计算结果不正确。第三个细节是记得开long long当价值和容量都到1e4以上时累加结果可能超过int范围虽然本题卡得不是很紧但养成用long long的习惯能避免很多无谓的WA。4. 进阶题详解带约束线性DP与状态压缩BFS4.1 E题连续跳格限制下的最大得分题意简述一条长度为n的路径每格有一个整数分值a[i]可能为负数从第1格出发每次可以向右跳1格或2格但不能连续两次都跳2格到达第n格时结束问能获得的最高得分。如果没有不能连续跳2格这个限制这题就是最简单的dp[i] max(dp[i-1], dp[i-2]) a[i]。加了限制后一维状态解决不了因为你不知道当前这个格子是通过跳1格还是跳2格到达的而跳2格到达的格子后面一步必须受约束。解决办法是把状态拆成两维dp[i][0]表示通过跳1格到达第i格时的最大得分dp[i][1]表示通过跳2格到达第i格时的最大得分。转移规则从i-1跳1格到达i那么上一步不管是怎么到i-1的都可以执行一次1格跳所以dp[i][0] max(dp[i-1][0], dp[i-1][1]) a[i]。从i-2跳2格到达i但是上一步不能也是跳2格到达i-2的所以只能从dp[i-2][0]转移即dp[i][1] dp[i-2][0] a[i]。参考代码#include bits/stdc.h using namespace std; const int N 100005; long long a[N]; long long dp[N][2]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; // 起点初始化为格子1的分数认为通过跳0格到达 dp[1][0] dp[1][1] a[1]; for (int i 2; i n; i) { dp[i][0] max(dp[i - 1][0], dp[i - 1][1]) a[i]; if (i 2) { dp[i][1] dp[i - 2][0] a[i]; } } cout max(dp[n][0], dp[n][1]) \n; return 0; }4.2 为什么贪心在这里不成立有同学赛后问能不能直接让得分高的格子多走、遇到负分就跳过去答案是不行因为跳2格不是无条件的连续两次跳2格会直接非法。贪心只考虑局部最优但局部最优可能有历史包袱。比如一个负分格子后面跟着一个超高分格子如果为了躲负分格子跳2格可能会把自己至于下一格不能跳2格的状态反而错过更后面的收益。这种后效性问题必须靠DP来全局决策。这也是E题的核心价值让你体会为什么有些问题不能拍脑袋贪心必须引入状态来消除后效性。4.3 F题钥匙、门与状态压缩BFS题意简述给定一个 n*m 的地图包含空地、障碍物、起点S、终点T、若干扇门每个门有一个编号最多4种以及对应编号的钥匙。小人在四方向上移动一格花费一步集齐某扇门的钥匙后就可以打开这扇门通过问从S到T的最短步数。这道题如果只用普通的BFS会踩进一个经典陷阱同一个格子第一次到达时不一定是最好的到达时机因为你可能第二次到达时带着钥匙而第一次到达时没有钥匙。普通BFS的vis数组会把这个格子标记掉导致漏掉后续状态。解决办法是把钥匙持有情况并入状态维度用状态压缩来记录当前拥有哪些钥匙。因为钥匙种类最多4种可以用一个4位的二进制数表示持有情况。比如第0位为1表示有0号钥匙第2位为1表示有2号钥匙。状态设计为(x, y, mask)mask的范围是0到15。BFS的vis数组可以改为vis[x][y][mask]。走格子时分情况处理#障碍物跳过。小写字母a到d是钥匙更新newMask mask | (1 (c - a))。大写字母A到D是门检查mask中对应位是否为1如果持有钥匙就通过否则跳过。S、T、.正常通行。参考代码#include bits/stdc.h using namespace std; const int N 35; char g[N][N]; int n, m; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; bool vis[N][N][16]; struct Node { int x, y, mask, step; }; int bfs(int sx, int sy) { queueNode q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] 1; while (!q.empty()) { auto cur q.front(); q.pop(); if (g[cur.x][cur.y] T) { return cur.step; } for (int k 0; k 4; k) { int nx cur.x dx[k]; int ny cur.y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] #) continue; int nmask cur.mask; if (g[nx][ny] a g[nx][ny] d) { nmask | (1 (g[nx][ny] - a)); } if (g[nx][ny] A g[nx][ny] D) { int need 1 (g[nx][ny] - A); if (!(cur.mask need)) continue; } if (vis[nx][ny][nmask]) continue; vis[nx][ny][nmask] 1; q.push({nx, ny, nmask, cur.step 1}); } } return -1; } int main() { cin n m; int sx 0, sy 0; for (int i 0; i n; i) { cin g[i]; for (int j 0; j m; j) { if (g[i][j] S) { sx i; sy j; } } } cout bfs(sx, sy) \n; return 0; }4.4 状态压缩BFS的调试建议这种题WA了之后很难直接看数据排查我自己的调试习惯是在BFS里把每个新状态打印出来检查是否出现了同格子不同钥匙状态的情况。如果没有把mask纳入vis维度输出结果会发现第二次进入同一个格子时直接跳过了那肯定就是vis维度少了。还有一个容易出错的地方是钥匙和门的编号映射。地图上钥匙是a、b门是A、B转换时一个减a一个减A不要写混。最后提醒一下起点S本身可能就直接在终点旁边BFS第一步返回的步数是0还是1取决于你是否在出队时才判断终点。我这里是在出队时判断也就是进入终点那一格的状态出队时才返回步数所以步数计数是从起点开始每走一步加1结果是对的。如果你习惯入队时判断记得初始化step为0入队终点时返回step 1。5. 赛后复盘训练赛里最常爆掉的雷5.1 输入输出与编译细节这次训练赛有好几份代码WA在奇怪的地方最后排查下来都是低级问题。例如有人在循环里用了while(n--)但循环体里面还要用到原来的n结果n被改没了。还有人读入字符串时上一行的换行符残留导致字符串为空直接用cin s是可以绕过这个问题的但如果用了getline要小心前一次的换行符。建议提交前花10秒钟检查数组够不够大、变量类型对不对、循环边界是否多跑一次少跑一次、有没有把cin和scanf混用导致输入流状态错乱。5.2 二分边界与数组越界C题二分答案时容易出现L和R更新错位导致死循环的问题。我提供一个更稳的模板维护一个ans变量记录最后一个可行答案二分结束后直接输出ans。无论边界怎么变化只要有可行解ans一定会被记录下来。数组越界则主要出在B题的前缀和如果l不小心传成0访问pre[-1]就直接崩溃了。B题把数组下标从1开始就是为了防这个。5.3 long long 没开导致的隐性错误D题和E题都有可能出现累加结果超过int的情况。很多同学习惯性把所有变量定义成int小数据测试时一切正常一上大数据就WA。这个问题最坑的地方在于不一定会RE而是可能因为整数溢出产生一个看似合理的错误答案非常难排查。我的建议是竞赛中凡是涉及累加、求和、乘法一律用long long省下的麻烦远比写long long多出的那几秒贵得多。5.4 时间分配与心态管理这次训练赛的排名分布很有意思AC了前4题的同学绝大部分都排在前列而纠结E题导致F题没时间看的同学反而排名不高。这提醒我们一个很现实的问题比赛得分是AC题数 罚时的函数不是难题钻研深度的函数。碰到压轴题卡住时果断往下走先把所有能拿的分稳妥拿下回过头再补难题这种策略在内部训练赛和正式比赛中都适用。5.5 赛后如何彻底消化一套题训练赛结束不等于学习结束。我见过太多同学赛后只看一眼题解觉得自己会了但下次碰到同类型题还是不会写。真正有效的复盘方式是隔两天不看题解把每道题重新写一遍代码直到一遍AC为止。重点不是默写代码而是重新推导状态定义、边界条件、复杂度分析。特别是E题和F题这类有状态设计的题目一定要能用自己的话解释清楚为什么这样设状态为什么能消除后效性为什么vis要多一维。能讲清楚才是真的掌握。最后再分享一个我自己坚持了很久的复盘小技巧准备一个本子每道做错的题记录三行——错误原因、正确思路、同类题的共性特征。训练赛的价值从来不在于名次而在于每一次实战都能让自己看到几个我以为我会了但实际不会的盲点。把一套题吃透比囫囵吞枣刷十套题更有用。这套题覆盖的算法都不算偏门如果你能不看题解全做出来说明基础这块已经比较扎实了可以开始接触更综合的题型了。