文章目录
- 一. 容斥原理
- 1.1 集合AUB
- 1.2 集合AUBUC
- 二. 知识回顾
- 三. 课后习题
- 3.1 丑数 III
- 3.2 播放列表的数量
一. 容斥原理
容斥原理在我们的高中数学中由了解过，就是两个集合A，B的并集的元素个数。同样，在大学里的概率论中也会讲解。
1.1 集合AUB
在概率论中,我们有这样的一个公式：
如图：
由于A与B有重叠部分，所以A+B后要减去一次重叠的部分（A∩B）。
1.2 集合AUBUC
如图：
很明显，E，F，G三个部分分别重叠了两次，所以我所我们要减(A ∩ B) ，(A ∩ C) ，(B ∩ C)，但也相当于减了三次G部分(A ∩ B ∩ C)，所以我们还要在加一次(A ∩ B ∩ C)。
以此类推。
二. 知识回顾
推荐专栏：
算法零基础100讲》(第14讲)最小公倍数
由于今日的题解需要用到最小公倍数，所以我们需要回顾一下，最小公倍数的计算方法。通过定理我们可以很明确的知道，a和b的最小公倍数就等于(a * b) / gcd(a，b)。
三. 课后习题
3.1 丑数 III
题目链接：
1201. 丑数 III
思路分析：
题目要求我们找出第n个丑数，而题目给定丑数的定义为，能够被a，b，c，整除的数。所以我们最容易想到的就是暴力枚举，从1开始枚举，当遇到a，b，c的约数时，便记录下来，直到找到第n位。
代码如下：
int nthUglyNumber(int n, int a, int b, int c){
int i = 1;
int Ugly = 0;
int cnt = 0;
while (i){
if (i % a == 0){
cnt++;
}
else if (i % b == 0){
cnt++;
}
else if (i % c == 0){
cnt++;
}
if (cnt == n){
Ugly = i;
break;
}
i++;
}
return Ugly;
}
但题目给定的数据范围为[1，2000000000]，很明显暴力的解法会超时，而这种时候我们就得想到一种时间复杂度更快的方法，所以我们很容易会想到O(logn)的二分法，但是这种解法与该题由上面联系呢？
接下来我们进行进一步的分析。
- 首先我们需要知道的是一个数 a 的约数中，小于n的约数个数为 [n / a]；
- 然后我们还需知道，两个数的a，b的公约数中，小于n的公约数个数为 [n / lcm (a, b)] ,其中lcm是最小公倍数。
现在我们假设ab , ac , bc分别为a和b，a和c，b和c的最小公倍数，abc为a,b,c的最小公倍数，假设他们不大于n丑数有m个，则m = n / a + n / b + n / c - n / ab - n / ac - n / bc + n / abc。
有了上面的m，我们在结果区间[1，2000000000]上取中间值mid，计算不大于mid的丑数有m个，我们便可以对m与题目所给的n(这里的n是题目给的n)进行比较，如果m < n则说明小于mid的丑数还不够n个，那么我们就需将mid增大，便将区间转化为[mid + 1，2000000000]，在从中找出新的mid，继续进行比较，直到区间重合，此时的区间值就是我们所求的第n个丑数的值。
代码如下：
#define ll long long
//计算表最大公约数
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
//计算最小公倍数
ll lcm(int a, int b){
return (ll)a / gcd(a, b) * b;
}
int nthUglyNumber(int n, int a, int b, int c){
ll ab = lcm(a, b);//a 和 b的最小共倍数
ll ac = lcm(a, c);//a 和 c 的最小共倍数
ll bc = lcm(b, c);//b 和 c 的最小公倍数
ll abc = lcm(lcm(a, b), c);//a, b, c的最小公倍数
int left = 1, right = 2000000000;
while(left < right){
ll mid = left + (right - left) / 2;
//不大于mid的约数有多少个
ll m = mid/a+mid/b+mid/c-mid/ab-mid/ac-mid/bc+mid/abc;
if(m < n){
left = mid + 1;
}
else{
right = mid;
}
}
return left;
}
3.2 播放列表的数量
题目链接：
920. 播放列表的数量
分析：
这是一道动态规划题，题目给了我们三个参数，n首不同的歌，播放列表长度goal，播放过的歌经过k首后才能在次播放。
思路：
- 首先我们需定义一个数组dp[goal + 1][n + 1]，dp[i][j]代表长度为 i 的播放列表中恰好包含 j 首不同的歌。
- 当我们要计算dp[ i ][ j ]时，我们是在dp[i - 1][j - 1]的基础上还剩下n - j + 1首歌未播放，所以我们可以从中任取一首。
- 又因为题目给定了一个k值，当播放一首歌后，在播放k首歌，即可重复播放该首歌，所以我们还需在dp[i - 1][ j ]的基础上再判断（j - k）是否大于0，如果大于0，则dp[i][j] += dp[i - 1][j] * (j - k)。
代码如下：
#define MOD 1000000007
int numMusicPlaylists(int n, int goal, int k){
long long dp[goal+1][n+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= goal; i++){
for(int j = 1; j <= n; j++){
dp[i][j] += dp[i - 1][j - 1] * (n - j + 1);
dp[i][j] += dp[i - 1][j] * fmax(j - k, 0);
dp[i][j] %= MOD;
}
}
return dp[goal][n];
}
第三道题太难了，我争取吧(lll￢ω￢)