空白阴影的个人博客

测试预览

数论基础整除对于整数 和正整数 ，如果存在整数 使得 ，则称 能被 整除，记作 。否则，称 不能被 整除，记作 。 模运算性质在模运算的意义下， 与 （其中 是任意整数）是等价的。如在模 意义下，-2 与 6 是等价的。 加减法： 乘法： 同余对于整数 和正整数 ，如果 ，则称 与 在模 意义下同余，记作 。否则，称 与 在模 意义下不相等，记作 。 质数试除法判定质数题干给定 个正整数 ，判定每个数是否是质数。 输入格式第一行包含整数 。 接下来 行，每行包含一个正整数 。 输出格式共 行，其中第 行输出第 个正整数 是否为质数，是则输出 Yes，否则输出 No。 数据范围 输入样例：123226 输出样例：12YesNo 思路分析直接使用试除法判断是否为质数即可。对于每个数 ，只需要判断 到 之间是否存在它的因子即可。如果存在，则 不是质数；否则， 是质数。注意建议使用 而不是 来避免乘法溢出。 123456789101112131415161718192021222324252627282930#include &...

深度优先遍历与回溯算法排列数字题干给定一个整数 ，将数字 排成一排，将会有很多种排列方法。 现在，请你按照字典序将所有的排列方法输出。 输入格式共一行，包含一个整数 。 输出格式按字典序输出所有排列方案，每个方案占一行。 数据范围 输入样例13 输出样例1234561 2 31 3 22 1 32 3 13 1 23 2 1 思路分析本题考查深度优先遍历（DFS）和回溯算法。通过递归地选择数字，标记已使用的数字，构造排列，最终输出所有排列方案。 不妨设我们用 path 数组存储当前排列方案，用 st 数组标记数字是否被使用过；dfs(u)表示当前已经排列了 u-1 个数字，接下来需要排列第 u 个数字。 递归终止条件：当 u > n 时，说明已经排列完所有数字，输出当前 path 数组中的排列方案。 递归过程： 遍历数字 1 到 n，检查数字 i 是否被使用过（即 used [i] 是否为 true）。 如果数字 i 未被使用过，则将其加入当前排列方案 path [u]，并将 used [i] 标记为 true。 递归调用 dfs(u+1)以排列下一个数字。 回溯时...

链表单链表题干实现一个单链表，链表初始为空，支持三种操作： 向链表头插入一个数； 删除第 个插入的数后面的一个数； 在第 个插入的数后插入一个数。 现在要对该链表进行 次操作，进行完所有操作后，从头到尾输出整个链表。 注意:题目中第 个插入的数并不是指当前链表的第 个数。例如操作过程中一共插入了 个数，则按照插入的时间顺序，这 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 个插入的数。 输入格式第一行包含整数 ，表示操作次数。接下来 行，每行包含一个操作命令，操作命令可能为以下几种： H x，表示向链表头插入一个数 x。 D k，表示删除第 个插入的数后面的数（当 为 0 时，表示删除头结点）。 I k x，表示在第 个插入的数后面插入一个数 x（此操作中 均大于 0）。 输出格式共一行，将整个链表从头到尾输出。 数据范围所有操作保证合法。 输入样例：123456789101110H 9I 1 1D 1D 0H 6I 3 6I 4 5I 4 5I 3 4D 6 输出样例：16 4 6 5 思路分析使用数组模拟单链表，e[] 存储节...

快速排序快速排序题干给定你一个长度为 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式输入共两行，第一行包含整数 。 第二行包含 个整数（所有整数均在 范围内），表示整个数列。 输出格式输出共一行，包含 个整数，表示排好序的数列。 数据范围 输入样例：1253 1 2 4 5 输出样例：11 2 3 4 5 思路分析快速排序（Quicksort）是一种高效的排序算法，采用分治法策略。其基本思想是： 从数列中选择一个“基准”元素。 重新排列数列，使得所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面（相同的元素可以放在任意一边）。在这个分区结束之后，该基准就处于数列的中间位置。 递归地将小于基准元素的子数列和大于基准元素的子数列排序。 当子数列的大小为零或一时，递归结束，因为这样的子数列已经是有序的。 最终，所有子数列合并起来就形成了一个有序的数列。 快速排序的平均时间复杂度为 。 快速排序在算法题中永远不会用到，因为STL的sort函数已经高度优化过了，直接调用即可；但是在面试题中可能会考，因此要记...

背包问题01背包问题题干有 件物品和一个容量是 的背包。每件物品只能使用一次。 第 件物品的体积是 ，价值是 。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式第一行两个整数，，，用空格隔开，分别表示物品数量和背包容积。 接下来有 行，每行两个整数 ，用空格隔开，分别表示第 件物品的体积和价值。 输出格式输出一个整数，表示最大价值。 数据范围 输入样例123454 51 22 43 44 5 输出样例：18 思路分析主要考虑两方面：状态表示和状态计算。 状态表示：在本题中，有两个变量：给定的物品和背包容量。如果这两个变量已知，那么一定会有一个确定的属性；这个属性在本题中就是背包物品价值的最大值。因此我们要根据给定的物品和背包容量，得到背包物品价值最大值的动态规划。对于这两个变量，为了方便划分，我们可以规定 表示只用前个物品，体积不超过的背包物品价值的最大值。我们的集合就是所有只从前个物品中选，并且总体积不超过的选法，维护的集合属性就是价值的最大值。 状态计算：本质上就是集合划分，我们要根据已有的数据，通过表达式得到...