共有 261 篇文章
线段树
2019-05-28 - 2024-09-15

线段树(segment tree),顾名思义, 是用来存放给定区间(segment, or interval)内对应信息的一种数据结构。与树状数组(binary indexed tree)相似,线段树也用来处理数组相应的区间查询(range query)和元素更新(update)操作。与树状数组不同的是,线段树不止可以适用于区间求和的查询,也可以进行区间最大值,区间最小值(Range Minimum/Maximum Query problem)或者区间异或值的查询。

对应于树状数组,线段树进行更新(update)的操作为O(logn),进行区间查询(range query)的操作也为O(logn)。

Linux/Unix 环境下实现精确计算程序运行的时间
2019-05-27 - 2024-09-18
C++
写程序时,程序的运行效率很重要,其往往是评价程序优劣性的直接标准。程序运行效率的最简单方法就是计算程序的运行时间。为了提高程序效率,使用适当的方法对程序的各个部分进行运行时间的计算是很有必要的。
最大子列和问题
2019-05-27 - 2024-09-15

求取数组中最大连续子序列和,例如给定数组为A={1, 3, -2, 4, -5}, 则最大连续子序列和为

    $math_inline$6$math_inline$

,即

    $math_inline$1+3+(-2)+4=6$math_inline$

方法一共有三种,复杂度分别为

    $math_inline$O(N^2)$math_inline$

    $math_inline$O(NlgN)$math_inline$

    $math_inline$O(N)$math_inline$

PyCharm不识别turtle下的方法
2019-05-27 - 2024-09-18
PyCharm和turtle库有冲突,不能自己识别出turtle下的方法
分解质因数
2019-05-26 - 2024-09-15

每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。

把一个合数用质因数相乘的形式表示出来,叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。

质数: 质数(prime number)又称素数,有无限个。

质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

合数: 合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数。最小的合数是4。其中,完全数与相亲数是以它为基础的。

约数定理(约数个数定理,约束和定理)
2019-05-26 - 2024-09-15
约数个数定理可以计算出一个数约数的个数
高精度(Arbitrary-precision arithmetic)
2019-05-23 - 2024-09-15
在运算过程中如果运算结果很大,普通的数据类型无法储存,就需要用到所谓的高精度算法,即用数组来存储整数,并模拟手算的方式进行四则运算。
.ssh目录说明及密钥
2019-05-16 - 2024-09-18
SSH
SSH是Secure Shell的缩写,.ssh目录在用户根目录下
ACM卡常数(各种玄学优化)
2019-05-08 - 2024-09-18

首先声明,本博文部分内容仅仅适用于ACM竞赛,并不适用于NOIP与OI竞赛,违规使用可能会遭竞赛处理,请慎重使用!遭遇任何情况都与本人无关哈=7=

我也不想搞得那么严肃的,但真的有些函数在NOIP与OI竞赛中有相关规定不能使用,详细我也不知道各位要了解请自行去找比赛要求咯,当然在ACM竞赛中,没有限制函数,所以所有内容都适用于ACM竞赛。

那么什么是卡常数呢,简单来说就是你和某神犇算法思路一样,结果他的AC了,你的TLE,复杂来说就是程序被卡常数,一般指程序虽然渐进复杂度可以接受,但是由于实现/算法本身的时间常数因子较大,使得无法在OI/ACM等算法竞赛规定的时限内运行结束。

下面就是介绍各种各样的非(花)常(里)实(胡)用(哨)的优化方法的,若本文某些地方有错误或不明确的地方还请指出。=7=

KMP 算法
2019-04-30 - 2024-09-15
Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。
安装Scrcpy
2019-04-28 - 2024-09-18
Mac
Scrcpy是一个能够实时显示并控制Android手机的工具