お前はどこまで見えている

1. 简介 算法的时间复杂度是指在问题规模为 NNN 时整个算法执行的基本语句单元次数，记为 T(N)T(N)T(N) 。 2. 分类 在算法时间复杂度分析中，常用 log⁡−log⁡ plot\log-\log \ plotlog−log plot 图去衡量算法时间复杂度，该图横坐标为 log⁡N\log NlogN（NNN 为问题规模），纵坐标为 log⁡T\log TlogT（TTT 为时间频度）。 exponential：指数复杂度 cubic：N3N^3N3 quadratic：N2N^2N2 linearithmic：Nlog⁡NN\log NNlogN linear：NNN logarithmic：log⁡N\log NlogN constant：CCC 3. 符号 以 Nlog⁡NN\log NNlogN 为例： Θ(Nlog⁡N)\Theta(N \log N)Θ(NlogN)：表示时间复杂度渐近为 Nlog⁡NN \log NNlogN 。 O(Nlog⁡N)O(N \log N)O(NlogN)：表示时间复杂度小于等于 Nlog⁡NN \log NN ...

【注】参考自教材「算法导论」。 1. 简介 快速排序是一种被广泛运用的排序算法，虽然其最坏情况下的时间复杂度为 O(n2)O(n^2)O(n2)，但其平均时间复杂度为 (nlog⁡2n)(n\log_2 n)(nlog2​n)，而且其常数因子非常小，所以实际情况下跑的很快。快速排序是不稳定的、原址的排序算法。 【注】实际上只要保证快排的每一层枢轴左右两边的序列大小的划分比不超过某一常数比（即与序列大小 nnn 无关），那么最终快排的时间复杂度就为 O(nlog⁡2n)O(n \log_2 n)O(nlog2​n) 。 2. 思想 以从小到大排序的快速排序为例，快速排序主要思想是： 首先在序列中选定一个元素作为枢轴 然后将序列中所有小于枢轴的元素都交换到枢轴左侧，所有大于枢轴的元素都交换到枢轴右侧 接着递归处理枢轴左侧的序列和右侧的序列 其中最重要的就是实现将小于枢轴的元素交换到枢轴左侧，将大于枢轴的元素交换到枢轴右侧。 2.1 基础快排 维护两个指针，分别从序列首部和尾部往相反方向扫过去 第一个指针停在扫到的第一个大于枢轴的元素位置，然后交换两个指针指向的元素；第二个指针停在扫到 ...

XXX 表示随机变量/向量，其余小写黑体表示向量，大写黑体表示矩阵。 1. 离散分布 记 q=1−pq = 1 - pq=1−p。 概率分布 记法 累积分布函数 均值 方差 0-1 分布（伯努利分布） X∼B(1,p)X \sim B(1, p)X∼B(1,p) P(X=1)=pP(X=0)=qP(X = 1) = p \\P(X = 0) = qP(X=1)=pP(X=0)=q ppp pqpqpq 二项分布（nnn 重伯努利分布） X∼B(n,p)X \sim B(n, p)X∼B(n,p) P(X=k)=Cnkpkqn−kP(X = k) = C_n^k p^k q^{n-k}P(X=k)=Cnk​pkqn−k npnpnp npqnpqnpq 多项式分布 X∼PN(p1,⋯ ,pn)X \sim PN(p_1, \cdots, p_n)X∼PN(p1​,⋯,pn​) P(X=x)=n!x1!⋯xk!p1x1⋯pkxk,∑i=1kxi=nx=[x1,⋯ ,xk]⊤,xi∈{0,⋯ ,n},∑i=1kpi=1P(X = \boldsymbol{x}) = ...

1. 定义 监督学习方法可以为生成方法和判别方法，所学到的模型分别称为生成模型和判别模型。 生成方法由数据学习联合概率分布 P(X,Y)P(X, Y)P(X,Y)，然后求出条件概率分布 P(Y∣X)P(Y | X)P(Y∣X) 作为预测的模型，即生成模型： P(Y∣X)=P(X,Y)P(X)P(Y | X) = \frac{P(X, Y)}{P(X)} P(Y∣X)=P(X)P(X,Y)​ 生成模型表示了给定输入 XXX 产生输出 YYY 的生成关系。典型的生成模型有朴素贝叶斯法和隐马尔可夫模型。 判别方法由数据直接学习决策函数 f(X)f(X)f(X) 或者条件概率分布 P(Y∣X)P(Y | X)P(Y∣X) 作为预测的模型，即判别模型。判别方法关心的是对给定的输入 XXX，应该预测什么样的输出 YYY。典型的判别模型有：kkk 近邻法、感知机、决策树、逻辑斯谛回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。 监督学习的应用主要在三个方面：分类问题、标注问题和回归问题。 2. 分类问题 分类问题主要包括学习和分类两个过程： 在学习过程中，根据已知的训练数据集 ...

1. 定义 假设用 PPP 来评估计算机程序在某任务类 TTT 上的性能，若一个程序通过利用经验 EEE 在 TTT 中的任务上获得了性能改善，我们就说关于 TTT 和 PPP，该程序对 EEE 进行了学习。 2. 分类 机械学习 示教学习 类比学习 归纳学习（主流技术，涵盖监督学习、无监督学习等，相当于「从样例中学习」） 3. 归纳学习 3.1 符号主义 决策树：经典的决策树学习以信息论为基础，以信息熵的最小化为目标，直接模拟了人类对概念进行判定的树形流程。 基于逻辑的学习：ILP（Inductive Logic Programming）使用一阶逻辑（谓词逻辑）来进行知识表示，通过修改和扩充逻辑表达式来完成对数据的归纳。 3.2 统计学习 支持向量机（SVM） 核方法 3.3 连接主义 深度学习 4. 基本术语 一般地，令 D={x1,x2,⋯ ,xm} D = \{\boldsymbol{x_1,x_2,\cdots,x_m}\} D={x1​,x2​,⋯,xm​} 表示包含 mmm 个示例的数据集，每个示例由 ddd 个属性描述，则每个示例 xi= ...

1. 题目 题目链接：UVA437「The Tower of Babylon」 。 Description Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story: The babylonians had nnn types of blocks, and an unlimited supply of blocks of each type. Each type-iii block was a rectangular solid with linear dimensions (xix_ixi​, yiy_iyi​, ziz_izi​). A block could be reoriented so that any two o ...

1. 题目 题目链接：CF1407D「Discrete Centrifugal Jumps」 。 Description There are nnn beautiful skyscrapers in New York, the height of the iii-th one is hih_ihi​. Today some villains have set on fire first n−1n-1n−1 of them, and now the only safety building is nnn-th skyscraper. Let’s call a jump from iii-th skyscraper to jjj-th (i<ji < ji<j) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if i<ji < ji<j and one of the follo ...

1. 题目 题目链接：CF991F「Tree Destruction」 。 Description You are given an unweighted tree with nnn vertices. Then n−1n - 1n−1 following operations are applied to the tree. A single operation consists of the following steps: choose two leaves; add the length of the simple path between them to the answer; remove one of the chosen leaves from the tree. Initial answer (before applying operations) is 000. Obviously after n−1n - 1n−1 such operations the tree will consist of a single vertex. Calculate the m ...

1. 题目 题目链接：CF1405D「Tree Tag」 。 DESCRIPTION Alice and Bob are playing a fun game of tree tag. The game is played on a tree of nnn vertices numbered from 111 to nnn. Recall that a tree on nnn vertices is an undirected, connected graph with n−1n-1n−1 edges. Initially, Alice is located at vertex aaa, and Bob at vertex bbb. They take turns alternately, and Alice makes the first move. In a move, Alice can jump to a vertex with distance at most dadada from the current vertex. And in a move, Bob can jum ...

LCM（最小公倍数）和 GCD（最大公因数）在做 ACM 题时经常会用到，求两个整数的 LCM 和 GCD 有两种方法。 1. 辗转相除法（欧几里得算法） 定理：对于任意的两个整数 a,b(a≥b)a,b (a \geq b)a,b(a≥b)， 有 (a,b)=(b,a%b)(a,b) = (b, a\%b)(a,b)=(b,a%b) 。（(a,b)(a, b)(a,b) 表示 aaa 和 bbb 的最大公因数） 证明如下：    a=qb+ra = qb + ra=qb+r，其中 qqq 为整数，0≤a<b0 \leq a \lt b0≤a<b 。    设 d=(a,b)d = (a, b)d=(a,b)，则 b=mdb = mdb=md，a=nda = nda=nd 。    则 a=qmd+r=nda = qmd + r = nda=qmd+r=nd，进一步推出 r=(n−qm)dr = (n-qm)dr=(n−qm)d 。    故 ddd 也是 rrr 的因数，即 d≤(b,r)=(b,a%b)d \leq (b, r) = (b, a\%b)d≤(b ...

1. 简介 树中所有简单路径的最大值即为树的直径，可以通过两次 DFS 或者树形 DP 在 O(n)O(n)O(n) 时间内求解。 2. 思路 2.1 两次 DFS 首先将任意一个结点 uuu 看作是树根，然后进行 DFS 求出最远的结点 sss；则 sss 一定是树的直径的其中一个端点。 证明   假设结点 s′s's′ 和 t′t't′ 之间唯一的简单路径为树的直径，(a,b)(a,b)(a,b) 表示结点 aaa 和 bbb 之间的唯一的简单路径的长度。若该最远点 sss 不是树的直径的一个端点，则对于当前根结点 uuu 来说： 如果 s′s's′ 或 t′t't′ 二者有一个不与 sss 在同一个子树（假设为 t′t't′），则由于 (s′,t′)≤(s′,u)+(u,t′)≤(s,u)+(u,t′)=(s,t′)\begin{array}{c} (s',t') \leq (s',u)+(u,t') \leq (s,u)+(u,t') = (s,t') ...

1. 题目 题目链接：P2014「[CTSC1997]选课」 。 题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 NNN 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 aaa 是课程 bbb 的先修课即只有学完了课程 aaa，才能学习课程 bbb）。一个学生要从这些课程里选择 MMM 门课程学习，问他能获得的最大学分是多少？ 输入格式 第一行有两个整数 NNN，MMM 用空格隔开。（1≤N≤3001 \leq N \leq 3001≤N≤300，1≤M≤3001 \leq M \leq 3001≤M≤300） 接下来的 NNN 行,第 I+1I+1I+1 行包含两个整数 kik_iki​ 和 sis_isi​，kik_iki​ 表示第 III 门课的直接先修课，sis_isi​ 表示第 III 门课的学分。若 ki=0k_i=0ki​=0 表示没有直接先修课（1≤ki≤N1 \leq {k_i} \leq N1≤ki​≤N，1≤si≤201 \leq { ...