出题人题解：https://zhuanlan.zhihu.com/p/575803044?， F会从重测的呜呜呜大家轻点骂

出题人题解：https://zhuanlan.zhihu.com/p/575803044

题目陈述 大意：给定一个字符串仅由'5'、'2' 、'0' 和‘？’组成，其中'?'可以代表任何一个字符，所有可能的字符串中，位置不同的为 "520" 的子序列共有多少个？ 算法一：朴素算法 算法思路 最暴力的想法，直接枚举“520”的所有可能 第一层循环枚举5和？，第二层枚举2和？，第三层循环枚举0和？ 当然，此处枚举时，要注意'2'的位置一定得在‘5’的后面，‘0’得在‘2’的后面代码实现 typedef long long LL; //简化声明定义long long class Solution { public: LL a, b, c, md = 99824...

题目陈述 大意：给定两种若干数量的蛋糕和一些盘子，问所有的分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量是多少。所有分法应该满足：同一个盘子不装有两种蛋糕、每个盘子都有蛋糕。 算法一：朴素做法 算法思路 为了不多次重复冗余的文字，接下来我们约定，将蛋糕数量最少的盘子中分到最多的蛋糕数量称为。 我们先这样分析，如果有个盘子，只有一种蛋糕，数量为，那么所有分法的就是 为什么？此处我们感性理解一下，取的时候，一定是所有盘子的最大值和最小值的差值是最小的，如果不是最小的，将最大值的几个蛋糕，移动到最小值上面，我们又得到了更大的，与我们当初的定义相互矛盾。 我们从依次一个位置一个位置放蛋糕，循环的放置...

题目描述 大意：求解第kkk小的组合数 算法一：set+组合数 算法思路 以下是1-12的组合数的图 通过图片我们可以发现C(i,0)=C(i,i)=1C(i,0)=C(i,i)=1C(i,0)=C(i,i)=1 因为还有的组合数重复，所以我们用setsetset来去重 故我们可以用一个setsetset来维护这些组合数的大小，但是计算的时候就不重复插入111 将所有的组合数插入到setsetset中，最后返回setsetset中第kkk小的数 计算组合数时，我们只需要计算底数≤i\leq i≤i的即可 求解单个组合数，CnkC_n^kCnk​分子分母约分后，可以在O(k)O(k)O(...

题目陈述 大意：求解表达式的值 算法一：朴素算法 算法思路 暴力算法，枚举每个，计算其对答案的贡献，遍历所有的即可 代码实现 class Solution { public: int work(long long n) { long long ans = 0; for (int i = 1; i <= n ; i ++ ) //枚举所有的i ans += n / i; //计算i对答案的贡献 ans %= 998244353; //对答案取模 return ans; } }; 复杂度分析 时间复杂度，所有...

题目陈述 大意：给定一排牛牛，一开始都是不快乐的牛牛，每次等概率选择一个当前不快乐的牛牛，将[i,a[i])[i,a[i])[i,a[i])中的牛牛都变为快乐，最后所有的牛牛都变为快乐的在modmodmod mmm意义下，的期望步数是多少？ 前置知识 这题是一个ACM竞赛中很经典的树上期望问题，在该模型上做出一定变形的题目 相信我讲完这个树上期望问题的模型，大家会更加容易理解 模型 给定一颗树，然后每次随机删除一个节点，删除它的同时他的子树都会消失，每次删除的节点等概率，问删除掉所有节点的期望步数 解释模型 此处我解释一下模型的题意 如果给定了一下这棵树 有两种删除这棵树的方...

题目陈述 大意：给定一个正整数nnn，nnn表示为n=p×k+mn=p\times k + mn=p×k+m。即，nnn充当被除数，对于p,1≤p≤np,1 \leq p \leq np,1≤p≤n，充当除数，然后得到对应的余数mmm，求对于所有的除数p（1≤p≤n）p（1 \leq p \leq n）p（1≤p≤n）的商kkk与余数mmm的乘积之和，即∑k=⌊n/p⌋k∗m\sum_{k=\lfloor n/p\rfloor} k*m∑k=⌊n/p⌋​k∗m，答案取模modmodmod 算法一：朴素算法 算法思路 根据题意，一个很显然的算法，就是对于每一个ppp分别计算出他的k,mk,mk...

题目描述 牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下： 游戏地图内共有n个星球，共有m条隧道连接这些星球。每条隧道都是双向的，每两个星球间不一定只有一条隧道。现在牛牛占领了这n个星球中的p个星球，牛妹占领了这n个星球中的q的星球（每个星球最多只能被一个人占领）。现在牛牛想知道他占领的p个星球中任意一个星球，到牛妹占领的q个星球中任意一个星球，这两个星球的最短距离是多少。 算法一：暴力+最短路径 算法思路 一个很显然很暴力的思路，将牛牛统治的每一颗星球，都跑一次最短路径 然后每次最短路径中，再选择到牛妹占领的星球距离最短的，设置为当次的最短距离 这样总共跑p次最短路径就可以得到答案 我这边...

题目描述 大意：公司让你负责m个冰激凌的运输。运输车的冷库只够装n个冰激凌，一次运输需要t分钟，返回也需要t分钟。每个冰激凌制作好有一个时间。求最短运输完所有冰激凌的时间，以及在时间最短的情况下最少运输次数。（这题真的不知道怎么写个暴力了，如果写个暴力，不失正确性，发现不就是记忆化搜索？？？递推的顺序也不难发现，跟dp大同小意，所以此题我写暴力方法了） 算法一：动态规划 思路引入 （此处默认已经将c数组排序过了） 一个很直观的思路，如果我当前有n个冰淇淋，并且我人已经在工厂了，我肯定是立马送出 因为如果我在原地还等待，就算制作出了n+1个冰淇淋，我也依旧不能运输出去 因为冰淇淋没有差别，如果...

题目陈述 大意：n朵花排成一圈，最小化相邻两朵花高度差的最大值，输出最大值。 约定：将所求值成为丑陋值，即要求最小的丑陋值算法一：暴力做法 算法思路 因为已经知道了有n个数字，我们只需要生成这n个数字的所有排序 然后依次计算每个序列的丑陋值，依次更新ans，求出最小的即可代码实现 class Solution { public: int arrangeFlowers(int n, vector<int>& a) { sort(a.begin(),a.end());//排序 int ans=1e9;//ans初值需要足够大，才能保证第一次就被...

算法一：哈希映射 算法思路 开一个map容器或者是unordered_map容器来记录一个数出现的次数，最后在逐个访问容器中的元素，找到比大的那个就行了复杂度分析 值得注意的是map和unordered_map内嵌数据结构是不同的，map是红黑树，unordered_map是哈希表使用map 时间复杂度，对于map来说是插入、修改、删除操作都是一个级别的时间，所以总得时间复杂度是 空间复杂度，map利用率100%,为使用unordered_map 时间复杂度，unordered_map是哈希表，所以每次访问映射后的数是近似的所以总得时间复杂度为 空间复杂度，unordered_map的...

题目陈述 大意：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表 算法一： 算法思路 不难发现，二叉搜索树（BST）的中序遍历，得到的序列，是递增的 而需要的双向链表也就是利用递增序列排序的 因为STL中的vector是个模板类，也就是说他不仅仅可以装整数和字符，还可以装任意类型的，所以我们就用vector来装指针 然后依次连接vector中的前后指针即可代码实现 vector<TreeNode*> v;//将节点指针直接放入vector中，以便于直接访问 class Solution { public: void inOrder(TreeNode* ...

题目陈述 大意：定义波浪形序列为：序列中间的每个数都大于他的相邻的数或者小于他相邻的数。大小定义为字典序大小，求长度为n的序列中第k个波浪型的序列。 算法一：朴素算法 算法思路 一个很显然的思路，就是暴力枚举，字典序递增算出每一个序列，直到第k个 开一个vector来记录当前的序列，第i层代表当前要填写的是第i个数字，那么递归边界就是n+1层（前面n个数字都已经填写完毕） 那么我们该如何按字典序搜索？对于同一个位置填写的i，下一个位置如果填写的下降的，显然比上升的字典序来的小，所以应该先搜索下降的，再搜索上升的 如果确定了前两个数的关系，整个序列的山顶和山谷的位置也就确定了，只需要定义...