Qianmo's Blog

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){ ...

KMP 题目链接：Acwing 831. KMP字符串 KMP的过程一般比较抽象，较难理解。 题目背景： 123给定一个字符串S，以及一个模式串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串P在字符串S中多次作为子串出现。求出模式串P在字符串S中所有出现位置的起始下标。 我们先考虑暴力算法怎么做，然后怎么去优化： 假如s是比较长的串，p是比较短的串，我们可以遍历s的同时遍历p，即写一个二重循环。这么做的目的是为了按位匹配。在这个过程中设置一个变量flag来记录是否成功匹配。 假如出现不匹配的情况，即s[i+j-1]!=p[i]，那么我们直接break，同时把flag变为false 这个时间复杂度是感人的，为O(n∗m)O(n*m...

...

Nim游戏 Nim游戏属于公平组合游戏ICG，即满足以下特点： 由两名玩家交替行动 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关 不能行动的玩家判负 先看一下模板题题目： 甲，乙两个人玩 nim 取石子游戏。 nim 游戏的规则是这样的：地上有 nnn 堆石子（每堆石子数量小于 10410^4104），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 nnn 堆石子的数量，他想知道是否存在先手必胜的策略。 举个例子，对于两堆石子2 3，先手从第二堆拿了一个，变成2 2，那么接下来不管后手从哪一堆石子拿几个，先手只需要在另一堆石子里拿相同个数的石子就能保证最后后手没有石子取。比如后手从第一堆里拿一个，变成1 2，先手只需要在第二堆里拿一个，变成1 1，后手再从第一堆里拿一个，变成0 1，先手拿掉，变成0 0，先手获胜 我们先引出两个概念： 先手必败状态：在Nim游戏中指先手遇到0 0，此时先手必败 先手必胜状态：先手如果通过某些操作能够走到必败状态，即0...

题解：P11276 第一首歌 题意 这道题需要我们找到一个最短的字符串，使得给定的字符串既是它的前缀也是它的后缀。 KMP算法 用 pi[i] 表示字符串 s[0:i] 的最长的即是前缀又是后缀的子串的长度，那么 pi[n-1] 就是整个字符串最长的即是前缀又是后缀的字串的长度，也就是我们的答案的长度。 假设 k = pi[n-1] ，意味着整个字符串最长的即是前缀又是后缀的字串的长度为 k ，则 s[0:k] 既是s的前缀也是 s 的后缀，那么我们只需要把 s[0:k] 加上 s.substr(k) 就能得到最小的满足条件的答案 计算pi数组 其中 pi 数组是整个题目的关键所在，我们通过 while 循环不断回到之前的前缀位置，直到匹配或找到最大前缀后缀，具体见代码。 代码 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;const int N = 1e6+10;int pi[N];int main(){ string s; cin...

本题采用双向 BFS 来解决。 首先分析一下时间复杂度：变换规则数 R≤6R \leq 6R≤6 ，字符串长度 L≤20L \leq 20L≤20，操作数在 10 次以内，用朴素 BFS 的时间复杂度为 O((L⋅R)10)O((L\cdot R)^{10})O((L⋅R)10) ，完全爆炸；采用双向 BFS 的时间复杂度为 O((L⋅R)5)O((L\cdot R)^{5})O((L⋅R)5) ，相对于朴素做法降低了很多的时间复杂度。 但对于本题，可能出现以下情况：每次变换可能在字符串的多个位置替换、变换规则可能形成“无限繁殖”的状态等，导致搜索空间飞速增长。双向 BFS 并不能保证通过本题的数据，但也是一种优化搜索的方法。 双向 BFS 的具体步骤： 开两个队列 qa,qbqa,qbqa,qb，一开始分别把起点和终点丢入队列中。 每次选择较小的队列进行扩展，将队头其可能经过变换规则得到的字符串丢入队列中（注意假如扩展 qbqbqb...