1. 比赛概览与选题策略1.1 牛客周赛是给谁准备的牛客周赛这个系列我基本从 Round 100 前后就开始跟着打。它不像 ICPC、蓝桥杯那种正赛那么严肃但也不像随便一个网站的小练习那么没氛围。平台每周固定时间放出四道题难度从易到难排布基本上覆盖了“签到题、思维题、板子题、压轴题”四种典型形态。Round 135 延续了这套节奏所以对于正在准备校招笔试、想要保持算法手感、或者刚开始打竞赛的新手来说它其实是个性价比很高的练兵场。我见过不少人纠结“要不要打周赛”觉得排名不靠前没意义。但从我的实际体验看周赛最大的价值反而在于“时间盒”和“反馈感”。你花两小时坐在电脑前目标不是拿高名次而是逼自己在有限时间内完成读题、建模、编码、调试这一整套流程。这种完整闭环在平日里刷题是很难复刻的因为刷题时你很容易卡住就直接打开题解失去现场解决问题的压力感。Round 135 这场我打到一半就明显感觉到平台上很多参赛者跟我状态类似前三题写得快第四题开始暴露问题。1.2 赛题的难度分布与整体印象按我的记忆整理Round 135 的四道题大致是这样一种节奏第一题属于看完题面就能动手的签到题但里面埋了一个输出格式的小坑第二题和第三题是常见的枚举、贪心或者简单数据结构题考验的是能不能快速把模型抽出来第四题则明显上强度需要一点数学推导再加一点优化意识。整体难度曲线比上周的 LeetCode 周赛 430 要更“竞赛化”一些也就是说题面更直白不太绕弯但数据范围往往会逼你放弃朴素写法。第四题就是热搜里提到的“区间次方和”。这道题我印象很深因为现场很多人在它身上卡了很久。倒不是说思路有多难而是“次方”这个操作天然自带爆炸趋势如果第一时间没有反应过来要做降幂和离线处理很容易一头扎进快速幂的暴力循环里等到超时才回头。我周围几个打这场周赛的朋友赛后交流时也一致认为第四题是分水岭搞懂它以后再看牛客周赛里其他类似的区间查询题思路会清晰很多。1.3 赛前目标与做题策略我个人的习惯是开赛前先给自己定一个低标和高标。低标是“前三题尽量不罚时”高标是“第四题至少写出一个能过部分数据的版本”。这种目标不是为了面子而是为了避免比赛中出现“贪多嚼不烂”的情况。第一题和第三题之间难度差距并不大很多人喜欢按顺序硬推结果卡在第三题上第四题连题目都没读。我更喜欢速读四题先判断出每一题的题型和大致复杂度要求然后从软柿子开始捏。Round 135 我采用的策略是先花五分钟把四道题扫一遍把第一题和第四题优先看。第一题用来热身找手感第四题先放进脑子里慢慢发酵。这样等我写完第三题回头处理第四题时已经拥有了一段时间的“潜意识思考”往往比盯着屏幕死磕更有效率。这个策略在多次周赛里都帮我节省了宝贵时间尤其是像“区间次方和”这种需要灵光一闪的题目提前预读比现场现想从容得多。2. 重点题拆解区间次方和2.1 题目印象与数据范围先说我对第四题题面的记忆。大意是这样的给定一个长度为 n 的数组 a数组元素的值都在 1 到 100 之间接下来有 q 次询问每次询问给出一段区间 [l, r] 和一个很大的整数 k要求计算区间内所有元素的 k 次方之和并对一个质数模数 M 取模。模数我印象里是 998244353这是竞赛中很常见的 NTT 友好质数。数据范围方面n 和 q 都能到 10 的 5 次方级别k 则是一个 64 位整数都装得下但足够让暴力快速幂吃瘪的数字。这组约束一出来其实已经暗示了两件事第一你不能每次询问都对区间内每个数单独做一次快速幂第二k 很大说明需要借助费马小定理或者欧拉降幂把指数压缩。这里有一点值得反复强调的是数组元素值域只有 100这是整道题最关键的突破口。很多人在大范围区间查询题里习惯性往线段树、树状数组方向想却忽略了这个 100 的存在。看到“值域极小、区间极大”的组合我头脑里冒出的第一反应不是数据结构而是“按值域统计”。因为任意一个数的 k 次方只取决于这个数本身和 k和它出现在哪个位置无关。那么区间内的答案就可以写成对 1 到 100 的每个可能值 v统计 v 在区间内出现的次数乘以 v 的 k 次方最后求和。这个思路属于典型的“转区间查询为值域聚合”很多区间统计题都能套用。2.2 为什么朴素做法一定超时部分选手看到这道题的第一反应是每次询问直接遍历区间把 l 到 r 里的每个元素都用快速幂算一下 k 次方再累加。这个做法的复杂度是 O(q × 区间长度 × log k)最坏情况 q 和 n 都是 10 的 5 次方区间长度也是 10 的 5 次方那总操作量直接奔着 10 的 15 次方去了哪怕只有百分之一的常数优化也是不可能跑完的。还有人可能会想那我用线段树维护区间和每次修改某个位置的值查询时区间合并这样行不行这里的问题在于查询操作不是普通加法它要求对每个元素单独做幂运算。线段树能快速合并的是“已经算好的结果”但你不可能预先把每个元素在所有可能的 k 下的幂都存下来因为 k 的范围太大了。线段树维护区间的 sum(a[i]^k) 只有在 k 固定时才有意义一旦 k 随询问变化懒标记和合并逻辑就全乱套。所以这道题真正的难点不在于“区间查询”这个动作而在于“幂运算”和“变化的 k”。你必须找到一个办法把大指数 k 先降下来再把区间查询转化成可以预处理的统计问题。想通了这一点后面的代码其实很朴素。2.3 解法核心值域压缩加上前缀计数既然数组元素只可能是 1 到 100 这 100 种值我可以先做一个二维前缀频次表。pref[v][i] 表示数组前 i 个位置中值恰好为 v 的元素个数。这个表是静态的因为题目并没有要求修改数组。预处理的复杂度是 O(100 × n)内存上如果 n 是 10 的 5 次方那么开 101 × (n1) 的 int 数组大约 40 MB在牛客的评测环境里完全可接受。每次询问给定 l、r、k我先用费马小定理把指数降下来。因为 M 是质数且所有 a[i] 都在 1 到 100 之间和 M 互质所以 a[i]^k 和 a[i]^(k mod (M-1)) 在模 M 意义下相等。记 e k % (M-1)接下来只需要求每个可能值 v 的 v^e乘以区间内 v 的出现次数累加即可。这里有一个可以优化的点不要对每组询问里的每个 v 都现场跑一次快速幂。如果两个询问的 e 相同那么它们需要的 100 个幂结果是完全一样的。所以可以把所有询问离线读进来按照 e 分组同一个组只计算一次 v^e 的幂表。这样能把大量重复的快速幂计算省掉。实际效果取决于 e 的重复程度但就算最坏情况 e 全部不同这个版本的常数也比“每查询 100 次快速幂”要稳定得多。2.4 模数不是质数时怎么办现场有朋友问过我如果题目换成一个合数模数比如 10 的 9 次方加 7 的平方之类费马小定理会不会失效答案是会。费马小定理要求模数必须是质数而且底数不能是模数的倍数。如果模数变成了合数就需要使用扩展欧拉定理。扩展欧拉定理的公式是当指数 k 大于等于 phi(M) 时a^k 模 M 等于 a^(k mod phi(M) phi(M)) 模 M。注意这里有个“加 phi(M)”的步骤很多第一次接触欧拉降幂的人会漏掉。为什么必须加上 phi(M)因为当底数 a 和模数 M 不互质时直接只取 k mod phi(M) 会丢失 a 的某些质因子带来的周期影响。加上一个完整的 phi(M) 能保证指数的“周期性”部分和“非互质”部分都被保留下来。所以在写通用模板时我通常不会只写费马小定理版本而是封装一个“智能降幂”函数先算 phi(M)然后判断 k 是否大于等于 phi(M)如果大于等于就返回 k % phi(M) phi(M)否则直接用原 k。回到这道题如果模数不是质数那我上面的代码里就要用扩展欧拉定理来把 k 转化成 e其他地方逻辑不变。但要注意如果底数 v 和模数不互质快速幂里依然要小心结果可能为 0 的情况这是正常的。总之降幂是这类题目的第一道门把它做对了后面反而轻松。2.5 实战代码与优化点下面这段代码是我按记忆整理的现场版本做了一点离线分组优化核心逻辑应该足够复现。#include bits/stdc.h using namespace std; const long long MOD 998244353LL; long long qpow(long long a, long long b) { long long res 1; a % MOD; while (b 0) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } struct Query { int l, r, id; long long k, e; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorvectorint pref(101, vectorint(n 1, 0)); for (int i 1; i n; i) { for (int v 1; v 100; v) { pref[v][i] pref[v][i - 1]; } int x; cin x; if (x 1 x 100) { pref[x][i]; } } vectorQuery queries(q); for (int i 0; i q; i) { cin queries[i].l queries[i].r queries[i].k; queries[i].e queries[i].k % (MOD - 1); queries[i].id i; } sort(queries.begin(), queries.end(), [](const Query a, const Query b) { return a.e b.e; }); vectorlong long ans(q); vectorlong long power(101, 0); long long curE -1; for (auto qu : queries) { if (qu.e ! curE) { curE qu.e; for (int v 1; v 100; v) { power[v] qpow(v, curE); } } long long sum 0; for (int v 1; v 100; v) { long long cnt pref[v][qu.r] - pref[v][qu.l - 1]; if (cnt) { sum (sum cnt % MOD * power[v]) % MOD; } } ans[qu.id] sum; } for (int i 0; i q; i) { cout ans[i] \n; } return 0; }这段代码的时间复杂度主要取决于不同 e 的数量。每个不同的 e 最多做 100 次快速幂每次快速幂约 log(MOD) 次乘法大约 30 次。如果 e 的去重效果好整体很快如果 e 全不相同最坏会退化到 10 的 7 次方量级的快速幂调用这在极限数据里可能会被卡。现场还可以进一步用一个叫“指数分块”的技巧救场预先把每个 v 的 0 到 B 次幂存一张表再把 v 的 B 倍间隔次幂存另一张表查询时把 e 拆成高位和低位两次查表相乘即可。这个技巧本质上是用空间换时间把快速幂彻底从查询路径上拿掉。写这段代码时最容易踩的坑有两个。第一个是忘记 k 是 long long求 e 的时候用 int 截断造成负数或者溢出调半天才发现是这里的问题。第二个是前缀表的下标pref[v][i] 代表“前 i 个元素”里的次数查询区间是左闭右闭 [l, r]那么 cnt 必须写成 pref[v][r] - pref[v][l-1]写成 pref[v][r] - pref[v][l] 会让答案差一个位置样例数据短时不容易暴露。3. 其余赛题复盘与横向对比3.1 A题看似简单但容易罚时的点第一题我在 Round 135 里用了八分钟左右才通过原因不是题目难而是我一开始没注意输出格式的细节。这类签到题经常会让选手输出一个浮点数或者特定精度的字符串如果你的 printf 少写了一个换行或者精度比要求少了一位评测结果就会是 WA。说实话算法题里因为输出格式被判错是最让人恼火的罚时来源。我的教训是做完签到题以后不要着急提交先把输出语句和题目要求逐字核对一遍。特别是那些要求“每个结果占一行”或者“答案之间保留两个空格”的题直接复制样例输出对比是最稳妥的。很多竞赛老手之所以罚时少并不是他们手速比你快多少而是他们习惯在提交前花十秒钟做这个检查动作。3.2 B题和C题的常见套路B题和C题我放在一起说是因为它们的解法思路比较相似。B题我印象里是一个需要处理“前缀最值”的模拟题C题则涉及一个比较明显的贪心需要证明贪心策略的正确性。做这类题时我最常用的方法是先写一个朴素枚举版本故意让它跑在数据范围较小的测试点上用来验证自己的记忆化或贪心版本是否和暴力结果一致。贪心题容易出错的地方在于想当然。你以为的“每次都取最大”不一定是最优的可能题目里还藏着某个后效性条件让局部最优不等于全局最优。我在比赛里经常用穷举小规模数据来检验这个性质如果 n 小到可以枚举所有方案那就用全排列暴力求出真正的最优答案再去和贪心策略的结果对比。这招在赛场上虽然费一点时间但能避免错误思路带来的无意义罚时。3.3 D题压轴考察的真正能力回到第四题我认为它考察的已经不单纯是某个算法模板而是一种“先限制复杂度模型再匹配工具”的综合能力。看到区间查询第一反应是数据结构看到大指数第一反应是降幂看到值域只有 100第一反应是桶计数。当这三种反应同时出现时你必须把它们拼装在一起形成“离线 降幂 前缀计数”的完整方案。这个过程很像搭积木每一块都简单难的是在有限时间内识别出该用哪几块。平时训练如果只刷标签题比如“线段树题”“数论题”很容易形成思维惯性。但周赛压轴题故意把多个标签融合到一起让你没有办法靠单一模板秒杀。这也是我为什么建议大家在周赛结束以后不要只看题解而是自己把第四题重新实现一遍写的过程中你会真正体会到“为什么前缀计数能替代线段树”“为什么离线分组能减少重复计算”这些关键问题。3.4 和 LeetCode 周赛 430 的对比上周我也打了 LeetCode 周赛 430牛客周赛和它的差别确实值得聊一下。LeetCode 周赛的题目通常更偏“工程化思维”题目背景喜欢包装成实际业务场景比如任务调度、路径规划、数据流统计数据范围相对友好很多时候 O(n log n) 甚至 O(n^2) 都能过。而牛客周赛的风格更接近算法竞赛的原始形态数据范围更大边界条件更刁钻数学题含量也明显更高。拿区间次方和这道题来说它在 LeetCode 周赛里出现的概率不是没有但数据范围大概率会被压到比较小让你可以用带缓存的暴力甚至裸快速幂过掉。牛客这边则不同它更愿意把“优化”真正作为通过门槛。所以如果一个人能稳定处理牛客周赛的第四题再回头打 LeetCode 周赛的第三题第四题往往会觉得轻松不少。反过来习惯 LeetCode 节奏的选手去打牛客周赛容易在第一场就因为 TLE 受挫这很正常不是水平问题只是平台侧重点不同。4. 现场实操与排查技巧4.1 读题顺序与时间分配我打周赛的经验是前五分钟一定不要碰键盘先用眼睛把四道题全部扫完。这个动作有两个好处一是可以提前发现有没有“水题”判断出今晚上分的主要来源二是给大脑一个后台任务让它在你写前几题的时候自动思考难题。Round 135 的第四题我就是在写第一题的过程中突然想通值域压缩这个点的。如果我只盯着第一题顺序往下做恐怕要等到卡壳才去读第四题思路启动就晚了大半场。时间分配上我的原则是每道题设一个心理警戒线。签到题十五分钟内必须交第二题第三题三十分钟内解决第四题如果真的卡到比赛结束前二十分钟还没头绪就转为“写暴力争取部分分”模式。很多新手容易在一道题上死磕两小时追求“完美解题”的爽感却忘了周赛的目标是在有限时间内拿尽量多的分。部分分也是分哪怕暴力只能过 30% 的数据也远比空提交要好。4.2 取模与快速幂的那些细节降幂和取模是一对容易出错的组合。代码里我习惯先把所有输入都读成 long long再统一转成合适的类型。k % (MOD - 1) 这个操作看着简单但如果 k 是从键盘直接读入到 int一个大数就会变成负数或者乱码整个 e 就废了。另一个容易踩的坑是快速幂内部乘法溢出。MOD 是 998244353两个 long long 相乘大约 10 的 18 次方没有超出 long long 范围但如果你把 MOD 换成更大的质数比如 10 的 18 次方级别的数那就必须考虑用 __int128 或者快速乘来避免溢出。我写模板时会把乘法单独抽出来方便以后换模数。还有一个小细节就是减法取模。计算 cnt 的时候我用的是 pref[v][r] - pref[v][l-1]这两个前缀和都是非负的所以 cnt 不会为负。但如果在更复杂的题目里出现了减法记得一定要写成 (a - b MOD) % MOD不要写成 (a - b) % MOD因为 C 对负数的取模结果不是我们期望的数学含义。4.3 高频报错速查表赛后我整理过一份比赛现场常见的报错速查表很多问题在 Round 135 的讨论区里也能看到对应反馈。整理成表格方便大家直接查阅现象可能原因排查思路测试样例通过了大数据超时复杂度模型不对或者快速幂调用次数过多检查是否使用离线分组是否每个询问都重复计算幂表答案总是偏大或偏小前缀表下标用错或者指数没有降幂手写小数组跑一遍对比 pref[v][r] - pref[v][l] 与 pref[v][r] - pref[v][l-1]直接编译报错数组大小是变量没有用 vector改成 vectorvector 或 new 动态数组结果出现负数减法取模没加 MOD统一使用函数封装减法取模内存溢出二维前缀表开超了把 int 换成 short 或用离线扫描按值域依次处理这张表不能替代自己的调试但它能帮你快速定位到最常见的失败原因。尤其是前缀表下标问题和指数降幂问题我在不少比赛中反复遇到值得养成条件反射式的自查习惯。表格之外我再分享一个独家排错技巧写完代码后先构造一个 n 极小、q 极小的数据比如一个只有 5 个元素的数组然后手推一遍所有答案再用代码输出对照。这一步虽然原始但能过滤掉大约七成的低级错误。千万别依赖“看起来样例过了就交”周赛的平台对正确性格外较真一次 WA 可能就影响你本场排名几十个名次。5. 赛后复盘与后续训练5.1 一场比赛怎么复盘才有效果不少选手打完比赛对完题解就算结束了第二天再问他第四题为什么这么做已经说不出核心思路。我自己的复盘习惯是三步走第一步把四道题全部重新实现一遍不看题解先尝试自己推导第二步把自己的代码和平台上的高分解法对比记录两者在常数优化和代码简洁度上的差距第三步总结出本场用到的所有套路关键词比如“值域压缩”“欧拉降幂”“离线分组”“前缀计数”然后写进自己的套路本里。这套流程看起来费时间但效果非常好。我过去几个月通过这种方式把牛客周赛里常出现的“区间查询 统计”类题目归纳成一个稳定的思维框架。以后再遇到新题我不用每次从零开始建模而是先去匹配已有的套路再针对特殊条件做修改。这样解题速度和准确率都提升得很快。5.2 牛客周赛和 LeetCode 周赛搭配训练我现在每周固定打两场比赛一场牛客周赛一场 LeetCode 周赛。牛客周赛锻炼数据结构和数学能力LeetCode 周赛锻炼对题面的抽象能力和工程思维。两者形成互补对面试和竞赛都有帮助。如果时间有限我建议优先补弱项算法基础不牢固就多刷牛客面试主导就多打 LeetCode但千万不要只打一种。这里还要提一个容易被忽略的点每次比赛结束后的当日我会抽时间读一下排行榜靠前选手的代码。牛客周赛的成绩页允许查看代码里面能看到很多非常精简的写法。你可能会发现同样的思路别人用位运算优化了常数或者用滚动数组压缩了内存。这种“读源码”的过程比看题解更真实因为它展示了现场条件下你也能做到的水平。5.3 一个小技巧区间查询转值域统计最后分享一个我在第四题里印象很深的通用技巧当区间查询里的元素数量很多、但元素可能取值很少时优先考虑值域统计。具体步骤是先开一个“每个值出现多少次”的桶然后用前缀和把桶的累计次数存下来回答查询时枚举值域而不是枚举区间。这个技巧在“区间内每个数平方和”“区间内每个数出现次数众数”“区间内最大出现次数”等题目里同样适用。我常拿它和“字典序”作类比区间查询就像你在人群里找长得像的人如果直接一个个看过去代价随人群规模线性增长但如果你先按身高把所有排队的人分成若干组再来问某一队里有多少人达标那每次查询只需要数几下。这里的“身高分组”就是值域压缩“排队”就是前缀计数。5.4 一点个人体会我在实际训练中发现牛客周赛这类平台的题目质量虽然参差不齐但恰好因为参差不齐反而能更全面地暴露问题。比如 Round 135 的第四题第一次差点让我放弃但搞懂以后再看其他区间统计题脑子里会自动多出一个“值域压缩”的备选方案。这种从痛苦到通透的过程正是打周赛最值得珍惜的部分。每次被一道题折磨过我都会顺手把它记录到一个“错题本”里标注当时的错误思路、正确思路和代码教训。三个月下来这个本子成了我最值钱的资料比任何付费课程都有针对性。如果你也愿意每周稳定打一场周赛并且坚持赛后复盘我相信半年后回看这段经历一定会感谢那个没有放弃的自己。毕竟算法能力的提升不是靠某一天的爆发而是靠一次一次比赛里踩过的坑和想通的点慢慢堆出来的。