分类:算法

22 篇文章

字符串Hash – 模板备份
O(1) 取子串Hash O(1) 比较 通常使用 131 做乘法自然溢出即可满足要求(碰撞概率很小),如果数据不允许,可以使用两组 hash 避免哈希碰撞。也可以使用 64 位整数。   [crayon-5fbc56c18f7a5973717124/]  
TSOJ 1057 合法浮点数判断 – 字符串匹配 DFA(maybe)
题目描述 请你判断,哪些是合法的浮点数 浮点数的表示通常有以下两种形式: 1) 十进制小数形式。由数字和小数点组成,必须有小数点,允许出现若干个前导零。例如(123.)(123.0)(.123)(00123.456)。 2) 指数形式。字母 e(或 E)之前必须有数字,允许出现若干个前导零,e 后面的指数必须为整数。例如(123e3)(00123e…
TSOJ 1509 – 十进制快速幂
[latexpage] DESCRIPTION 对于\[a^n \pmod p\] 当$p$为素数,可以使用费马小定理降幂: \[a^n \equiv a^{n \mod {p-1}} \pmod p\] 当$p$为合数,可以使用十进制快速幂解决。 [crayon-5fbc56c190036625366231/] SUMMARY 留一个坑,期末考完…
Luogu 1288 – 博弈论
PROBLEM https://www.luogu.org/problemnew/show/P1288 ANALYSIS 因为一定有一个零权边,所以可以将环拉成链。 不考虑零权边,当链长度为 1 时,先手必胜;相应,为 2 时先手必败。 易证,若设起始点往左和往右走到零权边的距离为分别为x, y,则若x,y中有一个奇数,先手必胜。 这题的数据是真t…
Luogu P1199 – 贪心/博弈论
PROBLEM https://www.luogu.org/problemnew/show/P1199 ANALYSIS 题意就不描述了。 此题中,人是必胜的,只需要做到 每次取所有行中第二大元素最大的那个行。 证明: 计算机和人都永远都拿不到第一大的元素。 计算机永远都拿不到第二大的元素,但是人可以。 SOLUTION [crayon-5fbc5…
Luogu P1983 – 拓扑排序
PROBLEM https://www.luogu.org/problemnew/show/P1983 ANALYSIS STL真的降智 做题之前被周围的人乱说一通更降智 题目大意: 构建低优先级车站指向高优先级车站的单向边,找关键路径。 跑一边拓扑排序就可以了。 使用set的时间约为不使用set时间的13-14倍,空间为5.5倍。也可能是我用的方…