Functions — github.com/EndlessCheng/codeforces-go

hub / github.com/EndlessCheng/codeforces-go / functions

Functions8,098 in github.com/EndlessCheng/codeforces-go

⨍ Functions 8,098◇ Types & classes 911

EXTRA: 同余最短路 todo https://oi-wiki.org/graph/mod-shortest-path/ todo 跳楼机 https://www.luogu.com.cn/problem/P3403 k 短路 A* 算法可持久化可并堆优化 https://en.wikiped

copypasta/graph.go:1492

MethodmstPrim

最小生成树 Prim 适用于稠密图 O(n^2)，传入邻接矩阵 dis dis[v][w] == inf 表示没有 v-w 边有些题目需要在连通分量上求 MST，这时就需要用到 root https://oi-wiki.org/graph/mst/#prim 模板题 https://www.luo

copypasta/graph.go:1549

copypasta/geometry.go:1103

MethodmulRow

(i int, k int64)

copypasta/math_matrix.go:164

MethodmulVec

(b vec)

copypasta/geometry.go:195

copypasta/geometry.go:192

MethodmustCut

题目保证 o 和 p 连通时的写法

copypasta/link_cut_tree.go:182

FunctionnearestExit

(g [][]byte, entrance []int)

leetcode/biweekly/56/b/b.go:8

FunctionnearestValidPoint

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/47/a/a.go:4

FunctionnetworkBecomesIdle

* BFS + 统计每个点变为空闲状态的最早秒数题目可以抽象成一张图，我们可以用 BFS 求出 $0$ 号节点到其余节点的最短路长度，在 BFS 的同时求出每个节点变为空闲状态的最早秒数，其最大值就是整个计算机网络变为空闲状态的时间。以其中某一节点 $v$ 为例，$v$ 变为空闲状态的最早秒

leetcode/biweekly/63/c/c.go:19

FunctionnewBST

()

copypasta/bst.go:59

FunctionnewBSTWithArray

a 需要是有序的，这样我们可以把它当成中序遍历来构造 BST

copypasta/bst.go:76

FunctionnewFenwickTree

(n int)

copypasta/fenwick_tree.go:201

FunctionnewInt

(x int64)

copypasta/big.go:10

FunctionnewLeftistTreeNode

(id, val int)

copypasta/leftist_tree.go:19

FunctionnewSegmentTree

(a []int)

copypasta/segment_tree.go:126

FunctionnewTreap

也可以直接设 rd 为 1

copypasta/treap.go:90

copypasta/trie01.go:26

Methodnext

后继（大于 key，且最小的数) 等价于 lowerBound(key+1)

copypasta/bst.go:147

FunctionnextBeautifulNumber

* 一题双解：枚举、打表二分 #### 方法一：枚举对于一个数 $x$，我们可以通过统计 $x$ 每个数位的出现次数，记在一长度为 $10$ 的 $\textit{cnt}$ 数组中，并判断 $x$ 每个数位 $d$ 是否满足 $\textit{cnt}[d] = d$，若所有数位均满足，则

leetcode/weekly/264/b/b.go:50

FunctionnextBeautifulNumber2

(n int)

leetcode/weekly/264/b/b.go:68

FunctionnextPermutation

LC 31

leetcode/main.go:59

FunctionnodesBetweenCriticalPoints

github.com/EndlessCheng/codeforces-go

leetcode/weekly/265/b/b.go:9

Functionnorm32

将 (-mod,mod) 范围内的 a 变成 [0,mod) 范围内原理是负数右移会不断补 1，所以最后二进制都是 1，因此返回值等价于 a+_mod 而对于非负数，右移后二进制全为 0，所以返回结果仍然是 a

copypasta/math_fwt.go:109

Functionnorm64

(a int64)

copypasta/math_fwt.go:113

Methodnormal

a 的单位法线（a 不能是零向量） https://en.wikipedia.org/wiki/Normal_(geometry)

copypasta/geometry.go:218

FunctionnthElement

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6741/a/a.go:48

FunctionnthMagicalNumber

github.com/EndlessCheng/codeforces-go

leetcode/weekly/95/c/c.go:6

FunctionnthUglyNumber

(n int, a int, b int, c int)

leetcode/weekly/155/b/b.go:5

FunctionnumDifferentIntegers

github.com/EndlessCheng/codeforces-go

leetcode/weekly/234/a/a.go:9

FunctionnumDupDigitsAtMostN

github.com/EndlessCheng/codeforces-go

leetcode/weekly/128/d/d.go:6

FunctionnumEnclaves

(g [][]int)

leetcode/weekly/130/d/d.go:3

FunctionnumEquivDominoPairs

(dominoes [][]int)

leetcode/weekly/146/a/a.go:5

FunctionnumIdenticalPairs

(a []int)

leetcode/weekly/197/a/a.go:3

FunctionnumKLenSubstrNoRepeats

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/3/b/b.go:4

FunctionnumOfArrays

(n int, m int, K int)

leetcode/weekly/185/d/d.go:3

FunctionnumOfBurgers

(a int, b int)

leetcode/weekly/165/b/b.go:3

FunctionnumOfMinutes

(n int, headID int, manager []int, informTime []int)

leetcode/weekly/179/c/c.go:3

FunctionnumOfPairs

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/62/b/b.go:4

FunctionnumOfStrings

* 直接模拟就行了，或者 AC 自动机 */ github.com/EndlessCheng/codeforces-go

leetcode/weekly/254/a/a.go:12

FunctionnumOfSubarrays

(a []int)

leetcode/biweekly/31/b/b.go:3

FunctionnumOfSubarrays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/19/b/b.go:4

FunctionnumOfWays

(a []int)

leetcode/weekly/204/d/d.go:47

FunctionnumOfWays

https://oeis.org/A052913 a(n) is also the number of 3 X n matrices of integers for which the upper-left hand corner is a 1, the rows and columns are w

leetcode/weekly/184/d/d.go:7

FunctionnumPairsDivisibleBy60

github.com/EndlessCheng/codeforces-go

leetcode/weekly/128/b/b.go:4

MethodnumPairsWithDistanceLimit

点分治：求树上距离不超过 upperDis 的点对数 todo 待整理 https://www.luogu.com.cn/problem/P4178 http://poj.org/problem?id=1741 todo 求树上距离等于 k 的点对数 https://codeforces.com/p

copypasta/graph_tree.go:518

FunctionnumPoints

(points [][]int, R int)

leetcode/weekly/189/d/d.go:18

FunctionnumPrimeArrangements

github.com/EndlessCheng/codeforces-go

leetcode/weekly/152/a/a.go:6

FunctionnumSmallerByFrequency

(queries []string, words []string)

leetcode/weekly/151/b/b.go:3

FunctionnumSpecial

github.com/EndlessCheng/codeforces-go

leetcode/weekly/206/a/a.go:4

FunctionnumSplits

(s string)

leetcode/biweekly/31/c/c.go:3

FunctionnumSteps

(ss string)

leetcode/weekly/183/b/b.go:3

FunctionnumSub

(s string)

leetcode/weekly/197/b/b.go:3

FunctionnumSubarrayProductLessThanK

github.com/EndlessCheng/codeforces-go

leetcode/weekly/55/c/c.go:4

FunctionnumSubmat

全 1 矩形个数 LC1504/周赛196C https://leetcode-cn.com/problems/count-submatrices-with-all-ones/ 参考 https://leetcode.com/problems/count-submatrices-with-all-o

copypasta/monotone_stack.go:186

FunctionnumSubmat

(mat [][]int)

leetcode/weekly/196/c/c.go:5

FunctionnumSubmatrixSumTarget

github.com/EndlessCheng/codeforces-go

leetcode/weekly/139/d/d.go:4

FunctionnumSubseq

(a []int, target int)

leetcode/weekly/195/c/c.go:15

FunctionnumTeams

(a []int)

leetcode/weekly/182/b/b.go:3

FunctionnumTilePossibilities

(tiles string)

leetcode/weekly/140/b/b.go:3

FunctionnumTimesAllBlue

(light []int)

leetcode/weekly/179/b/b.go:3

FunctionnumTriplets

github.com/EndlessCheng/codeforces-go

leetcode/weekly/205/b/b.go:4

FunctionnumWaterBottles

(n, e int)

leetcode/weekly/198/a/a.go:3

FunctionnumWays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/34/b/b.go:6

FunctionnumWays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/38/d/d.go:4

FunctionnumWays

(n int, relation [][]int, k int)

leetcode/season/2020spring/b/b.go:3

FunctionnumWays

(steps int, arrLen int)

leetcode/weekly/164/d/d.go:3

FunctionnumberOfArrays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/24/d/d.go:4

FunctionnumberOfCombinations

(s string)

leetcode/biweekly/59/d/d.go:22

FunctionnumberOfDays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/4/a/a.go:6

FunctionnumberOfMatches

github.com/EndlessCheng/codeforces-go

leetcode/weekly/219/a/a.go:4

FunctionnumberOfRounds

github.com/EndlessCheng/codeforces-go

leetcode/weekly/246/b/b.go:6

FunctionnumberOfSets

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/37/c/c.go:6

FunctionnumberOfSteps

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/19/a/a.go:6

FunctionnumberOfSubarrays

(nums []int, k int)

leetcode/weekly/161/b/b.go:3

FunctionnumberOfSubstrings

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/20/c/c.go:4

FunctionnumberOfUniqueGoodSubsequences

* 倒序动态规划我们将 $s$ 反转，在反转后的字符串 $s'$ 上，定义 $f[i][0/1]$ 表示前 $i$ 个字符中，以 $\texttt{0}$ 或 $\texttt{1}$ 结尾的不同子序列的个数，这样最后取 $f[n-1][1]$ 就可以避免前导零的影响。转移时，我们可以直接在

leetcode/weekly/256/d/d.go:26

FunctionnumberOfWays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/13/d/d.go:6

FunctionnumberOfWeakCharacters

* 简洁写法将角色按照攻击**从大到小**排序，攻击相同的按照防御**从小到大**排序。然后遍历数组，维护遍历过的角色的防御的最大值 $\textit{maxDef}$。由于攻击已经按照从大到小排序了，对于当前角色 $p$，如果 $p$ 的防御小于 $\textit{maxDef}$，那么说

leetcode/weekly/257/b/b.go:14

FunctionnumberOfWeeks

* 贪心贪心的方案是，每周可以选择一个剩余任务数最多的项目（且与上一周不同）。考虑任务最多的项目 $i$，如果它超过了其余任务数之和，则最佳方案是从第一周开始，奇数周选项目 $i$，偶数周选其余项目。若它没有超过其余任务数之和，则可以做完所有任务。 */ github.com/Endles

leetcode/weekly/252/b/b.go:12

FunctionnumberTheoryCollection

* 数论组合数学一些不等式及其证明 https://www.luogu.com.cn/blog/chinesepikaync/oi-zhong-kuai-yong-dao-di-yi-suo-fou-deng-shi-ji-ji-zheng-ming https://en.wikipedia

copypasta/math.go:133

FunctionnumberWays

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/25/d/d.go:4

FunctionnumericalAnalysisCollection

数值分析 https://en.wikipedia.org/wiki/Numerical_analysis

copypasta/math_numerical_analysis.go:7

FunctionoddCells

(n int, m int, indices [][]int)

leetcode/weekly/162/a/a.go:3

Functionoddnumber

github.com/EndlessCheng/codeforces-go

misc/nowcoder/10323/a/a.go:4

MethodonLine

点 a 是否在直线 l 上判断方法：a-p1 与 a-p2 共线

copypasta/geometry.go:313

MethodonRay

点 a 是否在射线 o-d 上（d 是向量）判断方法：o-a 与 d 共线且方向相同

copypasta/geometry.go:328

MethodonSeg

点 a 是否在线段 l 上判断方法：a-p1 与 a-p2 共线且方向相反

copypasta/geometry.go:320

FunctionorderlyQueue

github.com/EndlessCheng/codeforces-go

leetcode/weekly/100/d/d.go:6

← previous next →7,601–7,700 of 8,098, ranked by callers