杜教筛与莫比乌斯反演 此篇文章是笔者参考 OI-wiki 写的一份简单的学习笔记。 杜教筛 简介 杜教筛,是一种用于快速求形如 \(\sum_{i = 1} ^ n f(i)\) 这样前缀和形式的算法,最高效时可以达到 \(O(n ^ {\frac{2}{3}})\) 的时间复杂度。 算法思想 对于 \(S(n) = \sum_{i = 1} ^ n f(i)\) 想办法构造一个 \(S(n)\) 关于 \(S([\ 2023-08-30 数据结构与算法 #数论 #杜教筛 #莫比乌斯反演
暑假集训 杭电多校 Round 6 比赛链接 补题链接 「1004」 Count 签到题,\(n \not= k\) 时答案为 \(m ^ {n - k}\) ,\(n = k\) 时答案为 \(m ^ n\)。 时间复杂度:\(O(logn)\) 空间复杂度:\(O(1)\) 1234567891011121314151617181920212223242526#include <iostream>const i 2023-08-03 ACM #杭电多校
暑假集训 杭电多校 Round 5 题目链接 补题链接 「1001」 Typhoon 签到题,遍历每条线段到每个点的最小距离即可。 时间复杂度:\(O(mn)\) 空间复杂度:\(O(m)\) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include &l 2023-08-01 ACM #杭电多校
暑假集训 Nowcoder 多校 Round 4 比赛链接 F 「Election of the King」 签到题,每次淘汰的候选人要么是最左的,要么是最右的,因此用两个变量维护两端的索引,逐步向中间移动。 每一轮选举使用二分查找来得到两人的票数,将得票高的一方淘汰即可。 时间复杂度:\(O(nlogn)\) 空间复杂度:\(O(n)\) 每一轮循环也可以只看中间的人来判断谁被淘汰,可以将时间复杂度优化到 \(O(n)\) 1234567 2023-07-28 ACM #Nowcoder
暑假集训 杭电多校 Round 4 补题链接 「1007」 Guess 结论题,证明得当 \(n\) 为素数的幂即 \(n = p ^ c\) 时 \(S(n) = ln\ \!p\) ,否则 \(S(n) = 0\) 。 然后使用 Pollard-Rho 算法进行质因数分解即可。 时间复杂度:\(O(n ^ {\frac{1}{4}})\) 空间复杂度:\(O(1)\) 123456789101112131415161718 2023-07-28 ACM #杭电多校
暑假集训 Nowcoder 多校 Round 2 比赛链接 E 「Square」 枚举 \(k\) ,然后二分查找即可。 时间复杂度:\(O(logn)\) 空间复杂度:\(O(1)\) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>using i64 = long 2023-07-24 ACM #Nowcoder #Manacher
最优终止策略 —— 为什么是 37%? 见好就收。 描述 考虑一个问题:假设现在有若干件同类型商品,每件商品的质量都不一样且商品质量等可能分布,我们在看到商品前不知道商品的质量,且在看商品时无法回退到上一个商品,接下来要从这些商品中挑选一件商品。现在考虑如下策略: 如果有 \(n\) 件商品,我们先依次看前 \(k\ (k \leq n)\) 件商品,不论商品质量如何,都将其舍弃,在随后的 \(n - k\) 件商品中如果出现了质量比 2023-07-21 数学 #概率论 #37% 法则
暑假集训 杭电多校 Round 2 比赛链接 补题链接 「1009」 String Problem 签到题,求出连续段字符的数量,字符串长度减去该数量就是答案。 时间复杂度:\(O(n)\) 空间复杂度:\(O(n)\) 123456789101112131415161718192021222324#include <iostream>void solve() { std::string str; 2023-07-20 ACM #杭电多校 #bitset
暑假集训 杭电多校 Round 1 暑假集训第一次杭电多校。 题目链接 I 「Assertion」 签到题,知道抽屉原理就行了。 时间复杂度:\(O(1)\) 空间复杂度:\(O(1)\) 123456789101112131415161718192021222324#include <iostream>void solve() { int n, m, d; std::cin >> 2023-07-18 ACM #杭电多校
暑假集训 Nowcoder 多校 Round 1 第一次参加暑假集训的牛客多校,感觉还是挺难的。 比赛链接 D 「Chocolate」 签到题,只有 1 × 1 的时候 Walk Alone 会赢,其余情况均是 Kelin 赢。 时间复杂度:\(O(1)\) 空间复杂度:\(O(1)\) 12345678910111213141516171819#include <iostream>void solve() { 2023-07-17 ACM #Nowcoder