Qianmo's Blog

导论的第一章和第二章为基础内容，我的《算法导论》的学习将从算法的复杂性理论分析开始。 渐进记号 本节介绍了一些常见的渐进记号，并介绍了它们的使用方法。 Θ\ThetaΘ 记号 对于一个给定的函数 g(n)g(n)g(n)，用 Θ(g(n))\Theta(g(n))Θ(g(n)) 来表示以下函数的集合： Θ(g(n))={f(n)∣∃c1,c2>0,n0,s.t.∀n≥n0,0≤c1g(n)≤f(n)≤c2g(n)}\Theta(g(n)) = \left \{f(n)\mid \exist c_1,c_2>0,n_0,s.t.\forall n\ge n_0,0\le c_1g(n)\le f(n)\le c_2g(n)\right \} Θ(g(n))={f(n)∣∃c1​,c2​>0,n0​,s.t.∀n≥n0​,0≤c1​g(n)≤f(n)≤c2​g(n)} 尽管 Θ(g(n))\Theta(g(n))Θ(g(n)) 是一个集合，我们也可以使用 f(n)=Θ(g(n))f(n) = \Theta(g(n))f(n)=Θ(g(n)) 来表示一个满足条件的...

公平组合游戏（ICG） 在算法竞赛中，遇到的最多的就是公平组合游戏（ICG），一个公平组合游戏应该满足如下的性质： 有两名玩家 两名玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面 一个局面的合法操作，只取决于游戏局面本身且固定存在，与玩家次序或者任何其它因素无关 无法操作者，即操作集合为空，输掉游戏，另一方获胜 ICG具有先手必胜状态和先手必败状态，具体地说： 先手必胜状态：可以走到某一个必败状态（走完之后，对于后手就是必败的） 先手必败状态：走不到任何一个必败状态（不管怎么走，后手都是必胜的） Nim游戏 给定 nnn 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。 这个问题的结论是熟知的：假设第 iii 堆石子有 aia_iai​ 个，则先手必胜当且仅当： a1⊕a2⊕⋯⊕an≠0a_1\oplus a_2\oplus\cdots\oplus a_n \ne...

莫比乌斯函数 定义 莫比乌斯函数是一个数论函数，定义如下： μ(n)={1,n=1(−1)k,n是k个不同质数的乘积0,n含有平方因子\mu(n)= \begin{cases} 1,\quad n=1 \\ (-1)^k,\quad \text{$n$是$k$个不同质数的乘积}\\ 0,\quad \text{$n$含有平方因子} \end{cases} μ(n)=⎩⎪⎪⎨⎪⎪⎧​1,n=1(−1)k,n是k个不同质数的乘积0,n含有平方因子​ 例如： μ(1)=1,μ(2)=−1,μ(6)=1,μ(12)=0\mu(1)=1,\mu(2)=-1,\mu(6)=1,\mu(12)=0 μ(1)=1,μ(2)=−1,μ(6)=1,μ(12)=0 性质 莫比乌斯函数是积性函数，也就是： (m,n)=1⇒μ(mn)=μ(m)μ(n)(m,n)=1\Rightarrow...

数论分块 数论分块可以快速计算一些形如 ∑i=1nf(i)g(⌊ni⌋)\sum_{i=1}^nf(i)g(\left \lfloor \frac{n}{i} \right \rfloor ) i=1∑n​f(i)g(⌊in​⌋) 的和式。如果可以在 O(1)O(1)O(1) 时间内计算出 ∑i=lrf(i)\sum_{i=l}^{r}f(i)∑i=lr​f(i) 或者已经预处理出 fff 的前缀和时，就可以用数论分块在 O(n)O(\sqrt{n})O(n​) 时间内计算出上述和式的值。 思路 首先，若计算和式： ∑i=111⌊11i⌋\sum_{i=1}^{11}\left \lfloor \frac{11}{i}\right \rfloor i=1∑11​⌊i11​⌋ 首先观察到，对于不同的 iii，⌊11i⌋\left \lfloor \frac{11}{i}\right \rfloor⌊i11​⌋ 的值有部分相同，呈现出“块状”结构。 i 1 2 3 4 5 6 7 8 9 10 11 ⌊11i⌋\left\lfloor...

我们可以使用形如 y=θ0+θ1xy=\theta_0+\theta_1xy=θ0​+θ1​x 的线性模型来拟合训练数据，也可以选择拥有更多参数的 y=θ0+θ1x+θ2x2y=\theta_0+\theta_1x+\theta_2x^2y=θ0​+θ1​x+θ2​x2 的多项式来拟合，也可以选择其它非线性模型来拟合。但不论选择何种模型，最终都要转化到如下最小化问题： min⁡∑i=1m(h(xi)−yi)2\min \sum_{i=1}^m(h(x^i)-y^i)^2 mini=1∑m​(h(xi)−yi)2 对于线性模型，我们已经掌握了使用梯度下降法和正规方程法来求解这个最小化问题。对于正规方程法，矩阵 XTXX^TXXTX 不一定是可逆的，我们可以使用 正则化 来解决这个问题。 欠拟合和过拟合 假如有 nnn 个训练数据，我们可以使用 y=θ0+θ1xy=\theta_0+\theta_1xy=θ0​+θ1​x 的线性模型来拟合，也可以使用...

2025年中国矿业大学转计算机学院机试题面及题解 样例输入和输出记不太清了，希望后续补充。 以下仅为本人考时解法，并非正解。 T1 题目描述 输入两个数 mmm 和 nnn，输出区间 [m,n][m,n][m,n] 中满足如下条件的所有数： 这个数是素数； 这个数的个位数字和十位数字的和的个位数等于百位数字。 输出要求从大到小，数之间空格隔开，并 5 个数字一行。 AC Code 12345678910111213141516171819202122232425262728293031323334#include <bits/stdc++.h>using namespace std;bool is_prime(int n){ if(n == 1) return false; for(int i=2;i*i<=n;i++) if(n%i == 0) return false; return true;}bool is_valid(int n){ int a = n%10; int b...

现在主流的机器学习、人工智能的语言非 Python 莫属，但是在理解深度学习算法原理，比如梯度下降法、正规方程法等时， MATLAB 在矩阵计算、可视化等方面具有天然的优势。因此，本篇文章主要讲述 MATLAB 的基本使用方法，并运用于简单的机器学习算法之中。 运算符 一些运算符（如加减乘除等）和主流编程语言（如 C++、Python ）基本一致，故省略。在这里介绍一些与主流编程语言不同的运算符： ~= 这类似于主流编程语言中的 != ，如 1~=2 返回 true ，而 1~=1 返回 false ； xor 这类似于 ^ ，表示异或运算，如 xor(1,0) 返回 1。 变量 MATLAB 和 Python 一样，定义变量时不需要声明数据类型。同时 MATLAB 和 Python 一样，也具有编译器和解释器。在 MATLAB 的解释器中输入 a = 3 ，会输出 a = 3 ，但假如在输入后加一个分号，如 a = 3; ，就不会输出，只执行赋值操作。 MATLAB 也有不同的数据类型，如整数、浮点数、字符串等，可以通过类似于 a = 3，a = 3.14，a =...

监督学习：给定一组样本（训练集），交给机器训练，让机器通过训练集来预测数据。 符号说明： mmm 训练样本的数量 xxx 输入变量/特征 yyy 输出变量/预测的目标变量 (x,y)(x,y)(x,y) 一组训练样本 (xi,yi)(x^i,y^i)(xi,yi) 第iii组训练样本 线性回归模型 监督学习的目的：根据训练数据得到一个假设函数 hhh ，这个假设函数可以实现：输入一个变量/特征，输出预测的目标变量。 在一开始，认为假设函数 h(x)=θ0+θ1xh(x) = \theta_0+\theta_1 xh(x)=θ0​+θ1​x ，也就是预测的目标变量是关于输入变量的线性函数。我们先拟合线性函数，在后续再对模型加以改进，引入更加复杂的模型。 这种线性模型被称作线性回归，上述的模型只有一个变量 xxx ，也被称为一元线性回归（单变量线性回归）。 代价函数 为了让我们的线性回归模型 h(x)=θ0+θ1xh(x) = \theta_0+\theta_1 xh(x)=θ0​+θ1​x 更加拟合训练数据，我们需要合理选择两个参数...

最小表示法 题目链接：最小表示法 最小表示法就是针对一个字符串，得到其同构循环串的最小字典序的一个 同构循环串：这里可以用一个队列方便理解：比如对于“123456789”，我们不断弹出队头将其放到队尾，得到的字符串即为其同构循环串 为了方便得到其算法，我们可以拿到一个数据进行模拟： 对于数据 2 3 6 5 1 7 8 9 3 0 我们要解决两个问题 ①如何存储其所有同构循环串？我们不需要用到队列，只需要将其复制一遍放到其末尾即可。于是就成为了2 3 6 5 1 7 8 9 3 0 2 3 6 5 1 7 8 9 3 0 ②如何得到其最优字符串？假如字符串长度为n，对于s[i]，我们很容易知道s[i]-s[i+n]这一段字符串是其一个同构循环串。比较字典序我们需要一个一个进行比较。因此我们可以指定两个指针i=0，j=1，让k从0循环到n，比较s[i+k]和s[j+k]，这样子就可以得到其每一位的大小。 1.若s[i+k]>s[j+k]，则说明0-i+k的所有字符串均不是最优解，所以i =...

字典树 题目链接：P8306 【模板】字典树 ①什么是字典树 字典树，又称Trie树，用于保存排序大量的字符串。其特点是能存储字符串的公共前缀，从而实现快速查询。 ②字典树的应用 字典树应用多样，比如最长公共前缀的查找，字符串排序，字符串的快速检索等等。 ③字典树的基本操作 无论什么字典树都离不开以下几点操作：建立、查找、插入 建立 字典树有三个性质：①根节点不存储任何数据，我们称之为虚点 ②从从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串 ③每个节点的所有子节点包含的字符都不相同 因此，我们可以用一个二维数组t[N][N]来表示字典树，但这里和一般的树状数组不同，我们用t[u][c]来表示节点u代表的字符串后面添加一个字符c所形成的字符串的节点。这里类似于链表，其中c的取值取决于我们的字符集的大小。那么我们的建树就显而易见了： 12345678910111213141516171819202122//字符转化成为ASCII码int getnum(char x){ ...