DAY4共2题：
树（组合数学）
子序列（dp，数学）
🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 原文链接（阅读原文获得更好阅读体验）： https://www.eriktse.com/algorithm/1095.html
树
题目传送门： https://ac.nowcoder.com/acm/problem/13611
通过观察条件“ 一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。 ”我们可以发现，当且仅当 染色的点可以全部连通 时可以满足条件。
所以现在问题是如何将 n 个点划分为 k 块。
我们可以发现在树上，任意删除一条边都会使得联通块个数 + 1 。
其实块数只要 <= k 即可，因为我们可以有一些颜色不使用。所以要划分为 i 块，只需要从 n - 1 条边中任选 i - 1 条进行删除即可，方案数是 C(n - 1, i - 1) 。
假设现在我们得到了 i (i <= k) 个联通块，需要将 i 种颜色染上去，首先需要 C(k, i) 种方法取出颜色，然后 A(i, i) 一个全排列将颜色染上去。
所以答案公式如下：
$$ans=\sum_{i=1}^{k}C(n - 1, i - 1)C(k, i)i!$$
可能涉及一些 快速幂 、 乘法逆元 的知识，需要自行学习。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 350, p = 1e9 + 7;
int fac[maxn];
int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
int inv(int x){return qmi(x, p - 2);}
int C(int n, int m)
{
if(n < m || n < 0 || m < 0)return 0;
return fac[n] * inv(fac[n - m] * fac[m] % p) % p;
}
signed main()
{
int n, k;scanf("%lld %lld", &n, &k);
fac[0] = 1;
for(int i = 1;i <= n; ++ i)fac[i] = fac[i - 1] * i % p;
int ans = 0;
for(int i = 1;i <= n; ++ i)//分为i块
{
int tmp = C(n - 1, i - 1) * C(k, i) % p * fac[i] % p;
ans = (ans + tmp) % p;
}
printf("%lld\n", ans);
return 0;
}
子序列
题目传送门： https://ac.nowcoder.com/acm/problem/17065
小技巧：观察数据范围，比较小，应该可以容纳O(n^3)的复杂度，所以可以大胆考虑dp。
首先定义状态 dp[i][j] 表示 以第i个元素结尾，且长度为j的序列的个数 。
再考虑一下转移，题目中的条件可以进行一些转换：
$${a_{p_i}}^{p_j} < {a_{p_j}}^{p_i}$$
等价于：
$$ \frac{log(a_{p_i})}{p_i} < \frac{log(a_{p_j})}{p_j} $$
我们可以记：
$$ b_i = \frac{log(a_{p_i})}{p_i} $$
也就是说 对于选出的子序列中的每一个元素 ，他们满足一个偏序关系，只要我的 b[j] > b[i] ，那么 b[j] 将会大于所有的 b[k] (k < i) 。
所以我们可以考虑以下的转移：
$$dp_{i, j} = \sum_{k=1}^{i - 1}[b_i > b_k] \times dp_{k, j - 1}$$
考虑初始化，当最后一个元素确定，序列长度为1 (j = 1) 时，方案仅有 1 种。
最后的答案是将所有情况加起来（注意取模，不过这道题数据较弱，不取模也可以过）。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 109, p = 1e9 + 7;
//dp[i][j]表示以第i个元素结尾，长度为j的方案数
int a[maxn], dp[maxn][maxn];
signed main()
{
int n;scanf("%lld", &n);
for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);
for(int i = 1;i <= n; ++ i)
{
dp[i][1] = 1;
for(int j = 1;j <= i; ++ j)
{
for(int k = 1; k < i; ++ k)
{
if(log(a[k]) / k < log(a[i]) / i)
{
dp[i][j] += dp[k][j - 1];
dp[i][j] %= p;
}
}
}
}
int ans = 0;
for(int i = 1;i <= n; ++ i)
for(int j = 1;j <= i; ++ j)
{
ans = (ans + dp[i][j]) % p;
}
printf("%lld\n", ans);
return 0;
}
🎈 本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬
查看更多关于【ACM算法竞赛日常训练】DAY4题解与分析【树】【子序列】| 组合数学 | 动态规划的详细内容...