科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文以 codeforces-go 仓库中 LeetCode 第 300 场周赛 T3题解文档为骨架完整讲解2327. 知道秘密的人数Number of People Aware of a Secret的两种主流解法差分数组与前缀和。题目模型本质上是「区间上的人口扩散 遗忘」是理解差分/前缀和两大数据结构思想的最佳入门实战题之一。读完本文你将掌握如何用「恰好在第 i 天得知秘密的人数」进行状态定义、如何把「给一段区间统一加值」用差分数组优化到 O(1)、如何把「区间求和」用前缀和优化到 O(1)以及这套解法在本仓库 Go 源码c.go与自动化测试c_test.go中的落地形态。一、理解题意先建立正确的时间模型恰好在第i天得知秘密的人会在[idelay, iforget-1]中的每一天分享秘密每天给一个新的人分享秘密。 新的得知秘密的人会按照同样的规则继续分享秘密。 在第i天得知秘密的人会在第iforget天忘记秘密。 我们计算的是第n天结束时还没有忘记秘密的人数。题目给出三个参数参数含义取值范围本题约束n总共观察的天数1 n 1000delay得知秘密后经过delay天才开始分享1 delay nforget得知秘密后经过forget天忘记1 forget n且delay forget关键结论可从题意直接推出一个在第i天得知秘密的人从第idelay天起每天感染 1 个新人直到第iforget-1天为止他在第iforget天不再计入答案因此第n天结束时仍未忘记的人必须满足i forget - 1 n即i n - forget 1。二、核心状态定义为什么必须是「恰好在第 i 天得知秘密」方法的关键在于维护数组known其中known[i]表示恰好在第 i 天得知秘密的人数。为什么强调「恰好」如果不用「恰好」第i天的集合里会混着各种人——刚知道的、昨天知道的、前天知道的……它们的剩余分享天数各不相同无法统一处理。而用「恰好」切分之后每个群体独立、行为完全一致都在自己的[idelay, iforget-1]区间内每天分享 1 人问题就变成了清晰的递推/区间更新问题。初始值known[1] 1第 1 天有 1 个人得知了秘密。分享规则翻译成代码语言就是恰好在第i天得知秘密的known[i]个人会把known[j]增加known[i]其中j idelay, idelay1, ..., iforget-1。答案计算known中下标[max(n-forget1, 1), n]的元素和就是第n天结束时没有忘记秘密的人数。三、方法一朴素模拟 → 差分数组优化3.1 优化前直接区间加O(n·(forget-delay))最朴素的做法是对于每个i用内层循环把known[idelay .. iforget-1]全部加上known[i]。class Solution: def peopleAwareOfSecret(self, n: int, delay: int, forget: int) - int: MOD 1_000_000_007 # known[i] 表示恰好在第 i 天得知秘密的人数 known [0] * (n 1) known[1] 1 for i in range(1, n 1): known[i] % MOD # 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 for j in range(i delay, min(i forget, n 1)): known[j] known[i] # 统计在第 n 天没有忘记秘密的人数 # 这要求 iforget-1 n解得 i n-forget1 return sum(known[-forget:]) % MODfunc peopleAwareOfSecret(n, delay, forget int) (ans int) { const mod 1_000_000_007 // known[i] 表示恰好在第 i 天得知秘密的人数 known : make([]int, n1) known[1] 1 for i : 1; i n; i { known[i] % mod // 统计在第 n 天没有忘记秘密的人数 // 这要求 iforget-1 n解得 i n-forget1 if i n-forget1 { ans known[i] } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 for j : i delay; j min(iforget-1, n); j { known[j] known[i] } } return ans % mod }复杂度分析时间复杂度 O(n·(forget − delay))空间复杂度 O(n)。注意 Python 版本在统计答案时用known[-forget:]切片与「i n-forget1」是等价的n-forget1对应的正是倒数第forget个元素Go/Java/C/C 版本则显式地用一个if判断i n-forget1在遍历中累加答案。3.2 优化把「区间加」换成差分数组O(n)观察上面代码内层循环做的其实是「把子数组的每个元素都增加known[i]」——这正是差分数组的用武之地。设diff是known的差分数组。对已知数组的区间[l, r]整体加x等价于diff[l] x diff[r1] - x初始值known[1] 1对应diff[1] 1、diff[2] -1第i天得到的真实人数known (known diff[i]) % MOD差分的前缀和还原分享动作变成两次 O(1) 的差分更新diff[idelay] knowndiff[iforget] - knownclass Solution: def peopleAwareOfSecret(self, n: int, delay: int, forget: int) - int: MOD 1_000_000_007 diff [0] * (n 2) diff[1] 1 diff[2] -1 ans known 0 for i in range(1, n 1): # 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % MOD # 统计在第 n 天没有忘记秘密的人数 if i n - forget 1: ans known # 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 diff[min(i delay, n 1)] known diff[min(i forget, n 1)] - known return ans % MODfunc peopleAwareOfSecret(n, delay, forget int) (ans int) { const mod 1_000_000_007 diff : make([]int, n2) diff[1] 1 diff[2] -1 known : 0 for i : 1; i n; i { // 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % mod // 统计在第 n 天没有忘记秘密的人数 if i n-forget1 { ans known } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 diff[min(idelay, n1)] known diff[min(iforget, n1)] - known // 注意这里有减法这会导致上面累加 diff[i] 时known 可能是负数 } return (ans%mod mod) % mod // 保证答案非负 }class Solution { public int peopleAwareOfSecret(int n, int delay, int forget) { final int MOD 1_000_000_007; int[] diff new int[n 1]; diff[1] 1; diff[2] -1; int known 0; long ans 0; for (int i 1; i n; i) { // 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % MOD; // 统计在第 n 天没有忘记秘密的人数 if (i n - forget 1) { ans known; } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 if (i delay n) { diff[i delay] (diff[i delay] known) % MOD; } if (i forget n) { diff[i forget] (diff[i forget] - known MOD) % MOD; // MOD 保证结果非负 } } return (int) (ans % MOD); } }class Solution { public: int peopleAwareOfSecret(int n, int delay, int forget) { const int MOD 1000000007; vectorint diff(n 1); diff[1] 1; diff[2] -1; int known 0; long long ans 0; for (int i 1; i n; i) { // 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % MOD; // 统计在第 n 天没有忘记秘密的人数 if (i n - forget 1) { ans known; } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 if (i delay n) { diff[i delay] (diff[i delay] known) % MOD; } if (i forget n) { diff[i forget] (diff[i forget] - known MOD) % MOD; // MOD 保证结果非负 } } return ans % MOD; } };#define MOD 1000000007 int peopleAwareOfSecret(int n, int delay, int forget) { int* diff calloc(n 1, sizeof(int)); diff[1] 1; diff[2] -1; int known 0; long long ans 0; for (int i 1; i n; i) { // 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % MOD; // 统计在第 n 天没有忘记秘密的人数 if (i n - forget 1) { ans (ans known) % MOD; } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 if (i delay n) { diff[i delay] (diff[i delay] known) % MOD; } if (i forget n) { diff[i forget] (diff[i forget] - known MOD) % MOD; // MOD 保证结果非负 } } free(diff); return ans % MOD; }var peopleAwareOfSecret function(n, delay, forget) { const MOD 1_000_000_007; const diff Array(n 2).fill(0); diff[1] 1; diff[2] -1; let known 0; let ans 0; for (let i 1; i n; i) { // 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % MOD; // 统计在第 n 天没有忘记秘密的人数 if (i n - forget 1) { ans known; } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 diff[Math.min(i delay, n 1)] known; diff[Math.min(i forget, n 1)] - known; // 注意这里有减法这会导致上面累加 diff[i] 时known 可能是负数 } return (ans % MOD MOD) % MOD; // 保证答案非负 };impl Solution { pub fn people_aware_of_secret(n: i32, delay: i32, forget: i32) - i32 { const MOD: i32 1_000_000_007; let n n as usize; let delay delay as usize; let forget forget as usize; let mut diff vec![0; n 1]; diff[1] 1; diff[2] -1; let mut known 0; let mut ans 0; for i in 1..n { // 加上 diff[i] 后known 表示恰好在第 i 天得知秘密的人数 known (known diff[i]) % MOD; // 统计在第 n 天没有忘记秘密的人数 if i n - forget 1 { ans (ans known) % MOD; } // 恰好在第 i 天得知秘密的人会在第 [idelay, iforget-1] 天分享秘密 if i delay n { diff[i delay] (diff[i delay] known) % MOD; } if i forget n { diff[i forget] (diff[i forget] - known MOD) % MOD; // MOD 保证结果非负 } } ans } }复杂度分析时间复杂度 O(n)空间复杂度 O(n)。两个实现细节值得注意负数的处理diff[iforget] - known之后known在累加过程中可能变成负数。Go / JS / Rust 版本用(ans % mod mod) % mod在最后统一保证答案非负Java / C / C 版本则是在每次做减法更新时直接- known MOD再取模保证diff中不出现负数。取模的合法性最终答案需要对MOD 1_000_000_007取模。由于「在模 MOD 意义下先取模再相加/相减等价于真实数值运算后再取模」模运算对加法和减法保持分配律因此可以在中途随时取模而不会改变最终结果。这正是差分数组写法里可以放心% MOD的根本原因。四、方法二前缀和换一个视角看问题差分数组是从「源头」看第i天的known[i]会影响到后面哪些天。前缀和则是「横看成岭侧成峰」从目的地看known[j]会被哪些known[i]更新由分享区间的不等式i delay j i forget - 1解得j - forget 1 i j - delay也就是说known[j]恰好等于known在区间[j-forget1, j-delay]上的子数组和。而子数组和正是前缀和的强项。设sum为known的前缀和数组则每个j只需要一次 O(1) 的区间查询known[j] sum[j-delay] - sum[j-forget] 注意下标越界时取 0 sum[j] sum[j-1] known[j]class Solution: def peopleAwareOfSecret(self, n: int, delay: int, forget: int) - int: MOD 1_000_000_007 s [0] * (n 1) # known 数组的前缀和 s[1] 1 for j in range(2, n 1): known s[max(j - delay, 0)] - s[max(j - forget, 0)] s[j] (s[j - 1] known) % MOD return (s[n] - s[max(n - forget, 0)]) % MODfunc peopleAwareOfSecret(n, delay, forget int) int { const mod 1_000_000_007 sum : make([]int, n1) // known 数组的前缀和 sum[1] 1 for j : 2; j n; j { known : sum[max(j-delay, 0)] - sum[max(j-forget, 0)] sum[j] (sum[j-1] known) % mod } ans : sum[n] - sum[max(n-forget, 0)] return (ans%mod mod) % mod // 保证答案非负 }class Solution { public int peopleAwareOfSecret(int n, int delay, int forget) { final int MOD 1_000_000_007; int[] sum new int[n 1]; // known 数组的前缀和 sum[1] 1; for (int j 2; j n; j) { int known (sum[Math.max(j - delay, 0)] - sum[Math.max(j - forget, 0)]) % MOD; sum[j] (sum[j - 1] known) % MOD; } int ans sum[n] - sum[Math.max(n - forget, 0)]; return (ans % MOD MOD) % MOD; // 保证答案非负 } }class Solution { public: int peopleAwareOfSecret(int n, int delay, int forget) { const int MOD 1000000007; vectorint sum(n 1); // known 数组的前缀和 sum[1] 1; for (int j 2; j n; j) { int known (sum[max(j - delay, 0)] - sum[max(j - forget, 0)]) % MOD; sum[j] (sum[j - 1] known) % MOD; } int ans sum[n] - sum[max(n - forget, 0)]; return (ans % MOD MOD) % MOD; // 保证答案非负 } };#define MOD 1000000007 #define MAX(a, b) ((b) (a) ? (b) : (a)) int peopleAwareOfSecret(int n, int delay, int forget) { int* sum malloc((n 1) * sizeof(int)); // known 数组的前缀和 sum[0] 0; sum[1] 1; for (int j 2; j n; j) { int known (sum[MAX(j - delay, 0)] - sum[MAX(j - forget, 0)]) % MOD; sum[j] (sum[j - 1] known) % MOD; } int ans sum[n] - sum[MAX(n - forget, 0)]; free(sum); return (ans % MOD MOD) % MOD; // 保证答案非负 }var peopleAwareOfSecret function(n, delay, forget) { const MOD 1_000_000_007; const sum Array(n 1).fill(0); // known 数组的前缀和 sum[1] 1; for (let j 2; j n; j) { const known sum[Math.max(j - delay, 0)] - sum[Math.max(j - forget, 0)]; sum[j] (sum[j - 1] known) % MOD; } const ans sum[n] - sum[Math.max(n - forget, 0)]; return (ans % MOD MOD) % MOD; // 保证答案非负 };impl Solution { pub fn people_aware_of_secret(n: i32, delay: i32, forget: i32) - i32 { const MOD: i32 1_000_000_007; let n n as usize; let delay delay as usize; let forget forget as usize; let mut sum vec![0; n 1]; // known 数组的前缀和 sum[1] 1; for j in 2..n { let known (sum[j.saturating_sub(delay)] - sum[j.saturating_sub(forget)]) % MOD; sum[j] (sum[j - 1] known) % MOD; } let ans sum[n] - sum[n.saturating_sub(forget)]; (ans % MOD MOD) % MOD // 保证答案非负 } }复杂度分析时间复杂度 O(n)空间复杂度 O(n)。注意 Rust 版本用saturating_sub饱和减法下溢时返回 0来天然处理下标越界代替了其他语言里max(..., 0)的写法。五、三种写法对比写法核心操作时间复杂度空间复杂度思路视角朴素模拟区间加known[l..r] known[i]O(n·(forget−delay))O(n)源头驱动逐天暴力差分数组区间加拆分diff[l] x; diff[r1] - xO(n)O(n)源头驱动O(1) 区间加前缀和区间查询sum[r] - sum[l-1]O(n)O(n)目的地驱动O(1) 区间求和三者共享同一个状态定义known[i]恰好在第 i 天得知秘密的人数区别只在于「区间更新」与「区间查询」的实现方式差分数组擅长把区间加变成 O(1) 的两点更新前缀和擅长把区间和变成 O(1) 的两点相减。本题同时用到「分享区间加法」和「答案区间求和」两种操作因此两种数据结构都能独立求解——这正是本题作为差分/前缀和入门题的经典之处。六、仓库源码验证实现与自动化测试6.1 Go 实现源码本仓库在 c.go 中同时实现了前缀和与差分数组两个版本peopleAwareOfSecret前缀和版本维护sum前缀和数组known : sum[max(j-delay,0)] - sum[max(j-forget,0)]直接 O(1) 算出第j天新增人数peopleAwareOfSecret1差分数组版本维护diff差分数组每次分享只做diff[min(idelay, n1)] known与diff[min(iforget, n1)] - known两次 O(1) 更新。两个版本的行末都写着// 保证答案非负对应解法中(ans%mod mod) % mod的负数处理技巧。6.2 自动化测试文件驱动用例仓库用 c_test.go 对实现做回归验证func Test_c(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, peopleAwareOfSecret, c.txt, targetCaseNum); err ! nil { t.Fatal(err) } }测试用例存放在同目录的 c.txt 中每fNumIn fNumOut行为一组本题入参n, delay, forget共 3 行 输出 1 行用例 1n6, delay2, forget4→ 输出5用例 2n4, delay1, forget3→ 输出6。驱动函数RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go先用os.ReadFile读取用例文件去掉空白行后通过reflect.TypeOf(f).NumIn()/NumOut()反射出函数的参数个数自动把文件内容按「输入行数 输出行数」切分成多组样例再交给RunLeetCodeFuncWithExamples逐个断言输出。这套「题解文档 Go 实现 txt 用例 反射驱动的测试工具」的配套结构让每一道 LeetCode 周赛题的解法都可以直接在仓库内本地复现和验证是学习算法题时「先看文档思路、再读源码实现、最后跑测试确认」的完整闭环。七、举一反三专题训练方向本题属于「时间轴上区间扩散」类模型学会后可继续深入以下专题对应仓库 common.go 中收录的分类题单数据结构题单前缀和一维、二维、多维与一维差分数组——本题是两者的最小完整闭环动态规划题单前缀和优化 DP——当 DP 转移中出现「对一段下标求和」时可套用方法二的「目的地视角」把转移复杂度从 O(n) 压到 O(1)滑动窗口与双指针与本题的「定长/不定长窗口内计数」有共通思想更进阶的方向包括网格图二维差分/二维前缀和、树形结构上的差分树上差分这些在仓库 fenwick_tree.go差分数组 树状数组实现 O(log n) 区间加区间查和 graph_tree.go树上差分中都有对应模板。建议的练习路径先独立写出朴素模拟版本确认题意再分别用差分数组与前缀和两个版本提交最后对照本仓库 c.go 与 2327.md 的代码逐行核对下标边界尤其是min(..., n1)与max(..., 0)这两处防越界细节。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解精讲LeetCode 2270「分割数组的方案数」的前缀和单次遍历解法codeforces go 题解精讲LeetCode 2270「分割数组的方案数」的前缀和单次遍历解法 本文围绕算法竞赛模板库 codeforces go 中科学计算codeforces-go 题解精讲LeetCode 2416「字符串的前缀分数和」的字典树解法Python/Java/C/Gocodeforces go 题解精讲LeetCode 2416「字符串的前缀分数和」的字典树解法Python/Java/C/Go 本文基于 leetc科学计算LogicStack-LeetCode 题解精讲LeetCode 677 键值映射——Trie 前缀树与 DFS 前缀求和两种解法LogicStack LeetCode 题解精讲LeetCode 677 键值映射——Trie 前缀树与 DFS 前缀求和两种解法 导读 本文是「LogicS教程文档上一篇如何用foundry-template做以太坊主网Fork测试一个用例验证USDC余额下一篇reverse-interview机器学习集成智能问题推荐系统原型设计创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考