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 longusing 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 longusing 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原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言