可以在PTA补题。 题目大意 / Problem 给定两个字符串s和t，求一个s的子串s'使得s'和t的最大公共子串长度不超过1，问s'的最大长度。 子串可以不连续。 思路 / Thought 先把字符转换成[0, 25]的数字方便处理。 根据题意判断应该是个DP。由于是一个和位置和字符有关的dp，状态可以设为\(dp[i][j]\)，表示到s的第i个位置为止，最后一个敏感字符（定义为存在于t中的 […]

题目链接：The 2022 ICPC Asia Regionals Online Contest (I) (pintia.cn) 在PTA可以补题。 题意 / Problem 给定一个长度为N的01串，有Q次询问。 对于一个01串，每次可以代价为0的删除任意一个1以及和它相邻的两个数字，或者代价为1的将某个0翻转为1。 注意这个01串是环形的，也就是头尾相连，比如100也可以代价为0的进行一次删除 […]

题目传送门：P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 / Thought 关于二分图的最大匹配，参考以下文章： 算法学习笔记(5)：匈牙利算法 - 知乎 (zhihu.com) 最大匹配的思路可以这么理解：dfs(x)函数是用于判断x能否在另一边占到坑位，如果能那就占着，如果已经有人了就看能不能让这人去别的地方，如果可以就占着，否则 […]

使用试除法得到质因数的复杂度是\(O(\sqrt{n})\)，如果数字较大比如\(10^{18}\)就束手无策了。 在上一篇文章有写到Miller Rabin可以在\(O(klog^{2}{n})\)的复杂度下判断一个数字是不是素数，这次要介绍的Pollard Rho（普拉德柔）算法就是结合Miller Rabin的快速素性检验来进行的一个复杂度大约为\(O(n^{\frac{1}{4}})\)来 […]

我们知道一般的素数判断是\(O(\sqrt{n})\)的复杂度的，当\(n \le 10^{14}\)且仅判断个数较少的情况下尚且能用，如果需要判断k个较大的数字（\(n \le 10^{18}\)）的数字，估计一下要运算\(k * 10^8\)之多，显然无法接受。 介绍 / Introduction 这里介绍的MillerRabin算法是一种可以在\(O(k*log^{2}{2})\)的复杂度内 […]

在数字系统中除了机器码表示二进制数之外，还用四个二进制位表示一个十进制数，这种编码就叫BCD编码。 BCD码主要有8421、2421、余3码。 8421 BCD码 四个二进制位一共可以组成\(x^4=16\)个十进制数，而十进制数只有\(0 \sim 9\)这十个，所以是够用的。 因为BCD的四个二进制位的位权分别是\(2^3, 2^2, 2^1, 2^0\)所以这是8421码。 举个例子，\(2 […]

题目传送门：Problem - D - Codeforces 题意 / Problem 有一颗满二叉树，叶节点个数为\(2^N\)对于每个分支可以选择标记一条边，当A标记完成后，B可以选择修改k条边，请问最终获胜的节点最小是多少？（叶子节点编号为\([1,2^N]\)，如果某个叶子节点可以通过标记的边连接到根节点说明获胜），A希望结果尽可能小，而B希望结果尽可能大。 思路 / Thought 首先 […]

题目链接：B-Bitwise Exclusive-OR Sequence_第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） (nowcoder.com) 题意 / Problem 给定N个点，M条边，点权未知但是每条边上的边权就是其所连接的两个点的点权的异或和。问怎样规划点权可以使得所有点的点权加和最小，输出最小和。 注意：图不一定连通。（这个特别坑！！！） 思路 / Though […]

上一节《[Pytorch]机器学习入门项目笔记：手动实现线性回归（3）》写过手动实现线性回归，其实是半自动啦，因为使用了自动微分，但是却没有自动优化，也没有神经网络。只有单个的w和b，这样的网络容易出现过拟合或者无法拟合的问题，这一节写一下利用NN（神经网络）来实现线性回归。 首先引入需要的库文件 定义数据 这一步是创建出两个tensor，x是一个50 x 1的列向量，每个元素取值范围是[0, 1 […]

这是一个项目实践，通过自动微分、反向传播的方式来实现一个线性回归算法。 引入torch库 定义超参数 超参数就是在训练开始前需要预设的一些参数，这些参数会很大程度影响训练的速度和质量。 加载数据 这里随机生成一些点就可以了，根据函数表达式y = 3 * x + 0.8来构建x和y，定义域为[0, 1]。 x和y都是一个大小为[500, 1]的矩阵。 设置参数 这两个参数\(w, b\)就是我们要更 […]