为什么要学习递归与非递归的转换的实现方法? 并不是每一门语言都支持递归的. 在SD，省选的老年机栈空间十分小 非递归毒瘤 递归与非递归转换的原理 递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的. 稍有常识的人都知道，学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非 递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树说明,不过大多数情况下二叉树已经够...

去旅游了 (大雾 本来是 月份就有这篇文章的, 由于博主还要学文化课就咕咕咕到现在 主要就是 爆零的感受 前 Day - 准备初赛 不知道是前第几天了 初赛前做初赛题 定理完全不会, 希望不要考到吧 事实证明到现在 Shq 也不会 Day - 初赛 初赛很悬, 差点初赛退役 ( 考前疯狂学 定理, 希望多拿几分 然后考试考了个等差数列求和??? 还是原题? 考试两道数学题都蒙对了 ( 得知线段 的那个题目要用定积分直接凉 自闭 Day - 初赛后 自闭 初赛可能过不了 惊奇发现卡线过复赛 Day - 去清北学堂爆零 qbxt 做了几场原题赛 有时候交文件夹合法, 交...

题目链接 题目描述 栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。 由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是(0, 0)。 能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能 量的损失为2k +...

字符串算法三连击 Hash算法 如何快速判断两个字符串 相等？ 如果两个字符串被同一个函数 映射到相同的值，也就是 ，那么有可能 仔细地选择 ，可以使得 的概率很大，从而完成快速判断 其中 取质数（当 不是质数的时候降低碰撞概率），例如 。其中 可以取： ，用 位无符号自然溢出，计算速度快 级别的质数 当 取 级别质数的时候，应多取几个 以获得更高的正确率（只取一个是不行的） Hash快速计算 给定一个字符串 ，要求在 时间内快速获得任意一个子串的 函数 设 ，那么记： 则 的 函数就是： 预处理 , ， 计算子串 函数 利用Hash求LCP LC...

字符串算法三连击 在讲AC自动机之前我们先来看一下Trie树 Trie 树 Trie树可以用于查找一组字符串的前缀 图示: 最大异或和 给出 个数 ，求 思路 把每个数看成是一个 长度的二进制串，最高位是第一个字符，对这些二进制串构造一个 Trie 树， Trie 树上记录子树内一共有多少个数 考虑查询这个集合中的数与 异或的最大值，从最高位开始考虑，如果有这一位不同的就应该选择不同的那个分支。这样按照Trie 树走下去，就可以查找出来与 x 异或能得到的最大值 对于 到 每一个都这样做一次，就得到了最大值。时间复杂度 First 给 n 个字符串。现在你可以指定 2...

字符串算法三连击 本文是介绍KMP算法的运用 KMP算法 给定两个字符串 ，询问 是否在 中出现过，如果出现过要给出所有出现的位置，时间复杂度 KMP算法的核心是Next数组 Next 数组 定义 : 函数，它表示一个字符串的最长的严格前缀等于对应长度后缀的长度 ，因为前缀和后缀都是 ，并且没有更长的了 ，因为前缀和后缀都是 ，注意原串 也同时是前缀和后缀，但我们要求是严格前缀 ，因为不存在一个前缀等于对应长度后缀 对于一个字符串 ，我们定义它的 数组的第 项为 前 个字符构成的前缀的 函数对于字符串 来说，它的 数组是： 算法主体 如果要求 是否在 中出现...

求最短路是图论中的一项基本操作 最短路模版题目: Heat Wave 本文介绍一下几种最短路算法 （水chao题leng解fan 题目描述 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。 此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过个城镇，方便地标号為 到 。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条...

题目链接 [CQOI2018]九连环 题目背景 略 题目描述 圆环的装卸需要遵守两个规则: 第一个(最右边) 环任何时候都可以任意装上或卸下 如果第 个环没有被卸下，且第 个环右边的所有环都被卸下，则第 个环(第 个环左边相邻的环) 可以任意装上或卸下 与魔方的千变万化不同，解九连环的最优策略是唯一的。为简单起见，我们以“四连环”为例，演示这一过程。这里用 表示环在“剑”上， 表示环已经卸下。 初始状态为 1111 ,每步的操作如下: 1101 (根据规则2,卸下第 2 个环) 1100 (根据规则1,卸下第 1 个环) 0100 (根据规则2,卸下第 4 个环) 0101 (...

题目链接 工艺 Description 小敏和小燕是一对好朋友。 他们正在玩一种神奇的游戏，叫Minecraft。 他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。 他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。 两个工艺品美观的比较方法是，从头开始比较，如果第 个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 个方块。如果全都一样，那么这两个工艺品就一样漂亮。 Input 第一行两个整数 ，代表方块的数目。 第二行 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。 Ou...

氵一篇 Blog Shq 只会刷水题了 /kel 题目链接 1601. [Usaco2008 Oct]灌水 Description Farmer John 已经决定把水灌到他的 块农田，农田被数字 到 标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库 建造一个水库需要花费 , 连接两块土地需要花费. 计算 Farmer John 所需的最少代价。 Input *第一行：一个数 *第二行到第 行：第 行含有一个数 *第 行到第 行：第 行有 个被空格分开的数，第 个数代表 Output *第一行：一个单独的数代表最小代价. S...

线性基入门 下面数学内容大概是氵长度，可以暂且跳过直接看线性基 前备知识 本文的前备知识： 什么是向量，懂得常用表示方法 了解什么是方程组 善用搜索引擎搜索自己需要的内容 搜索亦是一门艺术 基 任何向量可由它所处的空间中的 基向量 线性组合表示，向量就是将基向量缩放并相加得到的。所以有了缩放和相加，就可以在基向量确定的空间构造任意向量。 比如二维空间的基向量通常被叫做 和 ，那么对于向量 就可以表示为 采用数值描述一个向量时严格依赖于当前使用的基，对于向量 在不同基的情况下是不同的 线性组合 两个数乘向量的和，就可以被称作 线性组合 比如对于 就是 和 的线性组合 下面...

题面 题面大意 对于长度为 的序列 , 将其分为几段, 对于段 的花费为 , 求最小花费 Problem Description Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate t...

简要题意 给你一颗点有点权的树, 次询问, 每次询问两点间路径点权的子集的最大异或和 #2013. 「SCOI2016」幸运数字 题目描述 A 国共有 座城市，这些城市由 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。 一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 号城市，沿着 号城市到 号城市之间那条唯一的路径游览，最终从 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清...

大概没有什么技术性内容 下面是一些前置知识 隐函数 定义 隐式方程 是形如 的方程, 其中 是一个多元函数 由上面隐式方程所定义的函数叫做 隐函数, 比如 圆锥曲线 导数 偏导数 是多元函数 对于其中一维 的导数, 通常表示为 或者是 可以看作是 的另一种写法, 用来表示偏导数 全导数 是多元函数 的导数, 并非偏向某一维 显然地, 全导数在点 存在的条件为此多元函数在 某邻域内的各个偏导数存在且偏导函数在该点都连续 下面是一些常用记号 的一阶偏导数: 的二阶偏导数: 下面就是关于多元函数全导数的计算: 对于多元函数 , 现在求这个函数的全导数 先求出 关...