GhostLX

题解

/ 注册

全部文章 / 题解（共9篇）

题解 | #组合数第k小#

题目描述大意：求解第kkk小的组合数算法一：set+组合数算法思路以下是1-12的组合数的图通过图片我们可以发现C(i,0)=C(i,i)=1C(i,0)=C(i,i)=1C(i,0)=C(i,i)=1 因为还有的组合数重复，所以我们用setsetset来去重故我们可以用一个se...

数学

2021-09-02

1 681

题解 | #浅尝辄止#

题目陈述大意：求解表达式的值算法一：朴素算法算法思路暴力算法，枚举每个，计算其对答案的贡献，遍历所有的即可代码实现 class Solution { public: int work(long long n) { long long ans = 0; fo...

数学

2021-08-27

1 534

题解 | #序列取反问题#

题目陈述大意：给定一排牛牛，一开始都是不快乐的牛牛，每次等概率选择一个当前不快乐的牛牛，将[i,a[i])[i,a[i])[i,a[i])中的牛牛都变为快乐，最后所有的牛牛都变为快乐的在modmodmod mmm意义下，的期望步数是多少？前置知识这题是一个ACM竞赛中很经典的树上期望问题，在...

数学概率期望差分约束前缀和

2021-08-27

2 507

题解 | #牛牛算题#

题目陈述大意：给定一个正整数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 ...

数学整除分块

2021-08-26

1 683

题解 | #牛牛的冰激凌#

题目描述大意：公司让你负责m个冰激凌的运输。运输车的冷库只够装n个冰激凌，一次运输需要t分钟，返回也需要t分钟。每个冰激凌制作好有一个时间。求最短运输完所有冰激凌的时间，以及在时间最短的情况下最少运输次数。（这题真的不知道怎么写个暴力了，如果写个暴力，不失正确性，发现不就是记忆化搜索？？？递推的顺...

动态规划贪心贪心数学

2021-07-23

2 679

题解 | #牛牛摆木棍#

题目陈述大意：定义波浪形序列为：序列中间的每个数都大于他的相邻的数或者小于他相邻的数。大小定义为字典序大小，求长度为n的序列中第k个波浪型的序列。算法一：朴素算法算法思路一个很显然的思路，就是暴力枚举，字典序递增算出每一个序列，直到第k个开一个vector来记录当前的序列，第i层代表当...

动态规划数学集合

2021-07-17

0 706

题解 | #丑数#

题目陈述描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。算法一：质因数分解（暴力）算法实现一个很朴素的做法从每次+1，一直枚举，直到找到地N个丑数为...

集合堆数学

2021-06-21

21 2162

题解 | #整除问题#

题目陈述给定 a, b, c, d，求所有被 2021 整除的 (x, y) 数对个数，其中。算法思路前缀和思想 and 容斥原理（计数问题经常见）前缀和思想我们用前缀和的思路来想这个问题,我们要求的是[a,b]和[c,d]中满足条件的数对,如图所示计算区间[1,b]和[1,...

面试容斥原理数学

2021-06-18

2 544

题解 | #最大公约数#

题目陈述题目大意：求正整数a,b的最大公约数x仔细审题：最大公约数，即不存在一个比x大，且同时能整除整数a,b的正整数算法一：暴力做法算法思路设mi=min(a,b),即mi为a,b中较小的那个数字 for循环暴力求解，i从1开始循环，到mi截至（因为不存在因数比原数字大的情况），如果能整...

面试递归数学

2021-06-18

25 1625